Fall 2010
Schedule and assignments listed below; (Basic course info page here.)
Tentative Lecture Plan#:
| Lecture | Date | Topics Covered | Pages in Textbook | Web Links/ Handouts |
| 1 | Sep 23 | Intro, Propositions, Logical Connectives, Truth tables |
*, 1-15, 21-27 | Math Symbols Logic Symbols Truth Tables for Logic Operators Handout 1 (pdf) |
| 2 | Sep 28 | Equivalences, Predicates and Quantifiers | 21-27, 30-46 | Propositional Calculus Handout 2 (pdf) |
| 3 | Sep 30 | Rules of Inference, Logical forms |
63-70 | Prolog language Common fallacies |
| 4 | Oct 5 | Methods of Proof | 75-85 | Mathzone (more examples)
Handout 3 (pdf) |
| 5 | Oct 7 | More Proofs |
86-102 |
Millenium Prizes Existence Proof: Tic-tac-toe Handout 3 (pdf) |
| 6 | Oct 12 | Sets | 111-130 | Handout 4 (pdf) Slides Lec 6 (pdf) |
| 7 | Oct 14 | Functions |
133-146 |
Handout 5 (pdf) |
| 8 | Oct 19 | Sequences and Summations | 149-158 | Sloane's Online Encyclopedia Handout 6 (pdf) |
| 9 | Oct 21 | Finish Summations and mini-review |
Sec 2.4 | Review probs for midterm Solutions to review probs |
| 10 | Oct 26 | Algorithms, Complexity | Sec 3.1-3.3 |
Handout 7 (pdf) Nature article on CS, Oct 13, 2010 |
| Oct 28 | MIDTERM |
Midterm solutions | ||
| 11 | Nov 2 | Function Growth, Complexity | Sec 3.2-3.3 | Big-Oh notation Handout 8 (pdf) |
| 12 | Nov 4 | Mathematical Induction, Strong induction |
Sec 4.1-4.2 | Induction Why induction is valid Handout 9 (pdf) |
| 13 | Nov 9 | Recursive Definitions, Structural Induction, Recursive Algorithms | Sec 4.3-4.4 | Fibonacci Numbers Handout 10 (pdf) |
| -- | Nov 11 | (Veteran's Day Holiday) | ||
| 14 | Nov 16 | Counting, Combinations, Pigeonhole | Sec 5.1-5.2 | Counting Problems Handout 11 (pdf) |
| 15 | Nov 18 | Permutations, Combinations, Poker, Binomial Coefficients |
Sec 5.3-5.4 |
Travelling Salesman Prob (TSP) Counting Problems Handout 12 (pdf) |
| 16 | Nov 23 | Discrete Probability |
Sec 6.1-6.2 | The Monty Hall Problem The Eudaemonic Pie Handout 13 (pdf) |
| -- | Nov 25 | (Thanksgiving Holiday) | ||
| 17 | Nov 30 |
Conditional Probability; Recurrences (Applications) |
Sec 6.2, 7.1 | Handout 14 (pdf) |
| 18 | Dec 2 | Soliving linear recurrence relations Divide and Conquer Algorithms |
Sec 7.2-7.3 | Master Theorem Strassen algorithm (extra) Handout 15 (pdf) |
| Dec 10 | Final Exam, 8am | |||
| Resources for Internships: (NSF, REU CS opportunities) Microsoft Research |
early Jan through mid-Feb. |
Resources for CS students: |
# may change as we progress into the
quarter; you should check it every week
* material was/maybe used that is not in your book
Watch this space for assignments and solutions: