Discrete Mathematics
Logic, proof techniques, sets, counting, relations and graphs.
Textbook: Discrete Mathematics and its Applications, Kenneth H. Rosen, McGraw-Hill Publishing Company.
- Week 1propositional logic, predicates and quantifiers
- Propositional logic, predicates and quantifiersConnectives, truth tables, laws of logical equivalence, and translating and negating statements with ∀/∃. The first midterm question almost always comes from here.
- Week 2nested quantifiers and introduction to proofs
- Nested quantifiers and rules of inferenceThe difference between ∀x∃y and ∃y∀x, truth values of nested quantifiers, their negation, and showing with rules that an argument is valid.
- Introduction to proof methods: direct, contrapositive, contradictionDirect proof, contraposition, contradiction, proof by cases and counterexamples, using the definitions of even/odd, divisibility and rational numbers. The template proof questions of the midterm come from here.
- Week 3proof techniques and mathematical induction
- Mathematical induction and strong inductionThe induction skeleton for sum formulas, divisibility and inequalities; strong induction for stamp problems and recursively defined sequences. An almost certain 20-point question on the midterm.
- Week 4sets and functions
- Sets: operations, power sets and proving set equalitySubsets, power sets, Cartesian products, set operations, and proving set equality with a membership table or double inclusion.
- Functions: one-to-one, onto, inverse, composition, floor and ceilingThe template for proving a function is one-to-one and onto, inverse functions, composition, and floor/ceiling. A 1-1/onto proof and a floor/ceiling computation are almost certain on the midterm.
- Week 5sequences and sums, cardinality of sets, intoduction to algorithms
- Sequences, summations, cardinality and an introduction to algorithmsArithmetic/geometric sequences, Σ summation formulas and double sums, countable and uncountable sets (Cantor), maximum in pseudocode, linear/binary search, bubble sort and greedy algorithms.
- Week 6growth of functions and complexity of algorithms
- Growth of functions and algorithm complexityDefinitions of Big-O, Big-Omega and Big-Theta, finding witnesses, the 'is not O' proof, growth ordering and loop counting. The last topic of the midterm.
- Week 7divisibility, modular arithmetic, primes
- Divisibility, modular arithmetic and primesa | b, the division algorithm (div and mod), congruence, prime factorization, GCD/LCM and the Euclidean algorithm. The foundation of the cryptography week, and a final exam topic.
- Week 8cryptography
- Cryptography: Caesar, affine cipher and RSAShift and affine ciphers, modular inverses with the extended Euclidean algorithm, fast modular exponentiation, and RSA key generation, encryption and decryption with small primes. A final exam topic.
- Week 9introduction to counting, the pigeonhole principle
- Introduction to counting and the pigeonhole principleProduct and sum rules, inclusion-exclusion, the pigeonhole principle (including the generalized form), permutations P(n,r) and combinations C(n,r). A final exam topic, not on this semester's midterm.
- Week 10advanced counting
- Advanced counting: selections with repetition, the binomial theorem and recurrence relationsPermutations and combinations with repetition (stars and bars), words with repeated letters, the binomial theorem and Pascal's identity, the next permutation in lexicographic order, and building recurrence relations from problems. A final exam topic.
- Week 11Solving linear recurrences, generating functions
- Linear recurrences, generating functions and inclusion-exclusionSolving recurrences with the characteristic equation, adding a particular solution, divide-and-conquer recurrences, counting with generating functions, and inclusion-exclusion. A full question on the final comes from here.
- Week 12relations
- Relations: properties, equivalence relations and partial ordersChecking whether a relation is reflexive, symmetric, antisymmetric or transitive, taking composites and closures, and drawing equivalence classes and Hasse diagrams. Classic question types for the final.
- Week 13Introduction to graphs, graph isomorphisms
- Introduction to graphs and graph isomorphismGraph terminology, degree and the handshaking theorem, special graphs (K_n, C_n, W_n, Q_n, K_{m,n}), bipartite graphs, adjacency matrices, and showing whether two graphs are isomorphic.
- Week 14"Connectivity, Euler and Hamilton paths,
- Connectivity, Euler and Hamilton pathsDefinitions of paths and circuits, components, cut vertices and bridges, counting paths with matrix powers, the degree condition for Euler circuits/paths, Dirac's and Ore's theorems for Hamilton circuits, and a brief look at Dijkstra's algorithm.