Princeton University |
Computer Science 341 |
|
A few students asked for suggestions for practice problems. Here are some suggestions from the two texts. Most of these have solutions/hints at the back of the book. The list consists of section number followed by problem numbers. These are only practice problems and should be used to supplement, not replace, other preparation for the final.
1.2: 7
1.3: 6, 8, 12, 13
2.1: 6
2.2: 3(b), 5, 7
2.3: 4, 7, 9, 16(a)(b), 23
2.4: 3, 5
2.5: 2, 5, 12
2.7: 2
2.8: 2, 4, 7, 11 (harder)
3.1: 5, 7
3.2: 4, 5, 11
3.3: 8, 10, 16
3.4: 7, 10
3.6: 8, 9
3.7: 2
4.1: 6, 8(a)
4.2: 6
4.3: 1
4.4: 5, 8, 10(a)
4.5: 5
5.1: 3
5.2: 7(a)
5.3: 5, 7(a), 8(a)
5.4: 4, 10
7.1: 2
7.2: 1
9.1: 3
9.2: 4, 10
9.3: 6
10.1: 6
10.2: 5, 8, 17, 10 (harder)
10.3: 1, 5, 7, 9, 13
10.4: 3
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 2 (due Wed, Oct 2) ps,
pdf solutions (ps,
pdf)
Clarification for problem 2: non-decreasing means each digit is
greater than or equal to the preceding digit (to the left of it), e.g.
1234445 has its digits in non-decreasing order, but 12435 and 32221 do
not qualify.
Homework 4 (due Wed, Oct 16) ps,
pdf solutions (ps,
pdf)
Some of you might have an incorrect answer to problem 4,
due to a subtle flaw in the technique you used to solve the problem. We
advise you to check your answer for small values of n and verify that the
formula you obtained produces the right values.
Homework 5 (due 4:30pm, Fri, Oct 25) ps,
pdf
solutions (ps,
pdf)
Homework 8 (due Wed, Nov 20) ps,
pdf
solutions (ps,
pdf)
There is no collaboration permitted on this homework. Note that
homeworks will be collected at the beginning of class.
Homework 10 (due at noon on Fri, Dec 6) ps,
pdf
solutions (ps,
pdf)
There is no collaboration permitted on this homework.
Homework 11 (due at noon on Fri, Dec 13)
ps, pdf
solutions (ps,
pdf)
Mon, Nov 18 problems (ps, pdf)
solutions (ps, pdf)
Copies of the solution set with drawings available in the TAs' offices.
handouts have 4 slides per page
Readings refer to sections from Matousek and Nesetril
Fri, Sept 13 (slides, handouts)
Readings: Chapter 1
Additional reference: Rosen, 3.2
Wed, Sept 18 (slides, handouts)
This material does not appear in Matousek and Nesetril.
Additional reference: Rosen, 1.1, 1.2, 1.3, 3.1
Mon, Sept 23 (slides,
handouts)
Much of the material for this lecture was taken from Steven
Rudich's slides for his course
"Great
Theoretical Ideas for Computer Science" at CMU.
Readings: 2.1, 2.2, 2.3
Mon, Sept 30 (slides, handouts)
Readings: 2.7, 2.8, 10.1, 10.2
Additional reference: Rosen, 5.5, 5.6, 5.4
Wed, Oct 2 (slides, handouts)
Readings: 10.2
Additional reference: Rosen, 5.4
Mon, Oct 7 (slides, handouts)
Readings: 10.2 (especially problem 14),
Additional reference: Rosen, 5.4, 5.1, 5.2
Wed, Oct 9 (slides, handouts)
Readings: 10.2 (especially problem 14), 10.3, 10.4
Additional reference: Rosen, 5.4, 5.1, 5.2
Mon, Oct 14 (see below for notes)
Readings: 10.3, 10.4
Additional reference: Rosen, 5.2 (more comprehensive coverage
than Matousek)
Wed, Oct 16 (notes for lectures 9,10 ps,
pdf)
Readings: 10.3, 10.4
Additional reference: Rosen, 5.2 (more comprehensive coverage
than Matousek)
Mon, Oct 21
Readings: 3.1-3.3
Additional reference:
Wed, Oct 23
Readings: 3.1-3.5
Additional reference:
Mon, Nov 4
Readings: 3.4-3.7
Additional reference:
Wed, Nov 6
Readings: 3.7-4.2
Additional reference:
Mon, Nov 11
Readings: 4.3-4.5
Additional reference:
Wed, Nov 13
Readings: 5.1-5.2
Additional reference:
Mon, Nov 18 (slides handouts)
Readings: 5.3
Additional reference:
Wed, Nov 20
Readings: 5.4
Additional reference:
Mon, Nov 25
Readings: 7.1-7.4, 6.3, Notes on matchings and Hall's theorem (ps,
pdf).
Additional reference:
Wed, Nov 27
Readings: Introductory material not in Matousek. Notes on
Probability (ps, pdf).
Additional reference: Rosen 4.4, 4.5
Introductory notes
on probability from Mathematics
for Computation course at MIT.
Mon, Dec 2
Readings: See notes for previous lecture.
Additional reference:
Rosen 4.5
Wed, Dec 4
Readings: 9.3. Additional notes (ps, pdf)
updated Thu 12/12
Additional reference:
Rosen 4.5
Notes
on random variables and expectation from Mathematics
for Computation course at MIT.
Mon, Dec 9
Readings: 9.3,9.1,9.4, also see notes for previous lecture.
Additional reference:
Rosen 4.5
Notes
on deviation from the mean from Mathematics
for Computation course at MIT.
Wed, Dec 11
Readings: 2.4,2.5,2.6
Additional reference: