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

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