Course Syllabus

Syllabus: Syllabus.pdf

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

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

 

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
January 6

Proof Techniques

Notes: January6.pdf

LLM Chapter 1.1-1.5.1
January 8

Proof Techniques

Notes: January8.pdf

LLM Chapter 1.5.2-1.7
January 10

Contradiction, Induction

Notes: January10.pdf

LLM Chapter 1.8, 6.1
January 13

Induction, Strong Induction

Notes: January13.pdf

LLM Chapter 6.1, 6.2
January 15

Strong Induction / Invariants

Notes: January15.pdf

LLM Chapter 6.2, 6.4
January 17

Set Theory, Relations

Notes: January17.pdf

LLM section 4.1 on Sets LLM Chapter 4
January 22

Relations, Asymptotics

Notes:  January22.pdf

LLM Chapter 4.4, 14.7
January 24

Counting Rules

Notes: January24.pdf

LLM Chapters 15.1-15.3
January 27

Permutations / Combinations

Notes: January27.pdf

LLM Chapter 15.4-15.5
January 29

Binomial Theorem, Pigeonhole Principle

Notes: January29.pdf

 LLM Chapter 15.7, 15.10

January 31

Principle of Inclusion Exclusion, Proof by Words

Notes: January31.pdf

January31-pbw.pdf

LLM Chapter 15.12, 15.13

February 3

Introduction to Probability

Notes: February3.pdf

LLM Chapter 17.4, 17.5
February 5

Conditional Probability, Independence

Notes: February5.pdf

LLM Chapter 17.5, 17.6
February 7

Independence, Birthday Paradox, Random Variables

Notes: February7.pdf

LLM Chapter  17.6, 18.1
February 10 Midterm
February 12

Random Variables, Expected Value

Notes: February12.pdf

LLM Chapter 18.2, 18.4
February 14

Linearity of Expectation

Notes: February14.pdf

LLM Chapter 18.5
February 17

Markov's inequality

Notes: February17.pdf

LLM Chapter 19.1, 19.2
February 19

Chebyshev's Inequality

Notes: February19.pdf

LLM Chapter 19.3, 19.4
February 21

Chernoff bounds, Introduction to Graphs

Notes: February21.pdf

Chernoff bound notes: February21-chernoff.pdf

LLM Chapter 19.7, 11.1, 11.2, 11.3
February 24

Graph Properties

Notes: February24.pdf

LLM Chapter 11.4, 11.8, 11.9
February 26

Trees

Notes: February26.pdf

LLM Chapter 11.11
February 28

Minimum spanning trees

Notes: February28.pdf

LLM Chapter 11.11
March 2

Coloring, bipartite graphs

Notes: March2.pdf

LLM Chapter 11.5,11.7, 11.10
March 4

Matchings, Hall's Theorem

Notes: March4.pdf

LLM Chapter 11.5
March 6

Stable Matchings

Notes: March6.pdf

LLM Chapter 11.6
March 9

Linear Algebra

Notes: March9.pdf

March 11

Eigenvalues/Eigenvectors

Notes: March11.pdf

March 13 Cancelled
March 17 Final
Tentative List of Topics & Readings

 

Course Summary:

Date Details Due