Princeton University
Computer Science Department

Computer Science 341
Discrete Mathematics

Moses Charikar

Fall 2005

      Directory
General Information    Handouts

 

Announcements

Fianal Exam Solutions pdf, ps


The theoretical computer science cheat sheet is a handy reference for formulae etc.

Pages 1,2,3,5 and 9 are relevant to the course material.

Here are some exams from previous years to help you prepare for the final:

Fall 02  solutions (outline only)
Fall 03  solutions (outline only)
Fall 04

We will organize three study sessions to go over the solutions to these exams (and review any other material you would like):


Wed, Jan 11   2-4pm, CS 302  (discuss fall 02)
Fri, Jan 13      2-4pm, CS 302  (discuss fall 03)
Mon, Jan 16   1-3pm, CS 402  (discuss fall 04)


In addition, we will have a pizza and icecream study break from 12noon-1pm on Mon, Jan 16
just before the study session.


Here are some lecture notes from a similar course at MIT that you may find useful to read in preparing for the final: 
Mathematics for Computer Science  (Warning: this is a 339 page pdf file!)

A lot of the material on probability covered in class was adapted from Chapters 18 through 25 of these notes.

Homework

Homework 0: Send mail to moses AT cs DOT princeton DOT edu with COS 341 in the subject header and the following information:

Your name, year and major.

A picture via a URL, so we can connect names to faces.

Why you are taking the class and what you hope to learn.

Your math background and familiarity with topics relevant to the class.

Homeworks are due at the beginning of class on Wednesdays.

Collaboration Policy:

You may collaborate in groups of at most 3 students. These groups must be disjoint and discussion across groups is not allowed. Collaboration is limited to discussion of ideas only, and you should write up the solutions entirely on your own and list your collaborators.

  1. Homework 1 (due Wed, Sept 28)  ps, pdf   Solutions ps, pdf
    Average grade: 29.57; Standard Deviation: 9.72

  2. Homework 2 (due Wed, Oct 5)  ps, pdf   Solutions ps, pdf
    Average grade: 29.41; Standard Deviation: 11.81
  3. Homework 3 (due Wed, Oct 12)   ps, pdf   Solutions ps, pdf
    Average grade: 26.75; Standard Deviation: 11.87
  4. Homework 4 (due Wed, Oct 19)  ps, pdf   Solutions ps, pdf
    Average grade: 28.15; Standard Deviation: 10.34
  5. Homework 5 (due Fri, Oct 28)  ps, pdf   Solutions ps, pdf
    Average grade:  34.06; Standard Deviation: 8.37
  6. Take-home Midterm (due Wed, Nov 9)  ps, pdf   Solutions ps, pdf
    Average grade:  77.41; Standard Deviation: 26.31
  7. Homework 7 (due Wed, Nov 16)  ps, pdf   Solutions ps, pdf
    Average grade: 33; Standard Deviation: 7.55
  8. Homework 8 (due Wed, Nov 23)  ps, pdf   Solutions ps, pdf
    Average grade: 21.85 ; Standard Deviation: 8.58
  9. Homework 9 (due Fri, Dec 2)  ps, pdf   Solutions ps, pdf
    Average grade: 34 ; Standard Deviation: 7.34
  10. Homework 10 (due Fri, Dec 9)  ps, pdf   Solutions ps, pdf
    Average grade: 24.8 ; Standard Deviation: 10.99
  11. Homework 11 (due Fri, Dec 16)  ps, pdf   Solutions ps, pdf
    Average grade: 31.55 ; Standard Deviation: 7.86

Problem Session handouts

Precept 1: Problems: ps, pdf.   Solutions ps, pdf

Precept 2: Problems: ps, pdf.   Solutions ps, pdf

Precept 3: Problems: ps, pdf.   Solutions ps, pdf

Precept 4: Problems: ps, pdf.   Solutions ps, pdf

Precept 5: Problems: ps, pdf.   Solutions ps, pdf

Precept 6: Problems: ps, pdf.   Solutions ps, pdf

Precept 7: Problems: ps, pdf.   Solutions ps, pdf

Precept 8: Problems: ps, pdf.   Solutions ps, pdf

Precept 9: Problems: ps, pdf.   Solutions ps, pdf

Precept 10: Problems: ps, pdf.   Solutions ps, pdf

Precept 11: Problems: ps, pdf.   Solutions ps, pdf

Readings

Readings are numbered by week. All section numbers are from Rosen, 5th edition. The list will be updated as the semester progresses.

1.5 (esp. Methods of Proving Theorems), 3.1 (Proof strategy),  3.3 (Mathematical Induction), 3.4 (Recursive Definitions and Structural Induction),  4.2 (Pigeonhole Principle).
Background Reading: 1.1 (Logic) , 1.3 (Predicates and Quantifiers).

3.2 (Sequences and Summation), 2.2 (Growth of functions).
Background Reading: 1.6 (Sets), 1.7 (Set Operations), 1.8 (Functions).

2.2 (Growth of functions)

4.1 (Basics of counting), 4.3 (Permutations and Combinations), 4.4 (Binomial Coefficients), 4.5 (Generalized Permutations and Combinations).

6.5 (Inclusion-Exclusion), 6.6 (Applications of Inclusion-Exclusion).

6.1 (Recurrence relations), 6.2 (Solving recurrence relations)

6.2 (Solving recurrence relations), 6.3 (Divide and conquer relations)

6.4 (Generating functions)
Additional notes on generating functions.
A proof of the Akra-Bazzi result.

5.1 (Introduction to Discrete Probability).

5.1 (Introduction to Discrete Probability), 5.2 (Probability Theory), 5.3 (Expected Value and Variance)
Additional notes on probability: ps, pdf

 

 Notes on the probabilistic method and derandomization by conditional probabilities: ps, pdf

8.1 (Introduction to graphs), 8.2 (Graph terminology), 8.3 (Representing graphs), 8.4 (Connectivity)

8.5 (Euler and Hamilton paths),  8.8 (graph coloring)

8.7 (Planar graphs)

9.1 (Introduction to trees),  9.2 (Applications of trees)

Additional reading: 9.4 (Spanning Trees), 9.5 (Minimum Spanning Trees)
Additional reading: 8.6 (Shortest Path Problems)

Seidel's paper on all-pairs-shortest paths using matrix multiplication

Additional notes on matchings and Hall's theorem: ps, pdf