Course Syllabus

Jump to Today

Syllabus: syllabus.pdf

Piazza link (use this if you are looking for a group): piazza.com/northwestern/fall2020/compsci212

Lecture: Mon, Wed, Fri, 4:10-5pm, Zoom: 993 1071 1270, password: 961615

Discussion (optional): Thurs 8am Zoom: 953 1055 3776, password: 162293

Thurs 6pm, Zoom: 973 7157 1672 password: 162293

Instructor Office Hours: Mon, Wed 3-3:50pm, Fri 2-2:50pm, Zoom: 944 9747 3794

TA/Peer Mentor Office Hours:  Monday 10am-12pm, 6-8pm, 9-10pm, Tuesday 3-4pm, 6-8pm, 9-10pm, Friday 10:30-11:30am, 12:50-1:50pm, 3-4pm, 5-8pm, Sunday 2-3pm, 7-9pm, 

Zoom: 944 9747 3794

 

Midterm:  October 19, 4:10-5pm (second slot October 20, 8am-8:50am)

Final:  December 7, 7-9pm (second slot December 8, 8-10am)

 

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

 

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

September 16

Propositions, Direct Proofs

Recording:

Notes: September16.pdf

 LLM Chapter 1.1-1.5.1
September 18

Direct Proofs, Cases, Contrapositive

Recording: 

Notes: September18.pdf

 LLM Chapter 1.5, 1.7
September 21

Iff, Contradiction, Induction

Recording: 

Notes: September21.pdf

 LLM Chapter 1,5, 1.8, 6.1
September 23

Induction, Strong Induction

Homework 1, out

Recording: 

Notes: September23.pdf

 LLM Chapter 6.1, 6.2
September 25

Strong Induction / Invariants

Recording:

Notes: September25.pdf

 LLM Chapter 6.2, 6.4
September 28

Set Theory, Relations

Recording: 

Notes: September28.pdf

 LLM section 4.1 on Sets LLM Chapter 4
September 30

Relations, Asymptotics

Homework 2, out

Recording: 

Notes: September30.pdf

 LLM Chapter 4.4,  14.7
October 2

Counting Rules

Recording:

Notes: October2.pdf

 LLM Chapters 15.1-15.3
October 5

Counting Rules Ctd.

Recording:

Notes: October5.pdf

 LLM Chapter 15.4-15.5
October 7

Binomial Theorem, Principle of Inclusion-Exclusion

Homework 3, out

Recording: 

Notes: October7.pdf

 LLM Chapter 15.7, 15.12
October 9

Pigeonhole Principle, More bijection rule

Recording:

Notes: October9.pdf

LLM Chapter 15.10, 15.13
October 12

Introduction to Probability, Conditional Probability

Recording: 

Notes: October12.pdf

 LLM Chapter 17.4, 17.5
October 14

Conditional Probability, Independence

Recording: 

Notes: October14.pdf

 LLM Chapter 17.5, 17.6
October 16

Birthday Paradox, Random Variables

Recording:

Notes: October16.pdf

 LLM Chapter  17.6, 18.1
October 19

Midterm
October 21

Expected Value, Linearity of Expectation

Homework 4, out

Recording: 

Notes: October21.pdf

 LLM Chapter 18.2, 18.4
October 23

Conditional Expectation, Binomial Distribution, Expected Value of Product

Recording:

Notes: October23.pdf

 LLM Chapter 18.5
October 26

Markov's inequality

Recording: 

Notes: October26.pdf

 LLM Chapter 19.1, 19.2
October 28

Chebyshev's Inequality

Homework 5, out

Recording: 

Notes: October28.pdf

 LLM Chapter 19.3, 19.4
October 30

Chernoff bounds, Introduction to Graphs

Recording: 

Notes: October30.pdf

 LLM Chapter 19.7, 11.1, 11.3
November 2

Graph Properties

Recording: 

Notes: November2.pdf

 LLM Chapter 11.4, 11.8, 11.9
November 4

Trees

Homework 6, out

Recording: 

Notes: November4.pdf

 LLM Chapter 11.11
November 6

Minimum spanning trees

Recording: 

Notes: November6.pdf

 LLM Chapter 11.11
November 9

Colorings

Recording:

Notes: November9.pdf

 LLM Chapter 11.5,11.7, 11.10
November 11

Bipartite graphs, Matchings

Homework 7, out

Recording: 

Notes: November11.pdf		 LLM Chapter 11.5
November 13

Stable Matchings

Recording: 

Notes: November13.pdf

 LLM Chapter 11.10
November 16

Linear Algebra

Recording: 

Notes: November16.pdf
November 18

Spectral Graph Theory

Homework 8, out

Recording: 

Notes: November18.pdf
November 20

Boolean Hypercube

Recording: 

Notes: November20.pdf
November 23

Sensitivity Theorem

Recording: 

Notes: November23.pdf
November 25 No class
November 30

Query Complexity, Sensitivity

Recording:

Notes: November30.pdf
December 7 Final

Course Summary:

Date Details Due