| Week of: | Contents | Course notes: | tutorial
|
|---|
| Sep 13 | Introduction, mathematical induction | 0, 1.1, 1.2 | preliminaries
|
| Sep 20 | Complete (strong) induction, correctness of iterative programs | 1.3, 1.6 | induction examples (A1 handout)
|
| Sep 27 | Recursive definition of functions and sets, structural induction | 1.4, 1.5 | induction example
|
| Oct 04 | Structural induction, solution of mergesort recurrence relation (powers of 2);
| 2.1, 2.2 | A1 due (A2 handout)
|
| Oct 11 | final analysis of mergesort, asymptotic bound notation (big-Oh, big-Omega, big-Theta), divide-and-conquer algorithms
| 2.2, 2.3.1, handout
| recurrence example
|
| Oct 18 | General form of divide-and-conquer recurrences, examples from 2.4 and/or 2.5
| 2.3, 2.4, 2.5 | A2 due; Old midterm exercises and more
|
| Oct 25 | Propositional logic: propositional formulas, truth tables, tautologies, satisfiable and unsatisfiable formulas,
logical implication and equivalencies, some important laws.
| 3.1,3.2,3.3,3.4,3.5,3.6 | Midterm Test; (A3 handout)
|
| Nov 01 | Propositional logic (cont'd): analysis of 3 proof techniques, DNF and CNF, boolean functions and circuits,
complete sets of connectives. | 3.8 (3.7),3.9,3.10,3.11 | Midterm discussed.
|
| Nov 08 | Predicate logic: introduction, the syntax of predicate logic (first-order languages, predicate formulas,
free variables), semantics of predicate logic (structures, valuations, interpretations, truth value of a formula)
| 4.1,4.2,4.3 | A3 due (A4 handout)
|
| Nov 15 | Some important logical equivalences, deriving new equivalences, PNF, order and scope of quantifiers.
| 4.4,4.5,4.6,4.7,4.8 | -
|
| Nov 22 | Intro to Finite State Automata and regular expressions; languages, operations on languages, regular expressions.
| 5.1,5.2 | A4 due (A5 handout)
|
| Nov 29 | Deterministic FSA; nondeterministics FSA; equivalence between DFSA and NFSA. | 5.3,5.4 | -
|
| Dec 06 | Equivalence between regular languages and FSAs; regular languages; brief discussion
of non-regularity and pumping lemma | 5.5,5.6 (5.7 only an overview)
| A5 due
|