How large should a hash table be? Goal: Make the table as small as possible but large enough so that it wont overflow(or otherwise become inefficient Problem: what if we don 't know the proper size

Fixed -universe successor problem Goal: maintain a dynamic subset s of size n of the universe 0=10, 1,.,u-1 of size u subject to these operations INSERT(X∈U\\S): Add x to s DELETE(X E S): Remove x from S

Computational geometry Algorithms for solving geometric problems in 2D and higher Fundamental objects: o point line segment

ynamic order statistics OS-SELECT(i, S): returns the i th smallest element in the dynamic set S. OS-RANK(, S): returns the rank ofx E S in the sorted order of s s elements IDEA: Use a red-black tree for the set S, but keep subtree sizes in the nodes

Balanced search trees Balanced search tree a search-tree data structure for which a height of o(g n)is guaranteed when implementing a dynamic set of n items

Binary-search-tree sort 7∈ b Create an empty Bst for i=i to n do trEe-INSert(,AiD) Perform an inorder tree walk of t Example:

a weakness of hashing Problem: For any hash function h, a set of keys exists that can cause the average access time of a hash table to skyrocket An adversary can pick all keys from tkeU: h(k)=i for some slot i IDEA Choose the hash function at random independently of the keys

Symbol-table problem Symbol table T holding n records

Order statistics Select the ith smallest of n elements(the element with rank i i=l: minimum, .i=n: marimum, i=L(n+1)/2]or[(n+1)/2 median Naive algorithm: Sort and index ith element Worst-case running time =o(n Ig n)+o(1 o(nIg n using merge sort or heapsort(not quicksort) c 2001 by Charles E Leiserson

How fast can we sort? All the sorting algorithms we have seen so far are comparison sorts: only use comparisons to determine the relative order of elements E. g, insertion sort, merge sort, quicksort heapsort The best worst-case running time that weve seen for comparison sorting is O(nIgn) Is o(nlgn) the best we can do?