Midterm Exam

Wednesday, May 04, 2016 (4:30 pm6:00 pm, JHN 102)

Final Exam

Monday, June 06, 2016 (2:30 pm4:20 pm, JHN 102)
**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, ...

**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