All material from Lecture one up to and including relations is fair game. The exam will focus on the material from strong induction onwards.

Relations: you should be able to apply the relations definitions to prove properties of relations
Countability: you should be able to prove that a set is countable or uncountable
Undecidability: you should understand the halting problem and be able to evaluate the decidability of properties of programs
Irregularity: you should be able to prove a language is not regular
Powerset Construction to Convert NFAs to DFAs: you should be able to convert NFAs to DFAs
Conversion of Regular Expressions to NFAs: you should be able to convert regular expressions to NFAs
Minimizing FSMs: you should be able to minimize DFAs
Finite State Machines With Output: you should be able to construct FSMs with output for a given specification
Product Construction for DFAs: you should be able to use and understand the applicability of the product construction for DFAs
DFAs, NFAs, and Regular Languages: you should be able to construct DFAs and NFAs for languages
Context-Free Grammars and Languages: you should be able to construct CFGs for languages
Regular Expressions: you should be able to construct regular expressions for languages
Structural Induction: you should be able to read new definitions and write good structural induction proofs about them
Strong Induction: you should be able to write a good strong induction proof
Induction: you should be able to write a good induction proof
GCD/Extended Euclidean Algorithm/Solving Modular Equations running the algorithm, solving a given equation, understanding what inverses are
Modular Arithmetic: proofs, definitions, ...
Set Theory: set operations, set proofs, ...
English Proofs
Predicate Logic: translations, negations, ...
Circuits/Boolean Algebra: CNF/DNF, simplifying, proving identities, ...
Propositional Logic: translations, truth tables, equivalences, negations, ...