Studying for this exam

[top]

• Understand the lecture slides and discussions thoroughly.
• Solve relevant problems in the Exam Database.
• Revisit the MPs and make sure you understand the solutions thoroughly. Repeat any you are not comfortable with.
• Take the sample exam as a dry-run for the actual exam.

Syllabus

[top]

The exam will cover the material through lecture slide set 09, up to and including regular expressions and DFAs as means of describing languages. It will not cover the material covered in the last part of class on June 22nd on converting from NFAs to DFAs. The following give examples of the kinds of questions you are likely to be asked for each topic (but the exam database provides a more comprehensive and useful source of example questions):

• Basic OCaml
  • Know the basic constructs (e.g., match, fun, let, let rec) like the back of your hand.
  • Be able to evaluate OCaml expressions
  • Be able to determine the type of OCaml expressions
• Recursion
  • Be able to write recursive functions, possibly tail-recursive.
  • Be able to recognize whether a function is tail-recursive, and when a recursive call is in tail call position
  • Understand the performance benefits of tail recursion.
• User-Defined Types
  • Be able to define record types and disjoint (variant) types in OCaml.
  • Know the difference between record and disjoint types, and when each should be used.
  • Be able to write OCaml functions over recursive disjoint types.
• Higher Order Functions (HOFs)
  • Be able to write the definitions of the common HOFs.
  • Be able to use map and fold to implement other functions, as in MP1.
  • Be able to write functions which use other functions as arguments
  • Be able to write map and fold functions appropriate to user-defined data types (like in lecture and in MP2)
• Types and Type Derivations
  • Explain and apply the key terminology of types and type systems.
  • Make type proofs and type inferences using typing rules
• Unification
  • Solve simple unification problems such as the ones in the lecture slides.
  • Know how unification is used for pattern matching, type checking, and type inference.
• Lambda Calculus (LC)
  • Describe and know how to apply α-conversions and β-reductions.
  • Write simple non-recurisve functions as λ-expressions.
  • Understand Church numerals and how to manipulate/generate them in LC (e.g, be able to write addition and multiplication λ-expressions).
  • Understand how other high-level datatypes are implemented in LC.
• Regular Expressions & DFAs
  • Be able to tell when a string is in the language of a regular expresion or DFA
  • Be able to construct simple DFAs/Regular Expression given a description of the strings they should accept.