CPSC 202: Mathematical Tools for Computer Science

Assignments

[HW1] | [HW2] | [HW3] | [HW4] | [HW5] | [HW6] | [HW7] | [HW8] | [HW9] | [HW10]

Notes
All assignments are due in class on the day specified. They will be posted on this page at least one week before the due date to allow ample time for completion and to seek instructor/TA help on any difficult problems.
Each HW assignment is worth 5% of the overall course grade.

HW1
Due in class Thursday, Sept 17, 2009
Reading: Some of you are probably already familiar with Sections 1.1 through 1.5 of Rosen. Skim these sections and read carefully whichever parts of them are not already familiar to you.

Written Assignment (from Rosen):
Section 1.2, #58 (1 point)
Section 1.3, #42 (1 point)
Section 1.4, #48 (2 points)
Section 1.5, #24 (1 point)

Note: Problem 48 from Section 1.4 is worth 2 points instead of 1 because it is a "starred exercise."

HW2
Due in class Thursday, Sept 24, 2009

Section 2.1, #20 AND Justify your answer (1 point)
Section 2.2, #18 (1 point)
Section 2.3, #16 (1 point)
Section 2.4, #48 (2 points)

Note that the last problem (a starred exercise) is worth 2 points.

HW3
Due in class Thursday, October 1, 2009

Reading assignment:
Skim all of Chapter 3, much of which will be familiar to many of you. Read carefully the portions of Chapter 3 with which you are not familiar.

Written assignment:
Section 1.4 #50 (1 point)
Section 2.4 #12 (1 point)
Section 2.4 #22 (1 point)
Section 3.7 #26 (.5 point)
Section 3.7 #56 (.5 point)
Section 3.8 #24 (.5 point)
Section 3.8 #26 (.5 point)

Based on your estimates of how much time you spent on HW1, neither HW1 nor HW2 was long enough by the standard of weekly assignments in 200-level CPSC courses. Therefore, HWs 3 through 10 will be longer.

Note, however, that some of the problems on each HW assignment will be "review problems," i.e., they will deal with material that has been covered in earlier HW assignments rather than with new material. This opportunity to review some old material each week should make preparing for exams less time consuming.

HW4
Due in class Thursday, October 8, 2009

Read pp. 158-160 of Rosen on "Cardinality"
Section 2.4 #40 (0.5 point)
Section 2.4 #42 (0.5 point) (Hint: See exercise #77 in Section 2.3; you may just use the fact stated in that exercise and don't have to provide a proof of it.)

Section 3.7 #30 (NOT REQUIRED. If you have already done it, you may turn it in for up to 1 point of extra credit.)

Section 3.8 #12 (0.5 point)
Section 3.8 #22 (0.5 point) (Remember that we did #17b in class last week.)

The following four exercises are about proof by induction; those worth a full point are, as usual, the starred exercises. Numbers 30, 32, and 12 are straightforward applications of induction and the definitions of Harmonic numbers, divisibility, and Fibonacci numbers, respectively. Number 14 requires only induction and the definition of Fibonacci numbers, but it is harder, because it requires more algebraic manipulation than the other three; this one may take you considerably more time than the other three.

Section 4.1 #30 (1 point)
Section 4.1 #32 (0.5 point)
Section 4.3 #12 (0.5 point)
Section 4.3 #14 (1 point)

HW5
Due in class Thursday, October 22, 2009
Read Section 5.2 of Rosen

In Section 5.1, do exercises 24, 32, 34, and 38.
In Section 5.2, do exercises 4, 6, 12, and 32.

Exercises 12 and 32 in Section 5.2 are worth 1 point each. The rest of the exercises are worth 1/2 point each.

HW6
Due in class Thursday, October 29, 2009
Section 5.4
Exercise 24 (1/2 point)
Exercise 32 (1 point. Hint: One key step involves Pascal's identity.)

Section 6.1
Exercise 10 (1/2 point. Note that the problem assumes that all five-card hands are equally likely.)
Exercise 38 (1/2 point. Note that the problem assumes that all three-coin-toss sequences are equally likely.)

Section 6.2
Exercise 10 (1 point)
Exercise 14 (1/2 point. Note that Bonferroni's Inequality is given in Exercise 13. You may assume that this inequality holds; that is, you do not have to provide a solution to Exercise 13.)
Exercise 20 (1 point. Be sure to read the instructions just above Exercise 18. The people's birthdays are chosen independently and uniformly from the set of 366 possibilities.)

HW7
Due in class November 5, 2009

Section 6.2
Exercise 34 (1/2 point)

Section 6.3
Exercise 6 (1/2 point)
Exercise 18 (1/2 point. Hint: See Example 3 in Section 6.3.)

Section 6.4
Exercise 8 (1/2 point)
Exercise 16 (1/2 point)
Exercise 32 (1 point)
Exercise 40 (1/2 point. Note that Cov(X,Y) is defined just before Exercise 38.)

Section 7.2
Exercise 4 (1 point)

HW8
Due in class Thursday, November 12, 2009

Section 7.2
Exercise 8 (1/2 point)
Exercise 12 (1/2 point)

Section 7.3
Exercise 10 (1/2 point)
Exercise 14 (1/2 point)
Exercise 20 (1 point)

Section 7.4
Exercise 6 (1 point)
Exercise 8 (1/2 point)
Exercise 10 (1/2 point)

Extra Credit Problems (1/2 point each)
Exercises 52 and 54 in Section 7.4 (Note that the term "partition" is defined immediately before exercise 51.)

HW9
Due in class Thursday, November 19, 2009

Section 9.4
Exercise 26 (1 point)

Section 9.5
Exercise 10 (1/2 point)
Exercise 26 (1/2 point)
Exercise 28 (1/2 point)

Section 9.6
Exercise 18 Justify your answer. (1/2 point)
Exercise 22 (1 point: Note that Floyd's algorithm is given on page 657.)
Exercise 24 (1 point)

Extra Credit:
For 1 point, read Section 9.3 and solve Exercise 52. Note that the term "self-complementary" is defined right before Exercise 50.

HW10
Due in class Tuesday, December 1, 2009
Section 10.1
Exercise 14 (1 point)
Exercise 16 (1/2 point)
Exercise 44 (1/2 point)

Section 10.2
Exercise 6 (1/2 point)
Exercise 8 (1 point. Hint: The answer to Exercise 7 is "2 weighings." You may assume that you have an algorithm that solves the problem in Exercise 7 and uses 2 weighings.)
Exercise 36 (1/2 point)
Exercise 38 (1/2 point)
Exercise 40 (1/2 point. Hint: Apply the result in Exercise 39.)

Extra Credit: For one point, read Section 9.7 and do Exercise 18.