2806177
| Question | Answer |
| What do we store in a dictionary data structure? What three operations should we be able to perform? | We store (key,value) pairs. We want to perform add(x,v), lookup(x) and delete(x) |
| What does a hash function do? | |
| What data structure is used, when collisions are resolved by chaining? | Linked Lists |
| When building a linked list with chaining, what are the time complexities for add, lookup and delete? | O(1), O(length of chain containing x), O(length of chain containing x) |
| If h(x) and h(y) are chosen uniformly and independantly from [m], what is Pr(h(x) = h(y))? | 1/m |
| What is the expected run time per operation if we use a random hash function with chaining? | |
| For each key in U, we specify an arbitrary position in T. Why is this a bad choice for a random hash function? | We need ulogm bits, which is a ridiculous amount of space |
| Why can we not just pick the hash function when we first see x? | We would need to recall the hash function we use, therefore needing a dictionary to solve the dictionary problem! |
| Define Weakly Universal Hashing | |
| Explain why this scheme is weakly universal | ax + b is a linear transformation which spreads the keys over p values when taken modulo p. This causes no collisions. Only when taken modulo m do we get colliisions |
| What is the lemma for the longest chain in true randomness hashing? | |
| What is the lemma for the longest chain in weakly universal hashing? |
Want to create your own Flashcards for free with GoConqr? Learn more.