Winter 2008
Tentative Lecture Plan#:
| Lecture | Date | Topics Covered | Pages in Textbook | Web Links |
| 1 | Jan 8 | Intro, Example Problems, Propositions, Logical Connectives |
*, 1-15 | Math Symbols Truth Tables for Logic Operators |
| 2 | Jan 10 | Truth Tables, Equivalences, Rules of Inference | 20-26, 63-70 | Propositional Calculus |
| 3 | Jan 15 | More Rules of Inference, Proofs |
63-70, 75-85 | |
| 4 | Jan 17 | Methods of Proof | 75-85, 86-102 | Checkout Mathzone for more examples |
| 5 | Jan 22 | More Proofs, Predicates and Quantifiers |
86-102, *, 30-46 |
Existence Proof: Tic-tac-toe |
| 6 | Jan 24 | Sets | 111-130 | |
| 7 | Jan 29 | Functions |
133-146 |
|
| 8 | Jan 31 | Function Growth | 180-190 | Big-Oh notation |
| 9 | Feb 5 | Algorithms, Complexity |
167-177, 193-200 | |
| 10 | Feb 7 | Finish Complexity, Sequences and Summations | 149-158 | Sloane's Online Encyclopedia |
| Feb 12 | MIDTERM |
|||
| 11 | Feb 14 | Mathematical Induction, Strong induction | 263-291 | Induction |
| 12 | Feb 19 | Recursive Definitions, Structural Induction |
294-307 | Fibonacci Numbers |
| 13 | Feb 21 | Recursive Algorithms, Integers and Division | 311-317, 200-217 | |
| 14 | Feb 26 | Number Theory and Algorithms |
219-229 | Division Algorithm Euclidean Algorithm |
| 15 | Feb 28 | Counting, Permutations, Combinations | 335-344, *, 355-360 | Counting Problems |
| 16 | Mar 4 | Poker, Pigeonhole, Binomial Coefficients |
*, 347-353, 363-368 |
|
| 17 | Mar 6 | Recurrences: Solutions and Applications | 449-461 | |
| 18 | Mar 11 | Solving Recurrences |
461-471 |
|
| 19 | Mar 13 | Divide and Conquer Algorithms | 474-483 | Master Theorem Strassen algorithm(extra) |
| Mar 18 | Final review session | 3:30-5pm in Olson 106 | ||
| Mar 22 | Final Exam |
# may change as we progress into the
quarter; you should check it every week
* material was/maybe used that is not in your book