Exam 3
Exam 3 is focused primarly on the material since Exam 2 but will also review the material from the pervious exam.
Exam 3 contains only multiple choice or short answer problems. You will have 50 minutes to complete this exam.
Topics Covered
Topics from lecture (all BST concepts):
- Hash Table
- Hash functions
- Properties of a good hash function
- SUHA
- Hash Table Array
- Load Factor
- Hash Table Collisions
- Open Hashing vs. Closed Hashing
- Separate Chaining
- Linear Probing
- Double Hashing
- Re-Hashing
- Runtime of a hash table, in terms of
n
- Load factor’s impact on running times
- Properties of a good hash table
- Heaps
- Construction of a Heap
- Heap runtime
- HeapifyUp
- HeapifyDown
- Array Representation
- Priority queue ADT
- Disjoint Sets
- Union
- Smart Union (Size and Height)
- Find
- Path Compression
- Array Representation
- Disjoing Set Runtime
- Union-Find (Disjoint Sets) ADT
- Graphs
- Graph Representation
- Graph Traversal
- MST Algorithms Prim’s algorithm and Kruskal’s algorithm
Assignments referenced:
- mp_traversals, mp_mazes
- lab_hash, lab_btree, lab_heaps