CMSC 203, Section 0401 - Spring 2005
Discrete Structures
Suggested Review Problems for Final Exam - DO NOT TURN THESE IN
Sections 2.4-2.5, 2.7, 3.1-3.6, 4.1-4.3, 4.5, 5.1-5.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 #1-2: Section 8.3, exercises 34, 36
- Problems #3-4: Section 8.4, exercises 10, 12b
- Problem #5: Section 8.5, exercise 26
- Problem #6: Section 8.8, exercise 8
- Problems #7-8: 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, Inclusion-Exclusion, Relations, Graphs (ch. 6.4-6.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 #5-6: 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 #8-9: Section 7.5, exercises 10, 16
- Problem #10: Section 7.6, exercise 4
- Problems #11-13: 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 #1-4: Section 5.3, exercises 4, 12, 24, 40
- Problems #5-8: Section 6.1, exercises 8(a,c,f), 12, 18, 36(a)
- Problems #9-11: Section 6.2, exercises 4(b,d), 8, 12
Suggested Review Problems for Exam 2 - DO NOT TURN THESE IN
Sections 2.4-2.5, 2.7, 3.1-3.6, 4.1-4.3, 4.5, 5.1-5.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 #1-3: Section 4.3, exercises 8, 26, 38
- Problems #4-6: Section 4.5, exercises 12, 32, 46
- Problems #7-10: Section 5.1, exercises 10, 18, 28, 36
- Problems #11-14: 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 #1-3: Section 3.3, exercises 8 (using mathematical induction), 20, 34
-
Problems #4-5: Section 3.4, exercises 8 (b,c), 46
-
Problems #6-7: Section 3.5, exercises 4, 14
-
Problem #8: Section 3.6, exercise 12
-
Problems #9-10: Section 4.1, exercises 14, 24
-
Problems #11-13: 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.4-3.2).
-
Problem #1: Section 2.5, exercises 22 (b,d,f) (You must show each step!)
-
Problems #2-3: Section 2.7, exercises 10 (a,c,e), 24
-
Problems #4-8: 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.1-2.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.1-2.4).
-
Problems #1-3: Section 2.2, exercises 20, 26, 42 (you can very neatly hand-draw the graph or print it as a separate sheet)
-
Problems #4-6: Section 2.3, exercises 4, 12, 22
-
Problems #7-8: 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 #1-3: Section 1.6, exercises 4, 12, 26
-
Problems #4-6: Section 1.7, exercises 10, 22, 36
-
Problems #7-9: Section 1.8, exercises 16, 28, 42
Homework 2 - Due Wednesday, 2/16/2005
Topics: Predicates, Quantifiers, and Proofs, (Ch. 1.3-1.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.1-1.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