The final exam is cumulative. The material since the second prelim will be emphasized slightly more than the other material in the course.
Here are some sample questions from previous semesters (solutions). As usual, different topics have been emphasized to different extents in other semesters.
Reviewing the prelims and homeworks will also be helpful.
Here are the new topics since prelim 2; see also the prelim 2 study guide and the prelim 1 study guide. The list is potentially incomplete; everything covered in the lecture or homework is fair game.
Know definitions of regular expressions, language of a regular expression, "\(x\) matches \(r\)"
Be able to execute ε-NFA and generalized NFA
Be able to convert between DFA, NFA, and regular expressions. Know Kleene's theorem
Turing machines are out of scope
Know the statement of the Euclidean division algorithm, and how to apply it
Interpret a string of digits base \(b\) as a number, encode a number in base \(b\).
Know Euclid's GCD algorithm, and how to use it to compute Bezout coefficients
Know the definitions of modular numbers (\(\mathbb{Z}_m\)), and operations on those numbers. Prove that functions on \(\mathbb{Z}_m\) are well defined. Be comfortable moving between operations on modular numbers and operations on representatives.
Know the definition of a unit, \(\mathbb{Z}_m^*\), \(φ(m)\), inverse. Know how to find the units of \(\mathbb{Z}_m\), both by by finding the inverse by inspection and by checking for common factors.
Know Euler's theorem and how to apply it.
Use all of these concepts to solve equations and perform computations.
Know the RSA protocol, and the basic argument for why it is thought to be secure (factoring is thought to be hard). Know how to perform each of the steps efficiently.
Define propositional formula, interpretation, value of a formula in a given interpretation, validity, satisfiability, entailment.
Define soundness, completeness for a proof system.
Build simple proof trees for propositional formulas using natural deduction rules (you do not need to memorize the list of rules, although it would be good to understand introduction and elimination rules).
Some of the basic material on graphs will be in scope. I will update this section after this week's lectures to clarify.
Update: Know the following definitions:
Degree, eulerian cycle, hamiltonian cycle, coloring, graph isomorphism
Be able to determine whether a graph contains an eulerian cycle, and find one if it does.