The final consists of 6 questions spanning 8 pages.
It begins with short answer questions, some very easy, some not.
Then some problems where, if you know the material then you should
do very well. Finally, there is a problem that requires some
creativity, but, if you follow the hints carefully, then you should
be able to do it.
Make sure that you go over the midterm and can understand all questions
on it, particularly those that people found difficult last time.
Small variations of some midterm questions will appear on the final.
Additional topics to know for sure:
- Backtracking, 8-queens, tree size estimation.
- BRGC and its basic properties.
- Generating necklaces, prime strings, De Bruijn sequences.
- Plain changes algorithm, recursive (and iterative).
- Varol-Rotem algorithm, recursive and iterative.
- You may find it useful to review basic properties of binomial
coefficients (e.g., Pascal's triangle) and proofs by induction,
if you are a bit rusty on those topics.