Final exam study guide

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.

Topics since Prelim 2

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.

Strong induction

Be comfortable proving things using strong induction.

Number theory

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.
Understand the basic properties of a hash function (while not a number theory topic, you analyzed a particular hash function that relied on modular arithmetic in this section of the course).

Graphs and NP

Define graphs, paths, cycles, degree in both directed and undirected graphs.
Know the connection between degrees and the number of edges. Know the handshaking theorem and its proof.
Define Hamiltonian and Eulerian paths/cycles. Define graph coloring. Know the connection between degree and Eulerian paths.
Understand the informal definition of NP-hardness. List the steps that need to be performed to check that a given problem is NP-hard (by reducing a known hard problem to it). Know that the 3CNF satisfiability problem is NP-hard.

Logic

Note: I may revise this section after we complete the logic lectures next week.

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