# SP20:Prelim 2 guide

Prelim 2 will cover all material presented from Monday 3/2 through Monday 4/20. Material covered on prelim 1 will not be directly tested, although you will still need to know how to write proofs and work with the basic mathematical objects necessary for those topics. Material that you have had homework and discussion problems on will be tested more heavily.

~~The exam will be closed book, closed notes, and you will have 100 minutes to complete and upload the exam, starting from when you download it.~~ More logistics will be posted on Piazza

Here are some sample problems selected from previous semesters. These questions are 10-15 minute questions; I would expect 4-7 of them on an exam (Solutions).

Review session videos are posted on Canvas. Here are the slides:

Here is a brief list of topics:

- Induction
- Understand inductively defined sets and inductively defined functions, including BNF notation
- Be able to write proofs by structural induction, both on strings, pairs, and on other kinds of objects
- Be able to apply the algorithms contained in inductive proofs

- Number theory
- Key definitions:
- equivalence mod m,
- well-defined function (esp. with domain )
- modular number,
- ,
- unit, inverse, , ,

- Key algorithms:
- finding modular inverses (including computing Bézout coefficients),
- fast exponentiation
- computing φ(p) where is prime
- computing φ(pq) where and are distinct primes,
- RSA encryption and decryption

- Key results:
- Be able to work with equations involving modular numbers
- Know the relationship between modular equivalence, remainders, and divisibility

- Key definitions:
- Automata theory
- Be able to build DFAs for simple problems
- Understand how to prove that a DFA is correct
- Key definitions:
- Key results
- Know and be able to apply the pumping lemma
- Know how to prove that an automaton is correct (by giving and proving a specification for Lecture 23 Automata constructions) , see
- Know and be able to apply the different parts of Kleene's theorem (converting DFA to NFA to RE, etc.)
- Turing machines are not in scope.