Difference between revisions of "FA19:Prelim 2 guide"

Latest revision as of 09:17, 30 October 2019

Prelim 2 will cover all material covered in lecture and homework between 9/27 and 10/25. I will update this guide after Monday's lecture to reflect what we have covered and what is in scope. 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.

Update: Based on where we got in lecture on 10/25, I've decided not to include automata theory in the scope of the exam. You should ignore the sample questions having to do with automata.

Here are some sample questions from past prelims: Media:fa19-prelim2-sample.pdf (solutions coming soon: Media:fa19-prelim2-sample-sol.pdf).

Review session board image And video.

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

Equivalence relations
- Relations: relation, reflexive, symmetric, transitive, equivalence relation, equivalence class, A/R, well-defined functions from A/R.
Induction
- Be able to do proofs by weak induction, strong induction, and structural induction (structural induction will be covered on 10/23).
- Understand inductively defined sets and inductively defined functions, including BNF notation (this will be covered on 10/23)
- Be able to apply the algorithms contained in inductive proofs
Number theory
- Key definitions:
  - quotient, remainder, base b representation, divisibility
  - greatest common divisor
  - Bézout coefficient,
  - equivalence mod m,
  - well-defined function,
  - modular number,
  - ,
  - unit, inverse, , ,
- 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,
  - RSA encryption and decryption
- Key results:
  - 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
Be able to build DFAs for simple problems

Understand how to prove that a DFA is correct

Key definitions:
alphabet, , language, string,

DFA, state, transition function, accept, L(M), recognize, [math][[\hat{δ}]] [/math]

Key results
Know how to prove that an automaton is correct (by giving and proving a specification for [math][[\hat{δ}]] [/math], see Lecture 23 Automata constructions)

@@ Line 1: / Line 1: @@
-Prelim 2 will cover all material covered in lecture and homework between 9/27 and 10/28.  I will update this guide after Monday's lecture to reflect what we have covered and what is in scope.  Material covered on prelim 1 will not be directly
+Prelim 2 will cover all material covered in lecture and homework between 9/27 and 10/25.  I will update this guide after Monday's lecture to reflect what we have covered and what is in scope.  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
@@ Line 5: / Line 5: @@
 closed book, closed notes, and will be 90 minutes long.
-Here are some sample questions from past prelims: [[File:fa19-prelim2-sample.pdf]]
+'''Update:''' Based on where we got in lecture on 10/25, I've decided not to include automata theory in the scope of the exam.  You should ignore the sample questions having to do with automata.
-(solutions coming soon: [[File:fa19-prelim2-sample-sol.pdf]]).
+Here are some sample questions from past prelims: [[Media:fa19-prelim2-sample.pdf]]
+(solutions coming soon: [[Media:fa19-prelim2-sample-sol.pdf]]).
+Review session [[Media:fa19-p2rev-board.pdf| board image]] And [https://vod.video.cornell.edu/media/t/1_c63qphr8 video].
 Here is a brief summary of what we've covered; for an exhaustive list see the [[Main Page]]:
+* [[Equivalence relation]]s
+** [[:Category:Relations|Relations]]: [[relation]], [[reflexive]], [[symmetric]], [[transitive]], [[equivalence relation]], [[equivalence class]], [[A/R]], [[well-defined functions from A/R]].
 * [[Induction]]
-** Be able to do proofs by [[weak induction]], [[strong induction]], and [[structural induction]].
+** Be able to do proofs by [[weak induction]], [[strong induction]], and [[structural induction]] (structural induction will be covered on 10/23).
-** Understand [[inductively defined set]]s and [[inductively defined function]]s, including [[BNF]] notation
+** Understand [[inductively defined set]]s and [[inductively defined function]]s, including [[BNF]] notation (this will be covered on 10/23)
 ** Be able to apply the [[algorithm]]s contained in inductive proofs
 * [[Number theory]]
@@ Line 23: / Line 30: @@
 *** [[modular number]],
 *** <math>[[ℤ_m]]</math>,
-*** [[unit]],
+*** [[unit]], [[inverse]], <math>[[ℤ_m^*]]</math>, <math>[[φ(m)]]</math>,
-*** [[inverse]],
-*** <math>[[ℤ_m^*]]</math>,
-*** <math>[[φ(m)]]</math>,
 ** Key algorithms:
 *** finding the [[base b representation]],
@@ Line 41: / Line 45: @@
 *** [[Euler's theorem]],
 *** [[Claim:⟦k⟧_m is a unit if and only if gcd(k,m) = 1]]
+<strike>
 * [[Automata]] theory
 ** Be able to build [[DFA]]s for simple problems
@@ Line 49: / Line 54: @@
 ** Key results
 *** Know how to prove that an automaton is correct (by giving and proving a specification for <math>[[\hat{δ}]]</math>, see [[SP19:Lecture 23 Automata constructions|Lecture 23 Automata constructions]])
+</strike>