CSCI 2720
Exam 2 Review Sheet
Topics:
- Recurrence Relations -- deriving, solving, the "Master Method" for divide-and-conquer
algorithms (this time, know the cases, as they won't be provided)
- Arrays and Strings:
- Contiguous Memory representation
- Column major v. row-major rep.
- Constant time initialization
- Sparse array representation: lists, hierarchical tables, special shapes
- String compression: Huffman Encoding
- String compression: Lempel-Ziv Encoding
- String searching: KMP
- String searching: Boyer-Moore
- List and Tree Implementation of Sets
- Unordered list v. ordered list search times
- The MTF heuristic
- The Transpose heuristic
- Binary Search in table rep -- procedure, running time
- Interpolation Search in table rep -- procedure, running time
- Skip Lists -- construction, perfect v. randomized, expected running time
- Binary Search Trees -- properties, insertion, deletion, expected and worst-case running times
- Static Binary Search Trees: Optimal, Probability-Balanced, Median-Split