Final exam topics

The final exam is cumulative: everything covered in lecture is in scope. Unlike prelim 2, we will place significant emphasis on older material as well as new. Consult the study guides for prelim 1 and prelim 2.

The material since the second prelim has no overlap with the past several semesters of 2800 (with the exception of structural induction and pumping lemma, which were on the practice prelims), so I am not posting practice finals.

Here is a (potentially non-exhaustive) list of topics covered since prelim 2:

RSA

• Know definitions of units and φ(m)
• Know Euler's theorem and what it means for modular exponentiation

• Give a 2-3 sentence overview of proof of Euler's theorem

• Give an overview of the RSA algorithm
  • e.g. recipient generates large primes p and q, publishes m = pq, generates k, a unit mod φ(m), ...

• Know how to compute k^− 1 mod φ(m) and [a]^k for large k

Structural induction

• Understand recursively/inductively defined sets
• Understand recursively/inductively defined functions
• Know how to set up a proof by structural induction

Computablity

• Pumping lemma
  • statement
  • how to use it
  • 2-3 sentence overview of proof
• Context free grammars
  • definitions
  • how to make them
• Turing machines
  • How to build them
  • Useful properties
    • can encode all known computational models
    • can be represented by strings
    • can simulate other turing machines
    • each point in computation can be represented by an ID, which is a string
    • can halt and accept, halt and reject, or run forever
• Recursive and recursively enumerable sets
  • Definitions
  • A good way to test your understanding is to prove for yourself the 9 properties proved on 11/20
• Definitions of NP-complete and NP-hard
  • be able to give a two to three sentence overview of the proof that SAT is NP complete

Logic

• Notation: ⊢, and ⊨
• Semantics of propositional logic (truth tables)
• Proofs in propositional logic (proof trees)
  • don't bother memorizing rules
  • do understand how a given rule works and what it means
• Know definitions of soundness and completeness