CMSC 203, Section 0401
Discrete Structures

Problem Set 1 - Due Tuesday 9/14

Topics: Predicate logic, (Ch. 1.1-1.2).
NOTE: You must complete this assignment using LaTeX.

Problem #1: Section 1.1, exercise 8 (c, e)
Problem #2: Section 1.1, exercise 12 (d, e)
Problem #3: Section 1.1, exercise 22 (a, c)
Problem #4: Section 1.1, exercise 30
Problem #5: Section 1.2, exercises 8 (c) and 10 (d)
Problem #6: Section 1.2, exercise 28

Problem Set 2 - Due Tuesday 9/21

Topics: Predicates, Quantifiers, and Proof Techniques (Ch. 1.3-1.5).

Problem #1: Section 1.3, exercise 22 (e)
Problem #2: Section 1.3, exercise 30 (d, e)
Problem #3: Section 1.3, exercise 42
Problem #4: Section 1.4, exercise 10 (e, i)
Problem #5: Section 1.4, exercises 30 (d)
Problem #6: Section 1.4, exercise 48 (b)
Problem #7: Section 1.5, exercise 22 (a)
Problem #8: Section 1.5, exercise 32

Problem Set 3 - Due Tuesday 9/28

Topics: Sets, Functions, Algorithms (Ch. 1.6-1.8, 2.1-2.3).

Problem #1: Section 1.6, exercise 4
Problem #2: Section 1.6, exercise 12
Problem #3: Section 1.7, exercise 10
Problem #4: Section 1.7, exercise 22 (a,b)
Problem #5: Section 1.7, exercise 36
Problem #6: Section 1.8, exercise 16 (a, b, c, d)
Problem #7: Section 1.8, exercise 28
Problem #8: Section 1.8, exercise 34 (a, b, c)
Problem #9: Section 2.1, exercise 20 (Note: Give Pseudocode and a narrative)
Problem #10: Section 2.1, exercise 48 (Note: show your work clearly)

Problem Set 4 - Due Tuesday 10/5

Topics: Algorithms, Number Theory, Matrices (Ch. 2.2-2.7).

Problem #1: Section 2.2, exercise 19 (a, b, c)
Problem #2: Section 2.3, exercise 4
Problem #3: Section 2.3, exercise 12 (a, b, c)
Problem #4: Section 2.4, exercise 16
Problem #5: Section 2.4, exercise 22 (we did this in class)
Problem #6: Section 2.4, exercise 32 and prove that ab = gcd(a,b) lcm(a,b)
Problem #7: Section 2.5, exercise 8 (a, b, c) and convert each to base 3
Problem #8: Section 2.5, exercise 22 (b, d, f) (show each step)
Problem #9: Section 2.6, exercise 2 (b, e, h) and exercise 12
Problem #10: Section 2.7, exercise 10 (a, c, e) and exercise 24 (a, b)

Problem Set 5 - Due Thursday 10/21

Topics: Sequences, Summations, Induction, Recursion, Correctness (Ch. 3.2-3.6).

Problem #1: Section 3.2, exercise 8 and exercise 10 (a and e)
Problem #2: Section 3.2, exercise 16 (a and b) and exercise 18 (a and d)
Problem #3: Section 3.2, exercise 34 and exercise 39 (I know it is odd)
Problem #4: Section 3.3, exercise 8 (use induction)
Problem #5: Section 3.3, exercise 22
Problem #6: Section 3.3, exercise 40 (hint: consider how n stones can be arbitrarily split -- you may need strong induction)
Problem #7: Section 3.4, exercise 4 (c and d) and exercise 8 (a and b)
Problem #8: Section 3.4, exercise 28 and exercise 46
Problem #9: Section 3.5, exercise 4, exercise 14, and exercise 16
Problem #10: Section 3.6, exercise 6

Problem Set 6 - Due Thursday 10/28

Topics: Counting, Pigeons, Permutations, and Combinations (Ch. 4.1-4.5).

Problem #1: Section 4.1, Exercise 16 and Exercise 22 (a, b, c)
Problem #2: Section 4.2, Exercise 6
Problem #3: Section 4.2, Exercise 14 (a, b)
Problem #4: Section 4.2, Exercise 32
Problem #5: Section 4.3, Exercise 10
Problem #6: Section 4.3, Exercise 32 (a, b, c, d)
Problem #7: Section 4.4, Exercise 22
Problem #8: Section 4.5, Exercise 12
Problem #9: Section 4.5, Exercise 30
Problem #10: Section 4.5, Exercise 46

Problem Set 7 - CHANGE -- Due Tuesday 11/9

Topics: Probability (Ch. 5.1-5.3).

Problem #1: Section 5.1, Exercise 6 and Exercise 18
Problem #2: Section 5.1, Exercise 28
Problem #3: Section 5.1, Exercise 36
Problem #4: Section 5.2, Exercise 6 (a, b, and c)
Problem #5: Section 5.2, Exercise 18 (a, b, and c)
Problem #6: Section 5.2, Exercise 24
Problem #7: Section 5.2, Exercise 34 (a, b, c, and d)
Problem #8: Section 5.3, Exercise 2 and Exercise 4
Problem #9: Section 5.3, Exercise 12 (a and b)
Problem #10: Section 5.3, Exercise 24 and Exercise 40 (keep it simple!)

Problem Set 8 - Due Tuesday 11/23

Topics: Recurrence Relations (Ch. 6)

Problem #1: Section 6.1, Exercise 8 (a, c, and e)
Problem #2: Section 6.1, Exercise 10 (a, b, and c)
Problem #3: Section 6.1, Exercise 18 (a and b)
Problem #4: Section 6.1, Exercise 40
Problem #5: Section 6.2, Exercise 4 (c and e)
Problem #6: Section 6.2, Exercise 8 (a and b)
Problem #7: Section 6.3, Exercise 14
Problem #8: Section 6.3, Exercise 18 (a and b)
Problem #9: Section 6.5, Exercise 16
Problem #10: Section 6.6, Exercise 2

Problem Set 9 - Due Thursday 12/2.

Topics: Relations (Ch. 7) amd Graphs I (Ch. 8.1-8.2)

You are on your own to do ten (10) total problems on relations (Ch. 7) and graphs (Ch. 8). Everyone will receive a free 30 points on this assignment. Those who turn in (attempted) solutions to 10 problems from the textbook will receive the full 40 points.

Problem Set 10 - Due Tuesday 12/14.

Topics: Graphs II (Ch. 8.5-8.8) and Models of Computation (Ch. 11)

Problem #1: Section 8.5, Exercise 26 (a, b, c, and d)
Problem #2: Section 8.6, Exercise 4 and Exercise 26
Problem #3: Section 8.7, Exercise 8
Problem #4: Section 8.8, Exercise 10
Problem #5: Section 11.1, Exercise 14
Problem #6, Section 11.1, Exercise 18
Problem #7: Section 11.2, Exercise 14
Problem #8: Section 11.3, Exercise 18 and 20
Problem #9: Section 11.4, Exercise 6 (a, b, and c)
Problem #10: Section 11.5, Exercise 10

Last Modified: Wednesday, 08-Dec-2004 12:34:46 PM EST

CMSC 203, Section 0401 Discrete Structures