CS 141 Final Study Guide
This is a fairly complete list of the topics you should know going
into the final. It does not necessarily represent everything that
will be on the final, but it is certainly the majority.
- Proof by induction and contradiction.
- Definitions of Big-Oh, Theta, and Omega
- Identifying known algorithms in different situations
- Huffman coding - the complete algorithm, from beginning to
end
- Strassen's Algorithm for matrix multiplication - what's the
concept, what's the recurrence relation. Not necessary to memorize S1
- S7.
- Karatsuba's Algorithm for integer multiplication - the whole thing
(since you had to implement it, you best know what you did.)
- Iterative Substitution method for solving recurrence
relations
- Recursion Tree method for solving recurrence relations
- Master Method for solving recurrence relations - understanding and
application, not memorization of the formulas
- Divide-and-Conquer techniques & example algorithms
- Greedy techniques & example algorithms
- Dynamic Programming techniques & example algorithms
- Graph terminology
- Graph representations
- BFS & DFS
- Topological Sort (both algorithms)
- Minimum Spanning Tree (Kruskal's algorithm)
- Max Flow: Finding a Flow, Max-Flow/Min Cut Theorem, Residual
Graphs, Reducing to Max Flow
- Min-Cost Flow: Definition, Reducing to Min-Cost Flow
- Dijkstra's Algorithm
- All-Pairs-Shortest-Paths
- Skip Lists: Detailed knowledge. Average overhead / node, detailed
algorithmic knowledge, average and worst case running times.
- Splay Trees: Be able to splay anything in the top 3 levels of a
tree. Understand how to implement Insert, Remove, and Find if you
have Splay. Worst case running times, average case running times.
Optimality of splay trees.
- Rot-13, Caesar Cipher, Vignere Cipher, One-time Pad