You will have X minutes to complete the exam. We will distribute the exam early and you can read and fill out the cover page of the exam, but you should not look at the exam questions until you are told to begin. You will not be allowed a calculator, cell phone, or any other electronic device.
All material from Lecture one up to and including induction is fair game; Strong Induction will NOT be on the midterm.

Propositional Logic: translations, truth tables, equivalences, negations, ...
Circuits/Boolean Algebra: CNF/DNF, simplifying, proving identities, ...
Predicate Logic: translations, negations, ...
Formal Proofs
English Proofs
Set Theory: set operations, set proofs, ...
Modular Arithmetic: proofs, definitions, ...
GCD/Extended Euclidean Algorithm/Solving Modular Equations running the algorithm, solving a given equation, understanding what inverses are
Induction: you should be able to write a good induction proof
Practice Exam
Practice Problems
Practice Proofs
Review Session

Recommended Questions: Weeks 1 - 2, Weeks 3 - 4
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, ...
Practice Exam
Practice Problems
Final Exam Definitions
Recommended Questions