Princeton University
Computer Science Department

Computer Science 341
Discrete Mathematics

Moses Charikar

Fall 2004


      Directory
General Information    Handouts

 

Announcements

If you haven't subscribed to the course mailing list yet, please do so ASAP. We will be sending important information on the course list. The mailing list archives are available here.

The course final is available for pickup beginning 9am on Wed, Jan 12. You can pick it up 9-5pm and must return it within 24 hours. The final must be returned no later than 5pm on Monday, Jan 17. This is a university mandated deadline. On Wed, Thu and Fri, the final can be picked up from Mitra Kelly, in 323 CS building, tel. 8-4562, email: mkelly@cs.princeton.edu. Avoid the lunch hour 12noon-1pm, since Mitra is likely to be away then.

In addition to the homework and precept solutions as well as supplementary notes posted on this page, you might find the theoretical computer science cheat sheet (ps,pdf) a handy reference. Pages 1,2,3,5 and 9 are relevant to the course material.

Resources you may use during your final: No collaboration is permitted on the final. You may refer to your own notes, textbooks (including those other than the course texts), and all materials posted on the course web site. You are not supposed to search for information online. The main objective of these rules is to prevent you from finding solutions to the questions on the final, either deliberately or accidentally.

We suggest that you use the finals from previous years to practice for the final. The solutions will be discussed in study sessions we will organize.

Fall '02 final (ps,pdf)  to be discussed in first study session (Thu, Jan 6)
Fall '03 final (ps,pdf)  to be discussed in second study session (Mon, Jan 10) 

 


Homework

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

  1. Your name, year and major.

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

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

  4. 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 22)  ps, pdf   Solutions ps, pdf
    Average grade: 26.21. Standard Deviation: 11.34

  2. Homework 2 (due Wed, Sept 29)  ps, pdf   Solutions ps, pdf
    Average grade: 33.03. Standard Deviation: 9.57

  3. Homework 3 (due Wed, Oct 6)  ps, pdf   Solutions ps, pdf
    Average grade: 31.94 Standard Deviation: 8.55

  4. Homework 4 (due Wed, Oct 13)  ps, pdf   Solutions ps, pdf
    Average grade: 28.19. Standard Deviation: 10.25

  5. Homework 5 (due Fri, Oct 22, 5pm)  ps, pdf   Solutions ps, pdf
    Average grade: 29.38. Standard Deviation: 9.47

  6. Homework 6 (due Wed, Nov 3)  ps, pdf   Solutions ps, pdf
    Average grade: 28.09. Standard Deviation: 9.15

    Correction. There is a typo in problem 3 part C. The last sentence should read:
    Show that with probability at least 95%, T is in the range (k + 1) · (1 ± 0.1).

  7. Homework 7 (due Wed, Nov 10)  ps, pdf   Solutions ps, pdf
    Average grade: 26.59. Standard Deviation: 10.57

  8. Homework 8 (due Wed, Nov 17)  ps, pdf   Solutions ps, pdf
    Average grade: 29.88. Standard Deviation: 10.82

  9. Homework 9 (due Wed, Nov 24)  ps, pdf   Solutions ps, pdf
    Average grade: 29.82. Standard Deviation: 11.09

  10. Homework 10 (due Th, Dec 2)  ps, pdf. Solutions ps, pdf
    Average grade: 21.64. Standard Deviation: 12.26

  11. Homework 11 (due Fri, Dec 10)  ps, pdf. Solutions ps, pdf
    Average grade: 22.96. Standard Deviation: 13.93


Problem Session handouts

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

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

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

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

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

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

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

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

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

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

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


Readings

Readings are numbered by week. All section numbers are from Rosen, 5th edition. 

  1. 1.4 (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.2 (Growth of functions)

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

  3. 4.4 (Binomial Coefficients), 4.5 (Generalized Permutations and Combinations), 6.5 (Inclusion-Exclusion), 6.6 (Applications of Inclusion-Exclusion).

    5.1 (Introduction to Discrete Probability), 5.2 (Probability Theory)

  4. 5.2 (Probability Theory), 5.3 (Expected Value and Variance)

    Additional notes on probability: ps, pdf


  5. 5.1 (Recurrence relations)

  6. 5.2 (Solving recurrence relations), 5.3 (Divide and conquer relations)

  7. 5.4 (Generating functions)

    Additional notes on generating functions and exponential generating functions

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

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

  10. 8.7 (Planar graphs)

  11. 9.1 (Introduction to trees),  9.2 (Applications of trees)
    Additional notes on matchings and Hall's theorem: ps, pdf