Princeton University
Computer Science Department

Computer Science 341
Discrete Mathematics

Moses Charikar

Fall 2003


      Directory
General Information    Handouts

Information about final exam

Statistics for final exam:
Average grade: 55.4
Standard Deviation: 25.96


Announcements

  1. Homework 1 has been posted. 

  2. Homework 2 has been posted. 

  3. Homework 3 and Precept 3 have been posted. 

  4. Homework 4 and Precept 4 have been posted. 

  5. Reference notes on probability and random variables added (see readings).

  6. Homework 5 and Precept 5 have been posted. 

  7. Homework 5 deadline extended to 5:00pm, Friday Oct 24.

  8. Homework 6 has been posted. 

  9. Precept 6 has been posted. 

  10. Precept solutions 3,4,5,6 have been posted. 

  11. HW solutions 3,4 have been posted 

  12. Homework 7 and Precept 7 have been posted. 

  13. Homework 5 solution has been posted. 

  14. Homework 6 solution has been posted. 

  15. Homework 8 and precept 8 have been posted. 

  16. Precept 8 solution has been posted. 
  17. Additional notes on generating functions have been added (see readings)
  18. Homework 9 and precept 9 have been posted. 

  19. Homework 10 has been posted. 

  20. Solutions for homeworks 7,8 have been posted. 

  21. Solutions for precept 9 have been posted. 

  22. Precept 10 has been posted. 

  23. Precept 11, solutions to HW 9,10 and Precept 10 have been posted. 

  24. Precept 11 solution has been posted. 

  25. HW 10 solution has been posted. 

  26. HW 11 solution has been posted. 

  27. Last year's final is available here for your reference (ps, pdf)

  28. Theoretical computer science cheat sheet (ps, pdf)

  29. Exam statistics are available at top of the page. 


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 24)  ps, pdf   Solutions: ps, pdf.
    Clarifications:

    Average grade: 88.17
    Standard Deviation: 12.28


  2. Homework 2 (due Wed, Oct 1)  ps, pdf   Solutions: ps, pdf.
    Clarification:

    Average grade: 83.94
    Standard Deviation: 13.39


  3. Homework 3 (due Wed, OcT 8)  ps, pdf   Solutions: ps, pdf.
    Average grade: 85.07
    Standard Deviation: 16.73


  4. Homework 4 (due Wed, Oct 15)  ps, pdf   Solutions: ps, pdf.
    Average grade: 59.37
    Standard Deviation: 22.47


  5. Homework 5 (due Fri, Oct 24ps, pdf  (Deadline extended to 5:00pm, Friday)
    Collaboration policy for this homework: you can collaborate only on problems 1 and 2. You must solve problems 3 and 4 on your own. 
    Solutions: ps, pdf.
    Average grade: 68.54
    Standard Deviation: 23.47


  6. Homework 6 (due Wed, Nov 5)  ps, pdf  ( corrections posted 10/27/03)
    Collaboration policy for this homework: you can collaborate only on problems 3 and 4. You must solve problems 1 and 2 on your own. 
    Solutions: ps, pdf.
    Average grade: 67.21
    Standard Deviation: 25.92


  7. Homework 7 (due Wed, Nov 12)  ps, pdf 
    Collaboration policy for this homework: you can collaborate only on problems 3 and 4. You must solve problems 1 and 2 on your own. 
    Solutions: ps, pdf.
    Average grade: 73.88
    Standard Deviation: 22.07


  8. Homework 8 (due Wed, Nov 19)  ps, pdf 
    Collaboration policy for this homework: you can collaborate only on problems 3 and 4. You must solve problems 1 and 2 on your own. 
    Solutions: ps, pdf.
    Average grade: 77.37
    Standard Deviation: 27.91


  9. Homework 9 (due Wed, Nov 26)  ps, pdf 
    Collaboration policy for this homework: you can collaborate only on problems 3 and 4. You must solve problems 1 and 2 on your own. 
    Clarification: In problem 4, you can consider all the persons with the $1 bills to be indistinguishable, as are all the people with the $2 bills, if it helps to simplify the combinatorics.
    Solutions: ps, pdf.
    Average grade: 73.2
    Standard Deviation: 18.34


  10. Homework 10 (due Thursday, Dec 4)  ps, pdf 
    Collaboration policy for this homework: you can collaborate only on problems 2,3 and 4. You must solve problem 1 on your own. Note that the collaboration policy is different this time from the last few homeworks.
    Clarification: In problem 1, the graph is simple (you can assume this always unless otherwise stated), and you can assume k>=2
    Solutions: ps, pdf.
    Average grade: 69.03
    Standard Deviation: 27.55

    Thanks to Jon Beyer and Randy Carnavale for a clever solution to problem 3!

  11. Homework 11 (due Fri, Nov 12)  ps, pdf 
    Collaboration policy for this homework: you can collaborate only on problems 3 and 4. You must solve problems 1 and 2 on your own. 
    Solutions: ps, pdf.
    Average grade: 78.14
    Standard Deviation: 19.86



Problem Session handouts

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

  2. Precept 2: Problems: ps, pdf     Solutions: ps, pdf.
    Correction: The solutions distributed in the precept had a mistake in problem 1. The correct solution is put up above.

  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).
    Background Reading: 1.1 (Logic) , 1.3 (Predicates and Quantifiers),

    4.2 (Pigeonhole Principle), 3.3 (Mathematical Induction), 3.4 (Recursive Definitions and Structural Induction).
    Background Reading: 1.6 (Sets), 1.7 (Set Operations), 1.8 (Functions), 3.2 (Sequences and Summation).

  2. 2.2 (Growth of functions), 4.1 (Basics of counting).

    4.3 (Permutations and Combinations), 4.4 (Binomial Coefficients).

  3. 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)
    Reference notes on probability: ps, pdf

  4. 5.3 (Expected Value and Variance)
    Reference notes on random variables: ps, pdf

  5. 5.3 (Expected Value and Variance)
    Also see notes on random variables above.

  6. 6.1 (Recurrence Relations), 6.2 (Solving  Recurrence Relations).

  7. 6.2 (Solving Recurrence Relations), 6.3 (Divide and Conquer Algorithms and Recurrence Relations)

  8. 6.4 (Generating Functions)
    Reference notes on generating functions: pdf

  9. 6.4 (Generating Functions),  8.1, 8.2, 8.3 (Graphs)
    Reference notes on exponential generating functions: pdf

  10. 8.3 (Isomorphism), 8.4 (Connectivity), 8.5 (Euler and Hamilton paths), 8.6 (Shortest paths)

  11. 8.7 (Planar graphs), 8.8 (Graph coloring)
    Additional notes on matchings: ps, pdf