Course Syllabus
Syllabus: syllabus.pdf
Piazza link (use this if you are looking for a group): piazza.com/northwestern/spring2021/compsci212
Lecture: Mon, Wed, Fri, 3-3:50pm, Zoom: 913 9350 0095
Live Lecture Notes: https://1drv.ms/u/s!AoIsMgFixI-dhxHQcirkH2P2CL-8?e=0usDBb
Discussion (optional): Thurs 5-6pm Zoom: 922 1176 4234, Fri 10-11am Zoom:
983 4377 2515
Instructor Office Hours: Mon, Wed 2-2:50pm, Fri 11-11:50am, Zoom: 959 7543 0602
TA/Peer Mentor Office Hours: Friday 1-3pm, 4-6pm, Sunday 1-3pm, Monday 10am-12pm, 1-2pm, 6-8pm, Tuesday 10am-12pm, 1-3pm, 6-9pm
Zoom: 959 7543 0602
Midterm: May 3 3-3:50pm (makeup May 4, 8-8:50am)
Final: June 10, 9-11am
Handouts: Advice for solving homework problems and studying for exams - advice.pdf
A list of things that do not have to be proved - Axioms.pdf
A strange determinant, by Tim Gowers - https://www.youtube.com/watch?v=byjhpzEoXFs
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.
| Date | Lecture Topics | Required Reading | Related References |
|
March 30 |
Propositions, Direct Proofs Recording: Notes: March30.pdf |
LLM Chapter 1.1-1.5.1 | |
| March 31 |
Direct Proofs, Cases, Contrapositive Recording: Notes: March31.pdf |
LLM Chapter 1.5, 1.7 | |
| April 2 |
Iff, Contradiction, Induction Recording: Notes: April2.pdf |
LLM Chapter 1,5, 1.8, 6.1 | |
| April 5 |
Induction, Strong Induction Recording:
Notes: April5.pdf
|
LLM Chapter 6.1, 6.2 | |
| April 7 |
Strong Induction / Invariants Homework 1, out Recording: Notes: April7.pdf |
LLM Chapter 6.2, 6.4 | |
| April 9 |
Set Theory, Relations Recording: Notes: April9.pdf
|
LLM section 4.1 on Sets | LLM Chapter 4 |
| April 12 |
Relations, Asymptotics Recording: Notes: April12.pdf
|
LLM Chapter 4.4, 14.7 | |
| April 14 |
Counting Rules Homework 2, out Recording: Notes: April14.pdf |
LLM Chapters 15.1-15.3 | |
| April 16 |
Counting Rules Ctd. Recording: Notes: April16.pdf |
LLM Chapter 15.4-15.5 | |
| April 19 |
Binomial Theorem, Principle of Inclusion-Exclusion Recording: Notes: April19.pdf
|
LLM Chapter 15.7, 15.12 |
|
| April 21 |
Pigeonhole Principle, More bijection rule Homework 3, out Recording: Notes: April21.pdf |
LLM Chapter 15.10, 15.13 |
|
| April 23 |
Introduction to Probability, Conditional Probability Recording: Notes: April23.pdf |
LLM Chapter 17.4, 17.5 | |
| April 26 |
Conditional Probability, Independence Recording: Notes: April26.pdf
|
LLM Chapter 17.5, 17.6 | |
| April 28 |
Birthday Paradox, Random Variables Recording: Notes: April28.pdf |
LLM Chapter 17.6, 18.1 | |
| April 30 |
Expected Value, Linearity of Expectation, Binomial Distribution Recording: Notes: April30-1.pdf |
LLM Chapter 18.2, 18.4 | |
| May 3 |
Midterm |
||
| May 5 |
Conditional Expectation, Expected Value of Product Homework 4, out Recording: Notes: May5.pdf |
LLM Chapter 18.5 | |
| May 7 |
Markov's inequality Recording: Notes: May7.pdf |
LLM Chapter 19.1, 19.2 | |
| May 10 |
Chebyshev's Inequality Recording: Notes: May10.pdf
|
LLM Chapter 19.3, 19.4 | |
| May 12 |
Chernoff bounds, Introduction to Graphs Homework 5, out Recording: Notes: May12.pdf |
LLM Chapter 19.7, 11.1, 11.3 | |
| May 14 |
Graph Properties Recording: Notes: May14.pdf
|
LLM Chapter 11.4, 11.8, 11.9 | |
| May 17 |
Trees Recording: Notes: May17.pdf |
LLM Chapter 11.11 | |
| May 19 |
Minimum spanning trees Homework 6, out Recording: Notes: May19.pdf |
LLM Chapter 11.11 | |
| May 21 |
Colorings, Bipartite Graphs Recording: Notes: May21.pdf |
LLM Chapter 11.5,11.7, 11.10 | |
| May 24 |
Matchings Recording: Notes: May24.pdf |
LLM Chapter 11.5 | |
| May 26 |
Stable Matchings Homework 7, out Recording: Notes: May26.pdf |
LLM Chapter 11.10 | |
| May 28 |
Linear Algebra Recording: Notes: May28.pdf |
||
| June 2 |
Spectral Graph Theory, Boolean Hypercube Recording: Notes: June2.pdf |
||
| June 4 |
Boolean Hypercube Recording: Notes: June4.pdf |
||
| June 10 | Final |
Course Summary:
| Date | Details | Due |
|---|---|---|