SP19:Prelim 2 guide

Prelim 2 will cover all material covered in lecture and homework between 9/21 and 10/19 (inclusive). 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 problems on will be tested more heavily. The exam will be closed book, closed notes, and will be 90 minutes long.

Here are some sample questions from past prelims: File:Fa18-prelim2-sample.pdf (solutions: File:Fa18-prelim2-sample-sol.pdf).

Here are the board images from the review session: File:Fa18-revp2-board.pdf

Here is a brief summary of what we've covered; for an exhaustive list see the Main Page:

• Induction
  • Be able to do proofs by weak induction, strong induction, and structural induction.
  • Understand inductively defined sets and inductively defined functions, including BNF notation
  • Be able to apply the algorithms contained in inductive proofs
• Number theory
  • Key definitions:
    • quotient,
    • remainder,
    • base b representation,
    • divides,
    • greatest common divisor,
    • Bézout coefficient,
    • equivalence mod m,
    • well-defined function,
    • modular number,
    • [math]\href{/cs2800/wiki/index.php/%E2%84%A4_m}{ℤ_m} [/math],
    • unit,
    • inverse,
    • [math]\href{/cs2800/wiki/index.php/%E2%84%A4_m%5E*}{ℤ_m^*} [/math],
    • [math]\href{/cs2800/wiki/index.php?title=%CE%A6(m)&action=edit&redlink=1}{φ(m)} [/math],
  • Key algorithms:
    • finding the base b representation,
    • Euclid's GCD algorithm,
    • finding Bézout coefficients,
    • finding modular inverses,
    • fast exponentiation
    • computing φ(p) where [math]p [/math] is prime
    • computing φ(pq) where [math]p [/math] and [math]q [/math] are distinct primes,
  • Key results:
    • quotient and remainder are unique,
    • Euclid's GCD algorithm computes the greatest common divisor,
    • modular addition and modular multiplication are well-defined,
    • Euler's theorem,
    • Claim:⟦k⟧_m is a unit if and only if gcd(k,m) = 1
• Automata theory (Note: this section will be updated after Friday's lecture)
  • Be able to build DFAs for simple problems
  • Understand how to prove that a DFA is correct
  • Key definitions:
    • alphabet, [math]\href{/cs2800/wiki/index.php?title=%CE%A3%5E*&action=edit&redlink=1}{Σ^*} [/math], language, string,
    • DFA, state, transition function, accept, L(M), recognize, [math][[\hat{δ}]] [/math]
  • Know and be able to apply the pumping lemma