CPSC 289 Sec 502
Spring 2007
Homework

General Instructions:

1. The numbers refer to the exercises at the end of the listed section in the textbook.

2. Write clearly and legibly. Grading will be based on correctness, clarity, and whether your solution is of the appropriate length.

3. Don't forget to acknowledge all sources of assistance. Unless otherwise instructed, you must write up your homework on your own. Turn in your homework together with this cover sheet.

4. Homework is always due at the beginning of class.

5. You are encouraged to work extra problems: the more you work, the more you will learn. The textbook has a wealth of exercises, and you can check your work with the odd-numbered ones.

[Homework 1] [Homework 2] [Homework 3] [Homework 4] [Homework 5] [Homework 6] [Homework 7] [Homework 8] [Homework 9]

Homework 1. Due Thursday, Feb 1, 2007, 11:10 AM

• Exercises for Section 1.1 (pp. 16-21):
• Ex. 8
• Ex. 10 (a), (c) and (e)
• Ex. 12
• Ex. 18 (a), (c) and (e)
• Ex. 28 (a), (c) and (e)
• Exercises for Section 1.2 (pp. 28-30):
• Ex. 4 (a)
• Ex. 10 (d)
• Ex. 16
• Ex. 46
• Exercises for Section 1.3 (pp. 46-50):
• Ex. 2
• Ex. 6 (a), (c) and (e)
• Ex. 12 (a), (c) and (e)
• Ex. 24 (d)
• Ex. 58
• Exercises for Section 1.4 (pp. 58-62):
• Ex. 8 (a), (b) and (c)
• Ex. 20 (a) and (c)
• Ex. 24 (c)
• Ex. 30 (a), (c) and (e)
• Ex. 42
• Exercises for Section 1.5 (pp. 72-74):
• Ex. 4 (a), (b) and (c)
• Ex. 14 (b)
• Ex. 18
• Ex. 24
• Exercises for Section 1.6 (pp. 85-86):
• Ex. 6
• Ex. 18
• Ex. 26. What kind of proof did you use?
• Exercises for Section 1.7 (pp. 102-104):
• Ex. 4
• Ex. 6
• Ex. 22. Try backward reasoning.
• Ex. 32. Try to adapt a known proof.

Homework 2. Due Tuesday, Feb 13, 2007, 11:10 AM

• Exercises for Section 2.1 (pp. 119-121):
• Ex. 6
• Ex. 8 (c) and (e)
• Ex. 12 (*OPTIONAL*)
• Exercises for Section 2.2 (pp. 130-133):
• Ex. 2 (b) and (d) (*2(b) is OPTIONAL, 2(d) is required*)
• Ex. 12 (*OPTIONAL*)
• Ex. 18 (d)
• Ex. 26 (c)
• Exercises for Section 2.3 (pp. 146-149):
• Ex. 12 (*12(b) and (c) are OPTIONAL; 12(a) and (d) are required*)
• Ex. 16
• Ex. 70 (b)
• Exercises for Section 2.4 (pp. 160-163):
• Ex. 6 (d)
• Ex. 16 (a)
• Ex. 18 (a)
• Ex. 24 (*OPTIONAL*)
• Ex. 32
• Ex. 42

Homework 3. Due Tuesday, Feb 20, 2007, 11:10 AM

• Exercises for Section 3.1 (pp. 177-179):
• Ex. 14
• Ex. 26
• Ex. 38
• Exercises for Section 3.2 (pp. 191-193):
• Ex. 4
• Ex. 8. Justify your answers and be sure to indicate the specific C and k for each part.
• Ex. 10
• Ex. 17. (Just read and understand the solution; nothing to turn in)
• Ex. 18
• Ex. 20
• Ex. 24 (a), (b) and (d)
• Exercises for Section 3.3 (pp. 199-200):
• Ex. 8
• Ex. 28 (b)

Homework 4. Due Tuesday, Mar 6, 2007, 11:10 AM

• Exercises for Section 4.1 (pp. 279-283):
• Ex. 4
• Ex. 6
• Ex. 16
• Ex. 18
• Ex. 20
• Ex. 32
• Ex. 46
• Ex. 48
• Exercise for Section 4.2 (pp. 291-294):
• Ex. 4

Homework 5. Due Tuesday, Mar 20, 2007, 11:10 AM

• Exercises for Section 4.2 (pp. 308-311):
• Ex. 4, (a) and (b)
• Ex. 12. Use induction.
• Ex. 24. This problem refers to polynomials of the form a_0 + a_1*x + a_2*x^2 + ... + a_n*x^n, where n is any nonnegative integer and the a_i's are integers.
• Read solution to Ex. 31 (nothing to turn in)
• Ex. 44
• Ex. 60
• Read solution to Ex. 61 (nothing to turn in)
• Ex. 62
• Exercises for Section 4.4 (pp. 321-322):
• Ex. 8
• Ex. 10
• Ex. 22
• Ex. 28
• Ex. 44
• Read solution to Ex. 49 (nothing to turn in)

Homework 6. Due Tuesday, Mar 27, 2007, 11:10 AM

• Exercises for Section 4.5 (pp. 327-328):
• Ex. 4
• Ex. 6. Read the solution to Ex. 5 to discover the rule of inference to use.
• Exercises for Section 7.3 (pp. 482-484):
• Ex. 22
• Ex. 24
• Ex. 28
• Ex. 34
• Ex. 36

Homework 7. Due Tuesday, Apr 3, 2007, 11:10 AM

• Exercises for Section 5.1 (pp. 344-347):
• Ex. 12
• Ex. 14
• Ex. 24 (a)
• Read solution to Exercise 35 (nothing to turn in)
• Read solution to Exercise 39 (nothing to turn in)
• Ex. 50
• Ex. 58 (don't be put off by the star; it's not hard)
• Exercises for Section 5.2 (pp. 353-354):
• Ex. 10 (read solution to Ex 11 for a hint)
• Ex. 14
• Ex. 26
• Exercises for Section 5.3 (pp. 360-362):
• Ex. 6 (c)
• Ex. 24
• Ex. 26
• Exercises for Section 5.4 (pp. 369-370):
• Ex. 2
• Ex. 4
• Ex. 14
• Ex. 22

Homework 8. Due Tuesday, Apr 17, 2007, 11:10 AM

• Exercises for Section 8.1 (pp. 527-529):
• Ex. 4
• Ex. 6, (a), (c), (f) and (g)
• Ex. 32 (b), (c) and (d)
• Ex. 34 (a), (d) and (g)
• Ex. 56
• Exercises for Section 8.3 (pp. 542-544):
• Ex. 8 for matrix in Ex 4(a), for reflexive, symmetric, antisymmetric and transitive
• Ex. 14 (a), (b), (c) and (d)
• Ex. 22
• Ex. 32 for directed graph in Ex. 27, for reflexive, symmetric, antisymmetric and transitive
• Ex. 36 for union

Homework 9. Due Thursday, Apr 26, 2007, 11:10 AM

• Exercises for Section 8.4 (pp. 553-555):
• Ex. 10
• Ex. 22
• Ex. 26 (c)
• Exercises for Section 8.5 (pp. 562-566):
• Ex. 16
• Ex. 24 (b)
• Exercises for Section 8.6 (pp. 578-581):
• Ex. 6
• Ex. 10
• Ex. 24
• Ex. 32
• Ex. 44 (d)
• Exercises for Section 12.1 (pp. 794-796):
• Ex. 30 (a)
• Exercises for Section 12.3 (pp. 814-817):
• Ex. 26
• Ex. 32
• Exercises for Section 12.4 (pp. 825-827):
• Ex. 6
• Ex. 10