Prelim 1 Review

Main topics to focus on for the exam:

  1. Evaluating OCaml expressions
  2. Pattern matching, tuples, records and lists
  3. Higher order functions and currying
  4. Map and fold
  5. Recursion and tail recursion
  6. Substitution model
  7. Modules and signature
  8. Data abstraction, representation invariants and abstraction functions
  9. Functional data structures: stacks, queues, dictionaries
  10. Function ordered trees: binary search trees, red-black trees
  11. Imperative data structures: disjoint set forest
  12. Induction

Work through problems, don't just read over your notes! There are lots of good problems with solutions in the notes; write down some questions that are answered in the notes, put the notes away, try to answer the questions, check your answers.