Princeton University |
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: 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)
1st discussion session: Thursday, Jan 6, 10:30am-12:30pm
(room 301)
2nd discussion session: Monday, Jan 10, 4:00pm-6:00pm
(room 301)
Pizza and ice cream study break: Monday, Jan 10, 6:00pm
(room 402)
We encourage you to come to the study break even if you don't attend the discussion session.
Please, RSVP to Konstantin (<kmakaryc@cs.princeton.edu>), 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.
Homework 1 (due Wed, Sept 22) ps,
pdf
Solutions
ps,
pdf
Average grade: 26.21. Standard Deviation: 11.34
Homework 2 (due Wed, Sept 29) ps,
pdf
Solutions
ps,
pdf
Average grade: 33.03. Standard Deviation: 9.57
Homework 3 (due Wed, Oct 6) ps,
pdf
Solutions
ps,
pdf
Average grade: 31.94 Standard Deviation: 8.55
Homework 4 (due Wed, Oct 13) ps,
pdf
Solutions
ps,
pdf
Average grade: 28.19. Standard Deviation: 10.25
Homework 5 (due Fri, Oct 22, 5pm) ps, pdf
Solutions
ps,
pdf
Average grade: 29.38. Standard Deviation: 9.47
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).
Homework 7 (due Wed, Nov 10) ps, pdf
Solutions
ps,
pdf
Average grade: 26.59. Standard Deviation: 10.57
Homework 8 (due Wed, Nov 17) ps, pdf
Solutions
ps,
pdf
Average grade: 29.88. Standard Deviation: 10.82
Homework 9 (due Wed, Nov 24) ps, pdf
Solutions
ps,
pdf
Average grade: 29.82. Standard Deviation: 11.09
Homework 10 (due Th, Dec 2) ps, pdf.
Solutions
ps,
pdf
Average grade: 21.64. Standard Deviation: 12.26
Homework 11 (due Fri, Dec 10) ps, pdf.
Solutions
ps,
pdf
Average grade: 22.96. Standard Deviation: 13.93
Readings are numbered by week. All section numbers are from Rosen, 5th edition.
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 (Growth of functions)
4.1 (Basics of counting), 4.3 (Permutations and Combinations), 4.4 (Binomial
Coefficients)
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)
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
relations)
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
trees)
Additional notes on matchings and Hall's theorem: ps,
pdf