UMBC CMSC 203 CSEE

# 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 #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