CS 205: Homework
 
Problem Sets:
  1. 1. For your recitation sessions during the week of  September 14:Problem 10 on p. 17. Problem 18 on p. 18. Problem 10 on p. 28. Problem 12 on p. 28. For each implication, write out a formal derivation using logical equivalences, as in Example 8 on p. 27.
  2. 2. For your recitation sessions during the week of  September 21: Problem 10 on p. 47. Problem 20 on p. 47. Problem 32 on p. 48. Problem 60 on p. 50.
  3. 3. For your recitation sessions during the week of  September 28:Problem 10 on p. 59. Problem 30 on p. 61. Problem 16 on p. 73. Problem 34 on p. 74.
  4. 4. For your recitation sessions during the week of  October 5:  Problem 18 on p. 85. In Part (b), see if you can find a proof by contradiction that is not simply a rewriting of the proof by contraposition in Part (a). Problem 26 on p. 85. Problem 8 on p. 102. Problem 28 on p. 103. Try a proof by cases.
  5. 5. For your recitation sessions during the week of  October 12: Problem 22 on p. 120. Problem 30 on p. 120. Problem 18 on p. 131. Problem 30 on p. 131. Note: There may be a typo in your copy of the text. Part (c) of Problem 30 should read: 
 A ∪ C = B ∪ C and A ∩ C = B ∩ C
  6. 6. For your recitation sessions during the week of  October 19:Problem 20 on p. 209. Problem 24 on p. 209. Problem 8 on p. 217. Problem 18 on p. 218.
  7. 7. For your recitation sessions during the week of  October 26:Problem 4 on p. 279. Problem 10 on p. 280. Problem 14 on p. 280. Problem 16 on p. 280.
  8. 8. For your recitation sessions during the week of  November 2:Problem 46 on p. 281. Problem 70 on p. 282. Problem 4 on p. 291. Problem 14 on p. 292.
  9. 9. For your recitation sessions during the week of  November 9:Problem 12 on p. 308. Problem 26 on p. 309. Problem 32 on p. 309. Problem 36 on p. 309.
  10. 10.  For your recitation sessions during the week of  November 16:  Here is a challenging problem that encompasses all the main ideas in Sections 4.3, 4.4 and 4.5 of the text.  Here is a sample solution.  
  11. 11.  For your recitation sessions during the week of  November 30: Problem 6 on p. 527. Problem 32 on p. 528. Problem 34 on p. 529. Caution: In your lecture notes, we denoted the composition of R and S by R ○ S, not S ○ R as in Rosen’s Definition 6.
  12. 12.  For your recitation sessions during the week of  December 7:Problem 10 on p. 554. Problem 20 on p. 554. Problem 16 on p. 563. Problem 40 on p. 564.