Math 19/CS 19: Discrete Math for Computer Science

There are two kinds of problems listed. The non-mandatory "warm-up" is problems you can try first if you're uncomfortable with the material or just want more practice; their answers are in the back of the book (as are all the odd-numbered problems' answers), and they will be assumed material on exams. Then there are the problems for handing in, which will be graded for credit.

Feel free to discuss the problems with each other and with me, but your write-up must be your own. Please do not hand in warm-up problems, but you are welcome to discuss them with me.

Assignment 1, due Monday, September 27

Warm-up: p. 16-21 #5, 7, 13, 23, 27, 47; p. 28-30 #9, 11, 15, 25, 31, 41, 45, 59; p. 46-50 #5, 7, 11, 13, 35, 43, 45, 51; p. 58-62 #1, 9, 19, 23, 25, 31, 33, 35

To hand in: p. 16-21 #24, 48; p. 28-30 #44; p. 46-50 #50; p. 58-62 #22, 34.
For #44 you must show disjunction, implication, and bi-implication are each equivalent to some expression that uses only conjunction and negation. For #50, compare #45 and 51 in the same section.

Assignment 2, due Friday, October 1

Warm-up: p. 119-121 #3, 5, 7, 9, 15, 17, 27, 29, 31; p. 130-133 #3, 7, 29, 31, 49, 51

To hand in: p. 119-121 #8, 20, 30; p. 130-133 #10, 14, 24

Assignment 3, due Friday, October 8

Warm-up: p. 146-149 #9, 29; p. 527-529 #3, 7, 13, 33, 39, 47; p. 562-566 #3, 7, 15, 35, 37, 41, 45, 55

To hand in: p. 146-149 #68; p. 527-529 #8; p. 562-566 #56 (parts a and b only)
Problem X: Let F and G both be functions from A to B. What conditions on F and G allow their union and intersection to be functions from A to B? Why will those fail to be functions otherwise?

Assignment 4, due Monday, October 11

Warm-up: p. 160-163 #13, 15, 17; p. 191-193 #1, 7, 15, 17, 19, 21

To hand in: p. 160-163 #18; p. 191-193 #24, 44

Review Suggestions for Midterm 1, Friday, October 15

Chapter 1: Review p. 105 #1-4, 6, 7, 10a, 13a
Supplemental Exercises p. 106 #1-7, 15-17, 24-26

Chapter 2: Review p. 164 #1, 2, 3a, 4, 5 (without symmetric difference), 6, 9, 11, 13
Supplemental Exercises p. 164 #1-8, 10, 11a, 13, 19-21

Chapter 3: Review p. 258 #3, 4, 13
Supplemental Exercises p. 259 #13-16, 19

Chapter 8: Review p. 582 #1-3, 10-13
Supplemental Exercises p. 583 #1-4, 7-9, 20

Assignment 5, due Friday, October 22

Warm-up: p. 279-283 #3, 5, 7, 13, 15, 17, 31, 33, 47, 49; p. 308-311 #13, 15, 49

To hand in: p. 279-283 #14, 32; p. 308-311 #14

Assignment 6, due Friday, October 29

Warm-up: p. 344-347 #11, 15, 17, 25, 27, 29, 31, 33, 39, 41, 43; p. 353-354 #3, 5, 9; p. 360-362 #3, 9, 11, 13, 17, 19, 21, 23, 27, 31, 33, 35; p. 369-370 #19, 21, 31; p. 504-505 #1, 3, 11, 13; p. 512-513 #1

To hand in: p. 344-347 #38, 44; p. 360-362 #22, 30, 36, 40

For #44, interpret "5" as "exactly 5".

Assignment 7, due Monday, November 8

Hand in Wednesday, November 3 if you want it back in class on the 8th; if you hand it in the 8th it will be ready to pick up on Tuesday the 9th by noon.

Warm-up: p. 398-400 #5, 9, 13, 15, 17, 21, 33, 35, 37; p. 414-416 #5, 7, 9, 11, 17, 19, 23, 25, 27, 31, 35; p. 424-425 #3, 5, 7, 9, 15; p. 439-441 #3, 5, 7, 11, 19, 23, 25, 29, 33(b)

Note: the way the Monty Hall problem is set up in 6.3 #15 is difficult to parse; it is much better explained earlier in the book, on p. 398.

To hand in: p. 414-416 #8, 26; p. 424-425 #12, 16; p. 439-441 #16, 30; Problem Y

Problem Y: A couple decides they will have children until they have at least one boy and one girl, though they will stop if they reach four children even if they are all boys or all girls. Assuming the sexes of different children are independent and boys and girls have equal probability, answer the following.
a) What's the probability they have at least three girls?
b) What's the probability they have at least three girls given their first child was a girl?
c) What's the probability their first child was a girl given they have at least three girls?
d) What's their expected number of children?

Review Suggestions for Midterm 2, Wednesday, November 10

Chapter 4: Review p. 329 #1, 2, 7
Supplemental Exercises p. 329 #1-14, 20, 21, 27, 43

Chapter 5: Review p. 387 #1-6, 8, 10, 13, 17
Supplemental Exercises p. 388 #1-8, 10-15, 20-24, 27, 28, 30, 33-36

Note: Part d in #1 and 2 and parts c-f in #21 require section 5.5, so skip them.

Chapter 6: Review p. 442 #1-6, 8, 9, 13-15
Supplemental Exercises p. 443 #1-10, 14-18, 20-22, 24, 26, 28, 31

Assignment 8, due Friday, November 19

Warm-up: p. 595-597 #11, 13, 19, 27; p. 608-611 #5, 21, 25, 27, 31, 33, 35, 37, 43, 45, 47, 49, 51, 53, 55; p. 618-621 #5, 7, 9, 11, 13, 17, 19, 23, 25, 29, 31, 47, 49

To hand in: p. 595-597 #12; p. 608-611 #18, 26; p. 618-621 #28, 32 (a-d only)

Assignment 9, due Wednesday, December 1

Hand in Monday, November 29 (or before Thanksgiving) if you want it back in class on the 1st; if you hand it in the 1st it will be ready to pick up on Friday the 3rd by noon.

Warm-up: p. 629-633 #1, 3, 5, 17, 23, 25, 27, 49, 53; p. 655-657 #1; p. 693-695 #3, 5, 9, 17, 19, 25, 27, 29, 39, 47; p. 734-737 #1, 7

To hand in: p. 629-633 #26; p. 693-695 #14, 28

Review Suggestions for the Final Exam, Monday, December 6

Miscellaneous: p. 332 #48; p. 389 #25; p. 543 #5, 7, 9, 11 (the matrix for a relation is the adjacency matrix for its digraph representation); p. 584 #14(c)

Chapter 9: Review p. 676 #3-8, 11, 12(a)
Supplemental Exercises p. 677 #6, 7, 9-11, 14-18, 32, 33, 46, 49, 50(a,b), 51

Chapter 10: Review p. 744 #1, 2, 4-6
Supplemental Exercises p. 745 #1, 3, 5, 8, 10, 11 36

Supplemental exercises from all through the material. Answers.
Note: problem 11(d) should read "...three or four of a kind in the manner of part (b) in both..."

Back to the main 19 page.

Last modified December 6, 2010