Computer Science 341
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: firstname.lastname@example.org. 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
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)
1st discussion session: Thursday, Jan 6, 10:30am-12:30pm
2nd discussion session: Monday, Jan 10, 4:00pm-6:00pm
Pizza and ice cream study break: Monday, Jan 10, 6:00pm
We encourage you to come to the study break even if you don't attend the discussion session.
Please, RSVP to Konstantin (<email@example.com>), so we know how much food to order.
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.
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.
Average grade: 26.21. Standard Deviation: 11.34
Average grade: 33.03. Standard Deviation: 9.57
Average grade: 31.94 Standard Deviation: 8.55
Average grade: 28.19. Standard Deviation: 10.25
Average grade: 29.38. Standard Deviation: 9.47
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).
Average grade: 26.59. Standard Deviation: 10.57
Average grade: 29.88. Standard Deviation: 10.82
Average grade: 29.82. Standard Deviation: 11.09
Average grade: 21.64. Standard Deviation: 12.26
Average grade: 22.96. Standard Deviation: 13.93
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 are numbered by week. All section numbers are from Rosen, 5th edition.
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)
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)
5.2 (Probability Theory), 5.3 (Expected Value and Variance)
Additional notes on probability: ps, pdf
5.1 (Recurrence relations)
5.2 (Solving recurrence relations), 5.3 (Divide and conquer
5.4 (Generating functions)
Additional notes on generating functions and exponential generating functions
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
Additional notes on matchings and Hall's theorem: ps, pdf