You will have 110 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.
Exam Topics
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
Propositional Logic: translations, truth tables, equivalences, negations, ...
Practice Exams
We strongly suggest that you try to solve all of these problems yourself, on paper
without looking at the answer key until you're done. You may also want to time yourself to practice your pacing.
You will have 90 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.
The exam will be closed book, closed notes. You will not be allowed a calculator, cell phone, or any other electronic
device.
Exam Topics
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, ...
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 Exams
We strongly suggest that you try to solve all of these problems yourself, on paper
without looking at the answer key until you're done. You may also want to time yourself to practice your pacing.