Structure
The exam will consist of autograded multiple choice and fill in the blank questions. Most multiple choice questions will allow you to submit twice, first for full credit and the second for a moderate amount of points.
Concepts
The exam will cover material presented in weeks 5 - 8. You should be familiar with everything covered in class or as part of an assignment. That said, to help you identify core topics that you should definitely prepare for:
- Stacks and Queues
- LIFO vs FIFO
- Allowable operations and how to use them
- Big O Efficiency
- Hash Tables
- Necessary properties of a hash function
- Necessary components for a hash table
- Methods for addressing hash collisions:
- Separate Chaining
- Linear Probing
- Quadratic Probing
- Double Hashing
- Big O Efficiency
- Simple Uniform Hashing Assumption
- Sets and Sketches
- Jaccard Coefficient
- Implementation details, how to use, and Big O for:
- Bloom Filter
- K-minima cardinality estimation
- Minhash sketch
- Sorting Algorithms
- Implementation details, how to use, and Big O for:
- SelectionSort
- InsertionSort
- MergeSort
- QuickSort
- I will not ask questions about sorting algorithm space efficiency
- Binary Search
- Implementation details, how to use, and Big O