CS 141 Midterm Study Guide
This is a fairly complete list of the topics you should know going
into the midterm. It does not necessarily represent everything that
will be on the midterm, 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