This exam is 1 hour and 50 minutes. It will be a mix of coding and theory questions as seen in the previous exams.
Topics Covered
The final exam is comprehensive and includes all materials on previous exams as well as the following that was not on any exam.
- Huffman Trees
- Tree construction
- Encoding
- Decoding
- Disjoint Sets
- Union
- Smart Union (Size and Height)
- Find
- Path Compression
- Array Representation
- Disjoing Set Runtime
- Union-Find (Disjoint Sets) ADT
- 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
- Probabilistic Data Structures
- Bloom Filters
- Count Min Sketch
It covers all material from all assignments in the course.