|
|
|
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 |
|
|
|
|
|
|
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? |
|
|
|
|
Insert key 18 with random priority 2 into this
Treap (don’t worry about “proper” way to rotate): |
|
Notes