Relevant textbook chapters: Ch. 0-4, 5.1-7, 5.9-11, 6.1-6, 6.9-11, 7

Lecture Summary
===============
Week 1 (Jan 8-9): Introduction to induction
   - principle of weak induction
   - example: sequence of numbers is decreasing
Week 2 (Jan 15-19): More induction
   - 12^n - 1 is divisible by 11
   - n^2 <= 2^n
   - postage using 4 and 7 cent stamps
Week 3 (Jan 22-26): Strong induction
   - intro to the principle of complete induction
   - max num of nodes in a ternary tree of height h
   - weak induction implies complete induction
   - a non-empty, full binary tree has an odd number of nodes
   - Pascal's triangle
Week 4 (Jan 29-Feb 2): Wrapping up induction
   - complete induction implies strong induction
   - finding closed forms
   - recursively defined sets
   - counting binary strings with no adjacent zeroes
Week 5 (Feb 5-9): Program correctness
   - well ordering principle, on quotients and remainders
   - introduction to program correctness, again on quotients and remainders
Week 6 (Feb 12-16): More program correctness
   - correctness of binary search
Week 7 (Feb 26-Mar 2): And still more program correctness
   - binary multiplication
   - recursive binary search
Week 8 (Mar 5-9): Recursive program correctness
   - correctness of mergesort
   - running time of mergesort
Week 9 (Mar 12-16): Propositional logic
   - connectives
   - truth tables
Week 10 (Mar 19-23): More propositional logic
   - normal forms (CNF and DNF)
   - logical equivalences 
   - classification of formulas: tautology, contradiction, satisfiable
   - complete sets of connectives
Week 11 (Mar 26-30): Predicate logic
   - first-order language, free/bound variables
   - structures, interpretations
   - logical equivalences
   - Prenex Normal Form
Week 12 (Apr 2-6): Formal languages
   - formal languages
   - regular expressions
   - proving equivalence of languages
   - FSAs (deterministic and non-deterministic)
Week 13 (Apr 9-13): Regular (and non-regular) languages
   - nFSAs <-> regEx
   - nFSAs <-> dFSAs
   - common operations on languages
   - pumping lemma
   - some stuff about the exam

Tutorial Summary
================
Week 1:
   - review
      - logic operators
      - proof techniques
   - variations on code fragment from lecture
Week 2:
   - sum_{i=1}^{n} (1/root(i)) <= 2 root(n) - 1
Week 3:
   - Fibonacci sequence
   - for all pos. natural numbers n < m, 
        \sum_{k=1}^{m} 1/k - \sum_{k=1}^{n} 1/k >= (m-n)/m
Week 4:
   - solution to A1, question 6
   - defining sets by induction
Week 5:
   - correctness of gcd algorithm
Week 6:
   - open session for midterm review
Week 7:
   - correctness of iterative and recursive algorithms for computing b^p
Week 8:
   - solution to A3, question 3
   - propositional logic examples
Week 9:
   - prove by induction on n that if P_1, ..., P_n, Q are propositional
     formulas for n >= 2, then P_1 \/ P_2 \/ ... \/ P_n -> Q is logically
     equivalent to !Q -> !P_1 /\ !P_2 /\ ... /\ !P_n
   - examples of building predicate formulas
Week 10:
   - example of producing Prenex Normal Form for a formula
   - show that L(1*0(0+1)*) = L((0+1)*01*)
   - ch. 7, exercise 4
   - produce regEx for 
      i) the set of strings that contain 010
      ii) the set of strings that don't contain 010
      iii) the set of all strings with an even number of 0s, odd number of 1s
      iv) the set of all strings that contain a substring of length at most
          3 that has at least two 1s