Princeton University

Computer Science
341


Directory
General Information Handouts
The theoretical computer science cheat sheet is a handy reference for formulae etc.
Pages 1,2,3,5 and 9 are relevant to the course
material.
Fall 03 solutions
(outline only)
Fall 04
We will organize three study sessions to go over the solutions to these
exams (and review any other material you would like):
Wed, Jan 11 24pm, CS 302 (discuss fall 02)
Fri, Jan 13 24pm, CS 302 (discuss
fall 03)
Mon, Jan 16 13pm, CS 402 (discuss fall 04)
In addition, we will have a pizza and icecream study break from
12noon1pm on Mon, Jan 16
just before the study session.
Here are some lecture notes from a similar course at MIT that you may
find useful to read in preparing for the final:
Mathematics
for Computer Science (Warning: this is a 339 page pdf file!)
Homework 0: Send mail to moses AT
cs DOT
princeton DOT edu with
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.
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
1.5 (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
3.2 (Sequences and Summation), 2.2 (Growth of functions).
Background
2.2
(Growth of functions)
4.1 (Basics of counting), 4.3 (Permutations and Combinations), 4.4
(Binomial
Coefficients), 4.5 (Generalized Permutations and Combinations).
6.5
(InclusionExclusion), 6.6
(Applications of InclusionExclusion).
6.1 (Recurrence relations), 6.2 (Solving recurrence relations)
6.2 (Solving recurrence relations), 6.3 (Divide and conquer relations)
6.4 (Generating
functions)
Additional notes on generating
functions.
A proof
of the AkraBazzi result.
5.1 (Introduction to Discrete Probability).
5.1 (Introduction
to Discrete
Probability), 5.2 (Probability Theory), 5.3 (Expected Value and
Variance)
Additional notes on probability: ps, pdf
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 reading: 9.4 (Spanning Trees), 9.5 (Minimum Spanning Trees)
Additional reading: 8.6 (Shortest Path Problems)
Seidel's paper on
allpairsshortest paths using matrix multiplication
Additional notes on matchings and Hall's theorem: ps,
pdf