| Titles make PowerPoint happy. |
| (not as much work as it looks) | |
| Perform Disjoint Union-Find operations on Up-Tree with path compression and using weight (# of nodes) in merges. | |
| Starting with empty tree. | |
| Keep track of (sub)tree weight, and pointers into tree (pointers isn’t too hard) | |
| Vaguely have a sense of # of operations (e.g. edge traversals) | |
| For items: a,b,c,d,e,f,g,h,i,j,k | |
| Union (a,b). Union (b,c). Union (d,e). Union (d,f). Union (d,j). Union (d,k). Union (e,g). Union (h,i). Union (c,h). Union (c,f). Find (i). Find (b). Find (c). Find (i). Find (h). |
| (diagram on next page) | |
| Make a random 3x3 maze with exactly one path between any two points | |
| Simulate up-trees (or don’t if you feel comfortable) | |
| Use edge order (first edge, second edge,…) on next page. | |
| Feel the power of the Dark Side |
| Show that Q-notation is an equivalence relation. Formal proofs not necessary. | |
| Contemplate putting functions into up-trees based on Q-notation (but not for too long…) |
| Hash table size 7, key=integers | ||
| Consider this hashing function: | ||
| H(X)= X mod 7 | ||
| What patterns of (distinct) keys would cause only one bucket to be used? | ||
| (answer on next page) | ||
| One answer: 0,7,14,21,28,… Integers may have a reason to be multiples of 7 (probably even worse if you’re hashing strings of English words – very biased data) |
| How about this hashing function: | |||
| given a parameters A,B,K: | |||
| HA,B,K(X)=(A*X+B mod 7K)/K | |||
| What patterns would cause only one bucket to be used? | |||
| For a given bad pattern, can you find different values of A,B,K to make this pattern OK (defeat your adversary)? | |||
| Given a patterns, if you ran your program many times with random A,B,K, what’s the average performance? | |||
| If you knew the data ahead of time, how could you design a really good hashing function? | |||
| In the extendible hash table on the
next page, perform the following inserts: 0100 0101 |
Extendible Hashing: table so far…
| Merge these binomial queues: |
| What happens when you insert this into a BST: 1,2,3,4,5,… | |
| What about a treap? | |
| Create a sequence of random numbers that’d create a perfectly balanced Treap for 1,2,3,4,5… | |
| What should the range of your random priorities be? What are bad properties for the random-number generator? |
Traverse & not-too Deep: Treaps
| Insert key 18 with random priority 2 into this Treap (don’t worry about “proper” way to rotate): |