Princeton University Computer Science Department

Computer Science 341 Discrete Mathematics Moses Charikar

Fall 2003

Information about final exam

• This is a repeat of some information about the final sent out in emails to the class list earlier.
  
• The final was available for pickup since Wednesday, Jan 14. 
  If you haven't picked up the final yet, you can pick it up from 9-5 Saturday, Sunday or Monday. 
  You have to return the exam within 24 hours of the time you pick it up, and no later than 5pm Monday.
  
• Mitra Kelly, Elad or I will be around 9-5 Saturday, Sunday and Monday. Here is our contact information:
  
• Mitra Kelly
  323 CS building
  Tel: 8-4562
  mkelly AT cs.princeton.edu
  
• Moses Charikar
  305 CS building
  Tel: 8-7477
  moses AT cs.princeton.edu
  
• Elad Hazan
  413 CS building
  Tel: 8-1797
  ehazan AT cs.princeton.edu
  
• Try to avoid picking up or dropping off the exam 12-1, since people may be away at lunch. 
  If you do intend to come at this time, send email or call before hand and let Mitra, Elad or me know.
  

• Look at the end of the list of announcements below for last years final and the theoretical computer science cheat sheet, a useful reference (pages 1,2,3,5 and 9 are particularly relevant to the course material).
  

• Additional reference notes on probability: The following course notes from MIT may find useful to read and refer to in addition to the Rosen text. (These cover material that is a superset of what we covered in class). http://theory.lcs.mit.edu/classes/6.042/fall03/handouts/ln10.pdf
  http://theory.lcs.mit.edu/classes/6.042/fall03/handouts/ln12.pdf
  http://theory.lcs.mit.edu/classes/6.042/fall03/handouts/ln13.pdf
  
• 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 may also use the course notes on probability pointed to above. 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.
  

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:

   • In problem 2, assume that the numbers are integers.
   • In problem 4, a player X will be said to have bested player Y if Y can be reached from X in a chain of defeats of length atmost 2, i.e. if X beats A, who beats B, who beats C, then X will be said to have bested A and B, but not C.
   Average grade: 88.17
   Standard Deviation: 12.28
   
   

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

   • In problem 4: a necklace flipped over remains the same and doesn't count as a distinct necklace.
   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 24)  ps, 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