Course Syllabus
Syllabus: Syllabus.pdf
Piazza link (use this if you are looking for a group): piazza.com/northwestern/spring2020/comp_sci212
Lecture: Mon, Wed, Fri, 3-3:50pm Zoom 617-633-773, password 780439
Discussion (optional): Wed, Thurs, 5-5:50pm, Zoom 613-342-554, password 561722
Instructor Office Hours:
Monday, Wednesday, Friday, 2-2:50pm Zoom 432-334-339
TA/Peer Mentor Office Hours:
Friday 11am-12pm, 4-6pm, Sunday, 4-6pm, 8-9pm, Monday 1-2pm, 4-5pm, 8-9pm, Tuesday 2-3pm, 5-6pm, 8-9pm Zoom 127-863-390
Midterm: May 11, 2020
Final: June 11, 2020
Handouts: Advice for solving homework problems and studying for exams - advice.pdf
The following is a tentative list of topics, and related references in the book Leighton, Lehman and Meyer (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 |
| April 6 |
Proof Techniques Recording: Notes: April6.pdf |
LLM Chapter 1.1-1.5.1 | |
| April 8 |
Recording: Notes: April8.pdf |
LLM Chapter 1.5, 1.7 | |
| April 10 |
Iff, Contradiction, Induction Recording: Notes: April10.pdf |
LLM Chapter 1,5, 1.8, 6.1 | |
| April 13 |
Induction, Strong Induction Recording: Notes: April13.pdf |
LLM Chapter 6.1, 6.2 | |
| April 15 |
Strong Induction / Invariants Recording: Notes: April15.pdf Homework 1, out |
LLM Chapter 6.2, 6.4 | |
| April 17 |
Set Theory, Relations Recording: Notes: April17.pdf |
LLM section 4.1 on Sets | LLM Chapter 4 |
| April 20 |
Relations, Asymptotics Recording: Notes: April20.pdf |
LLM Chapter 4.4, 14.7 | |
| April 22 |
Counting Rules Recording: Notes: April22.pdf Homework 2, out |
LLM Chapters 15.1-15.3 | |
| April 24 |
Permutations / Combinations Recording: Notes: April24.pdf |
LLM Chapter 15.4-15.5 | |
| April 27 |
Binomial Theorem, Principle of Inclusion-Exclusion Recording: Notes: April27.pdf |
LLM Chapter 15.7, 15.12 |
|
| April 29 |
Pigeonhole Principle, More bijection rule Recording: Notes: April29.pdf Homework 3, out |
LLM Chapter 15.10, 15.13 |
|
| May 1 |
Introduction to Probability, Conditional Probability Recording: Notes: May1.pdf |
LLM Chapter 17.4, 17.5 | |
| May 4 |
Conditional Probability, Independence Recording: Notes: May4.pdf |
LLM Chapter 17.5, 17.6 | |
| May 6 |
Birthday Paradox, Random Variables Recording: Notes: May6.pdf |
LLM Chapter 17.6, 18.1 | |
| May 8 |
Expected Value, Linearity of Expectation Recording: Notes: May8.pdf |
LLM Chapter 18.2, 18.4 | |
| May 11 |
Midterm |
||
| May 13 |
Linearity of Expectation Recording: Notes: May13.pdf Homework 4, out |
LLM Chapter 18.5 | |
| May 15 |
Markov's inequality Recording: Notes: May15.pdf |
LLM Chapter 19.1, 19.2 | |
| May 18 |
Chebyshev's Inequality, Chernoff bounds Recording: Notes: May18.pdf, Chernoff.pdf |
LLM Chapter 19.3, 19.4, 19.7 | |
| May 20 |
Introduction to Graphs Recording: Notes: May20.pdf Homework 5, out |
LLM Chapter 11.1, 11.2, 11.3 | |
| May 22 |
Graph Properties Recording: Notes: May22.pdf |
LLM Chapter 11.4, 11.8, 11.9 | |
| May 27 |
Trees Recording: Notes: May27.pdf Homework 6, out |
LLM Chapter 11.11 | |
| May 29 |
Minimum spanning trees Recording: Notes: May29.pdf |
LLM Chapter 11.11 | |
| June 1 |
Coloring, bipartite graphs Recording: Notes: June1.pdf |
LLM Chapter 11.5,11.7, 11.10 | |
| June 3 |
Matchings Recording: Notes: June3.pdf |
LLM Chapter 11.5 | |
| June 5 |
Hall's theorem Recording: Notes: June5.pdf |
LLM Chapter 11.6 | |
| June 11 | Final |
Course Summary:
| Date | Details | Due |
|---|---|---|