SP19:Final study guide

The final exam is cumulative with a heavier emphasis on material covered since prelim 2. See the Prelim 1 study guide and the Prelim 2 guide for old material. The new material includes everything covered in lecture and on the homework.

Old finals (as usual, topics covered and level of detail vary somewhat from semester to semester):

Slides from the review session boards:

review session 1 slides, video
review session 2 slides, video

New topics include:

Automata theory:
- NFA, Regular expressions, Kleene's theorem

Combinatorics:
- Know and be able to apply the sum rule, product rule, quotient rule.
- Know how to count the number of permutations of a set of size [math]n [/math], the total number of subsets and the number of subsets of size [math]k [/math].
- Be able to write combinatoric proofs of equations between natural numbers.

Probability: Know and be able to apply the definitions and basic results:
- sample space, event, outcome, probability measure (including the Kolmogorov axioms), probability space
- conditional probability, independent events
- Bayes' rule, the law of total probability
- random variables, PMF of a random variable
- constant random variables, sum of random variables (as well as product, etc.), comparing random variables (e.g. X = y)
- indicator variables
- expectation (both definitions), variance (both definitions)
- independent random variables
- linearity of expectation, sum of variance of independent random variables
- Markov's inequality, Chebychev's inequality, Weak law of large numbers
  - including statements and proofs
- hash functions will be treated as an example, but you don't need to know the definitions of nice, or of [math]H_x [/math], etc. You should be able to understand the different parts of the analysis, though: random variables, indicator variables, linearity of expectation, setting up sample spaces, etc.

Logic: Know the basic definitions (these will not be tested deeply, since you have not had homework on them)
- inductive definition of the set of propositional formulas
- semantics:
  - truth tables
  - interpretations
  - evaluation function
  - [math]I [/math] satisfies [math]φ [/math] ()
  - tautology/validity ()
  - entailment ([math]φ_1, \dots, φ_n ⊨ ψ [/math])
- proof trees, soundness and completeness:
  - Know the definition of
  - Be able to convert an English proof to a proof tree using natural deduction. You do not need to memorize the natural deduction rules, if asked to give a proof tree, I will provide them
  - However, you should understand introduction rules and elimination rules, and how they correspond to the table of proof techniques from the beginning of the semester
  - Know the definitions of soundness and completeness of . You do not need to know or understand the proofs.
  - Complete axiom systems and Godel's theorem are not in scope.