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.

Office hours:
Friday: 2:30-3:30
Mon: 2:30-3:30
Tue: 10:00-11:00
Wed: 4:00-5:00

• 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.