Summary for midterm test 2
• Hash tables, direct-addressing hash table, average length of list in hash table, hash functions, universal family of hash functions, open addressing hash table.
• Dynamic programming algorithms, structure of optimal solution, recursive definition for value of optimal solution (Bellman equation), pseudo code of algorithm, running time, apply dynamic programming approach to solve a problem.
1
• Greedy algorithms, pseudo code of algorithm, correctness of algorithm, running time, apply greedy approach to solve a problem.
• Amortized analysis, apply one of aggregate analysis, accounting method and potential method to find the amortized cost of some operations (e.g., a sequence of operations on a dynamic table).
2