CSCE 222 Lecture 35

« previous | May 3, 2011 | next »

Final Exam Review

1 Logic

• Propositional
• Predicate
• Logical Equivalences (e.g. a → b = ¬a → ¬b)
• Tautologies
• Proof techniques (modus ponens, modus tollens, etc.)

2 Sets

• Notations: $\bigcap _{i=1}^{\infty }A_{i}$
• Set theory
• Functions: surjective (function maps to every object in codomain), injective (unique mapping), bijective)
• Sequences and Summations

3 Asymptotic Analysis

• Big-O, Big-Ω, Big-Θ
• Proving inequalities
• Limits
• Complexity for algorithms
• Number Theory: GCD, primes, congruences, Chinese Remainder Theorem

4 Induction and Recursion

• Proof by mathematical induction, strong induction

5 Counting

• Basics: Summation rule, multiplication rule
• Pigeonhole principle
• Permutations and Combinations

7 Advanced Counting

• Recurrence relations

8 Relations

• Properties
• Equivalence relations

12 Finite State Automata

• Grammars
• Formal Languages
• Turing Machines