Course Syllabus
Syllabus: Syllabus.pdf Download Syllabus.pdf
Piazza link (use this if you are looking for a group): piazza.com/northwestern/winter2020/comp_sci212 Links to an external site.
Discussion (optional): Wed, Thurs, 5-5:50pm, Tech L251
Instructor Office Hours:
Monday 1-1:50pm (Mudd 3536), Wednesday 3pm-3:50pm (Mudd 3303), Friday, 3pm-3:50pm (Mudd 3532)
TA/Peer Mentor Office Hours: Sunday 4pm-6pm (Tech L221), Monday 12pm-1pm (Mudd 3536), 3pm-4pm (Mudd 3534), Tuesday 4pm-5pm (Mudd 3108), Tuesday 5-6pm (Mudd 3108), Friday 5-6pm (Mudd 3532)
Midterm: February 10, 2020, 4-4:50pm
Final: March 17, 2020, 12-2pm
Handouts: Advice for solving homework problems and studying for exams - Advice.pdf Download Advice.pdf
The following is a tentative list of topics, and related references in the book Leighton, Lehman and Meyer (MIT6_042Notes.pdf Download MIT6_042Notes.pdf ). This table will be updated frequently: do check this portion periodically. Required reading for the next lecture will be mentioned in the previous class and updated here. Please check Canvas for related assignments & quizzes.
| Date | Lecture Topics | Required Reading | Related References |
| January 6 |
Proof Techniques |
LLM Chapter 1.1-1.5.1 | |
| January 8 |
Proof Techniques |
LLM Chapter 1.5.2-1.7 | |
| January 10 |
Contradiction, Induction |
LLM Chapter 1.8, 6.1 | |
| January 13 |
Induction, Strong Induction |
LLM Chapter 6.1, 6.2 | |
| January 15 |
Strong Induction / Invariants |
LLM Chapter 6.2, 6.4 | |
| January 17 |
Set Theory, Relations |
LLM section 4.1 on Sets | LLM Chapter 4 |
| January 22 |
Relations, Asymptotics |
LLM Chapter 4.4, 14.7 | |
| January 24 |
Counting Rules |
LLM Chapters 15.1-15.3 | |
| January 27 |
Permutations / Combinations |
LLM Chapter 15.4-15.5 | |
| January 29 |
Binomial Theorem, Pigeonhole Principle |
LLM Chapter 15.7, 15.10 |
|
| January 31 |
Principle of Inclusion Exclusion, Proof by Words |
LLM Chapter 15.12, 15.13 |
|
| February 3 |
Introduction to Probability |
LLM Chapter 17.4, 17.5 | |
| February 5 |
Conditional Probability, Independence |
LLM Chapter 17.5, 17.6 | |
| February 7 |
Independence, Birthday Paradox, Random Variables |
LLM Chapter 17.6, 18.1 | |
| February 10 | Midterm | ||
| February 12 |
Random Variables, Expected Value |
LLM Chapter 18.2, 18.4 | |
| February 14 |
Linearity of Expectation |
LLM Chapter 18.5 | |
| February 17 |
Markov's inequality |
LLM Chapter 19.1, 19.2 | |
| February 19 |
Chebyshev's Inequality |
LLM Chapter 19.3, 19.4 | |
| February 21 |
Chernoff bounds, Introduction to Graphs Notes: February21.pdf Download February21.pdf Chernoff bound notes: February21-chernoff.pdf Download February21-chernoff.pdf |
LLM Chapter 19.7, 11.1, 11.2, 11.3 | |
| February 24 |
Graph Properties |
LLM Chapter 11.4, 11.8, 11.9 | |
| February 26 |
Trees |
LLM Chapter 11.11 | |
| February 28 |
Minimum spanning trees |
LLM Chapter 11.11 | |
| March 2 |
Coloring, bipartite graphs Notes: March2.pdf Download March2.pdf |
LLM Chapter 11.5,11.7, 11.10 | |
| March 4 |
Matchings, Hall's Theorem Notes: March4.pdf Download March4.pdf |
LLM Chapter 11.5 | |
| March 6 |
Stable Matchings Notes: March6.pdf Download March6.pdf |
LLM Chapter 11.6 | |
| March 9 |
Linear Algebra Notes: March9.pdf Download March9.pdf |
||
| March 11 |
Eigenvalues/Eigenvectors Notes: March11.pdf Download March11.pdf |
||
| March 13 | Cancelled | ||
| March 17 | Final |
Course Summary:
| Date | Details | Due |
|---|---|---|
|
|
||