CMSC 203, Section 0401  Spring 2005
Discrete Structures
Suggested Review Problems for Final Exam  DO NOT TURN THESE IN
Sections 2.42.5, 2.7, 3.13.6, 4.14.3, 4.5, 5.15.2
 All of the suggested review problems for exams 1 and 2
 Section 5.3: Exercises 3b, 8
 Section 6.1: Exercises 9, 11, 17, 23
 Section 6.2: Exercises 3, 9
 Section 6.6: Exercises 3, 5
 Section 7.1: Exercises 3, 7
 Section 7.3: Exercises 1, 7, 19, 21
 Section 7.4: Exercises 5, 7, 9, 16, transitive closure of graphs in 6 and 7
 Section 7.5: Exercises 3, 7, 15, 17
 Section 8.1: Exercises 19
 Section 8.2: Exercises 1, 3, 7, 9, 11, 15, 19, 21, 23
 Section 8.3: Exercises 3, 11, 13, 35, 37, 43, 57, 61, 63
 Section 8.4: Exercises 1, 3, 5, 7, 21
 Section 8.5: Exercises 5, 7, 10, 15, 31
 Section 8.7: Exercises 3, 5
 Section 8.8: Exercises 1, 3, 5, 9, 11, 13
 Section 11.2: Exercises 1, 7, 9, 13
 Section 11.3: Exercises 13, 15, 17
Homework 10  Due Monday, 5/16/2005
Topics: Graphs, Finite State Machines, Cryptography (ch. 8, 11, 2.6).
 Problems #12: Section 8.3, exercises 34, 36
 Problems #34: Section 8.4, exercises 10, 12b
 Problem #5: Section 8.5, exercise 26
 Problem #6: Section 8.8, exercise 8
 Problems #78: Section 11.2, exercises 8, 14
 Problem #9: Section 2.6, exercise 46
 Problem #10: What are the numerical values of the public key and private key for Problem #9? Describe two ways (as we discussed in class) that you can securely obtain an individual's public key.
Homework 9  Due Wednesday, 5/4/2005
Topics: Generating Functions, InclusionExclusion, Relations, Graphs (ch. 6.46.5, 7, 8).
 Problem #1: Section 6.4, exercise 3(c,d)  justify your answers.
 Problem #2: Section 6.5, exercise 16
 Problem #3: Section 6.6, exercise 2
 Problem #4: Section 7.1, exercise 6(d,f)
 Problems #56: Section 7.4, exercises 6, 18(b,e)
 Problem #7: Section 7.5, exercises 2(a,c) [justify your criteria, and show your work]
 Problems #89: Section 7.5, exercises 10, 16
 Problem #10: Section 7.6, exercise 4
 Problems #1113: Section 8.2, exercises 14, 16, 22
 Problem #14: Section 8.3, exercises 20
Homework 8  Due Wednesday, 4/27/2005
Topics: Probability, Recurrence Relations (ch 5.3, 6.1, 6.2).
 Problems #14: Section 5.3, exercises 4, 12, 24, 40
 Problems #58: Section 6.1, exercises 8(a,c,f), 12, 18, 36(a)
 Problems #911: Section 6.2, exercises 4(b,d), 8, 12
Suggested Review Problems for Exam 2  DO NOT TURN THESE IN
Sections 2.42.5, 2.7, 3.13.6, 4.14.3, 4.5, 5.15.2
 Section 2.4: Exercises 9, 17, 29, 31, 37
 Section 2.5: Exercises 21 (Show each step)
 Section 2.7: Exercises 1, 7, 9, 13, 17
 Section Chapter 2 Supplimentary Exercises: 25, 27
 Section 3.1: Exercises 5, 17, 25
 Section 3.2: Exercises 3, 9, 13, 17, 31, 35
 Section 3.3: Exercises 7, 13, 21, 31, 51, 53
 Section 3.4: Exercises 9, 13, 23, 27, 31
 Section 3.5: Exercises 1, 5, 13, 33
 Section 3.6: Exercises 1, 7
 Section Chapter 3 Supplementary Exercises: 43
 Section 4.1: Exercises 3, 9, 19, 25, 27, 31, 37, 49
 Section 4.2: Exercises 5, 15, 17, 19
 Section 4.3: Exercises 5, 6, 11, 21, 23, 27
 Section 4.5: Exercises 5, 7, 9, 31, 41
 Section Chapter 4 Supplementary Exercises: 3, 11
 Section 5.1: Exercises 5, 9, 17, 21, 29, 33
 Section 5.2: Exercises 3, 11, 21, 27, 33
 Section Chapter 5 Supplementary Exercises: 3, 17
Homework 7  Due Wednesday, 4/13/2005
Topics: Permutations, Combinations, Probability (ch 4.3, 4.5, 5.1, 5.2).
 Problems #13: Section 4.3, exercises 8, 26, 38
 Problems #46: Section 4.5, exercises 12, 32, 46
 Problems #710: Section 5.1, exercises 10, 18, 28, 36
 Problems #1114: Section 5.2, exercises 6, 18, 24, 34
 Extra Credit (5 pts): Chapter 5 Supplimentary Exercise 26
Homework 6  Due Wednesday, 4/6/2005
Topics: Induction, Recursion, Correctness, Counting, and Pigeons (ch 3.3  4.2).

Problems #13: Section 3.3, exercises 8 (using mathematical induction), 20, 34

Problems #45: Section 3.4, exercises 8 (b,c), 46

Problems #67: Section 3.5, exercises 4, 14

Problem #8: Section 3.6, exercise 12

Problems #910: Section 4.1, exercises 14, 24

Problems #1113: Section 4.2, exercises 8, 14, 32

Extra Credit (4 pts each): Section 3.3 exercise 40, Section 4.1 exercise 42
Homework 5  Due Wednesday, 3/16/2005
Topics: Number theory, Matrices, Sequences and Summations (ch 2.43.2).

Problem #1: Section 2.5, exercises 22 (b,d,f) (You must show each step!)

Problems #23: Section 2.7, exercises 10 (a,c,e), 24

Problems #48: Section 3.2, exercises 10 (a,b,d), 16 (a,d), 18 (d), 34, 39
Suggested Review Problems for Exam 1  DO NOT TURN THESE IN
Sections 1.12.3.
 Section 1.1: Exercises 11, 17, 21, 25
 Section 1.2: Exercises 9, 13, 21, 27, 51
 Section 1.3: Exercises 9, 21, 31, 43
 Section 1.4: Exercises 9, 21, 33, 39
 Section 1.5: Exercises 7, 11, 21, 27, 31, 35, 61
 Section 1.6: Exercises 9, 23
 Section 1.7: Exercises 3, 13, 14, 27
 Section 1.8: Exercises 17, 19, 21, 31, 41
 Chapter 1 Supplementary Exercises: All odd exercises, especially 23, 25
 Section 2.2: Exercises 9, 17, 23, 31, 35
 Section 2.3: Exercises 5, 15, 23
 Chapter 2 Supplementary Exercises: 9, 11, 12
Homework 4  Due Wednesday, 3/2/2005
Topics: Algorithms and Integers (ch. 2.12.4).

Problems #13: Section 2.2, exercises 20, 26, 42 (you can very neatly handdraw the graph or print it as a separate sheet)

Problems #46: Section 2.3, exercises 4, 12, 22

Problems #78: Section 2.4, exercises 16, 32

Problem #9: Prove theorem 7 of 2.4, that ab = gcd(a,b)lcm(a,b)

Extra Credit (5pts each): Section 2.2, exercise 62; Section 2.4, exercise 34
Homework 3  Due Wednesday, 2/23/2005
Topics: Sets and Functions (ch. 1.6  1.8).

Problems #13: Section 1.6, exercises 4, 12, 26

Problems #46: Section 1.7, exercises 10, 22, 36

Problems #79: Section 1.8, exercises 16, 28, 42
Homework 2  Due Wednesday, 2/16/2005
Topics: Predicates, Quantifiers, and Proofs, (Ch. 1.31.5).
You MUST complete this assignment using LaTeX.

Problem #1: Section 1.3, exercise 22 (e)

Problem #2: Section 1.3, exercise 30 (c, e)

Problem #3: Section 1.3, exercise 46

Problem #4: Section 1.4, exercise 10 (f, j) (Note that credit will not be given if you use the uniqueness quantifier  the "there uniquely exists" operator)

Problem #5: Section 1.4, exercise 22

Problem #6: Section 1.4, exercise 30 (d)

Problem #7: Section 1.5, exercise 20 (b)

Problem #8: Section 1.5, exercise 32
Homework 1  Due Wednesday, 2/9/2005
Topics: Predicate logic, (Ch. 1.11.2).
You MUST complete this assignment using LaTeX.

Problem #1: Section 1.1, exercise 8 (b, c, e, f)

Problem #2: Section 1.1, exercise 10

Problem #3: Section 1.1, exercise 12 (d, e)

Problem #4: Section 1.1, exercise 22 (a, c)

Problem #5: Section 1.1, exercise 30

Problem #6: Section 1.2, exercise 8 (a, c)

Problem #7: Section 1.2, exercise 10 (b, d)

Problem #8: Section 1.2, exercise 24