| Date |
Topic |
Reading |
Notes |
Discussion |
| Jan 15 |
Truth tables, propositions, logical equivalences, predicates, quantifiers |
Sections 1.3, 1.4 |
|
|
| Jan 17 |
Parse trees, implications |
Section 1.5 |
|
Week 1 |
| Jan 22 |
Direct Proof, Proof by Cases, Proof by Contradiction |
Sections 2.1, 2.2, 2.5 |
.pdf |
|
| Jan 24 |
Pigeonhole Principle, Proof by Minimum Counterexample, Introduction to Induction |
Sections 2.3, 2.4, 2.5 |
.pdf |
Week 2 |
| Jan 29 |
More Induction |
Chapter 2.3, 2.4 |
.pdf |
|
| Jan 31 |
Even More Induction, Problem Solving Techniques: Small Examples, Recurrence Relations |
Chapter 2 |
.pdf |
Week 3 |
| Feb 5 |
Introduction to Sets, Inclusion/Exclusion Principle |
Chapter 3.1, 3.3 |
.pdf |
|
| Feb 7 |
More Sets, Cartesian Product, Powerset, Partitions, Russell's Paradox |
Chapter 3.2, 3.3 |
.pdf |
Week 4 |
| Feb 12 |
Introduction to functions |
Chapter 4.1, 4.2, 4.3 |
.pdf |
|
| Feb 14 |
MIDTERM 1 - IN CLASS |
|
| Feb 19 |
Onto, one-to-one, and bijective functions; Cardinality of infinite sets |
Chapter 4.3 |
.pdf |
|
| Feb 21 |
More on Infinite Sets, Computable Functions, Posets |
Chapter 4.4 |
.pdf |
Week 5 |
| Feb 26 |
More on Posets, Equivalence Relations |
Chapter 4 |
.pdf |
|
| Feb 28 |
Asymptotic Analysis: big-O, big-omega, theta, little-o, little-theta |
Chapter 4 |
.pdf |
Week 6 |
| Mar 4 |
Intro to Recurrence Relations, Unrolling Recurrences |
Notes on Recurrences |
.pdf |
|
| Mar 6 |
Unrolling Recurrences, Recursion Trees |
Notes on Recurrences |
.pdf |
Week 7 |
| Mar 11 |
More Recursion Trees, Master Theorem |
Notes on Recurrences |
.pdf |
|
| Mar 13 |
Characteristic Equation Method |
Notes from MIT |
.pdf |
Week 8 |
| Mar 25 |
Recurrence Solving Review |
See above |
.pdf |
|
| Mar 27 |
Introduction to Algorithms |
Course notes |
.pdf |
Week 9 |
| Apr 1 |
MIDTERM 2 - IN CLASS |
|
| Apr 3 |
Sorting Algorithms; Introduction to Counting |
Chapter 5.1 |
.pdf |
Week 10 |
| Apr 8 |
Binomial coefficients |
Chapter 5.2, 5.3, 5.4 |
.pdf |
|
| Apr 10 |
More Counting |
Chapter 5.2, 5.3, 5.4 |
.pdf |
Week 11 |
| Apr 15 |
Intro to Graphs, Eulerian circuits, connectivity |
Chapter 7.1, 7.2 |
.pdf |
|
| Apr 17 |
Induction on Graphs, Connectivity, Trees |
Chapter 7.1, 7.2 |
.pdf |
Week 12 |
| Apr 22 |
k-colorable Graphs, Bipartite Graphs, Matchings |
Chapter 7 |
.pdf |
|
| Apr 24 |
Hall's Theorem, Directed Graphs, Tournaments, and Intro to Planar Graphs |
Chapter 7 |
.pdf |
Week 13 |
| Apr 29 |
Planar Graphs |
Chapter 7.3 |
.pdf |
|
| May 5 |
FINAL EXAM: 8:00-11:00 am, room TBD |
|