22 Assignments S2004Math 22 Assignments below were for Spring 2004 from Susannah Epp, Discrete Mathematics, 2nd edition
(Epp is currently in 3rd edition, 2nd edition is now out of print for 2006)
Assignments for Winter Quarter 2006 will be from Johnsonbaugh, Discrete Mathematics, 6th edition and have not yet been determined. They will be posted here during Winter Quarter 2006
Homework includes reading the appropriate sections of the textbook as well
as doing the homework problems. You are responsible for being able to do all assigned homework problems. Problem numbers for assigned homework from each
section of the text will be posted on this page and links may be provided
to some homework problems that are not in the text. Problems may be posted in advance; the problems for each day's assignment will be announced in class
Be prepared to ask questions in class for any homework problems you need help with. Homework questions will be answered in class as time permits.
Additional help with homework may be obtained from the instructor
during office hours or from tutors in the math tutorial center.
| Section | Problems | |
| Day 1 |
Finish Pascal Triangle Handout
Read "What is Discrete Mathematics Anyway?" by Joseph Rosenstein
at http://mathforum.org/dmpow/dmwhatis.html | |
| 1.1 | 5-10, 12, 13, 15, 17, 18, 23, 27, 28, 29, 30, 33, 37, 38, 41, 42, 43, 45, 46 | Symbolic Logic |
| 1.2 | 1, 2, 5, 7, 9, 13, 15, 16, 18, 19, 20, 21, 22, 25, 28, 29, 31, 34, 36, 38, 39, 40 | Conditional Statements |
| 1.3 | 6,7,8,10,12,21,22,23,24,25,26,29,30,35,36,40,42 | Valid forms of Argument |
| 1.4 | 1 - 12, 13, 14, 16, 18, 20, 22, 24, 26, 28, 30 | Logical Circuits |
| 1.5 | 1, 4, 6, 9, 35, 37, 38, 40, 41, 43 | Binary & Hexadecimal |
| 2.1 | Problems from text:3 - 10, 13, 15a,b,c
Additional Practice: Translating language into symbols
http://nebula.deanza.fhda.edu/math/FT/bloom/22HW2-1.htm |
Quantified Statements
Translating between
language & notation |
| 2.1 | Problems from text:19, 22a,b,c, 29, 31, 33
Additional Practice for Negation: Negate the sentences from the additional practice at
http://nebula.deanza.fhda.edu/math/FT/bloom/22HW2-1.htm | Negating
Quantified Statements |
| 2.2
| 1, 3, 4, 5, 7, 8, 9, 10, 13, 16, 22, 24, 26, 28, 31, 33, 34 | Doubly Quantified
Statements |
| 2.3
| 2, 3, 8, 9, 10, 11, 13, 14, 15
Answers for 11, 13, 14, 15 are on Math 22 solutions page | omit material on
diagrams in second
half of section |
| 3.1A
| 1, 3, 4, 6, 7, 8, 9, 15, 16 | Various Methods
of Proof |
| 3.1B
| 10, 11, 13, 21, 22, 25, 26, 27, 29, 32, 33, 36, 40, 41 | Direct Proof
& Counterexample |
| 3.2
| 1 - 4, 6, 8, 9, 11 - 18, 27
17 and 27 are more challenging than the other proofs | Direct Proof
& Counterexample |
| 3.3
| 1, 3, 5, 7, 8, 9, 11, 13, 14, 16, 18, 19, 21, 22, 23, 24, 29, 30a, 31a, 33
HINT: If your answer to number 18 is phrased in terms of "is not divisible by",
then you will not be able to prove it that way. If you have this problem,
then write the contrapositive of the statement and prove the contrapositive.
| Direct Proof
Divisibility |
| 3.4
| 1, 3, 5, 7, 9, 13, 15, 18, 23a,b, 27, 29, 32 - 35
| Direct Proof
div and mod
Quotient Remainder Theorem |
| 3.6
| 1, 2 - 10, 12, 13, 15, 17- 23
| Indirect Proof
|
| 3.7
| 12
|
| 3.5
| 1- 10, 13, 14, 16, 18, 20, 22
| Floor & Ceiling
|
| 5.1
| 1, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 15, 16, 17, 18a | Sets
|
| 5.3
| 40, 41a
35, 36, 37, 38, 44, 45, 46 | Power Sets
Partitions |
| 5.2
| 1, 2, 3, 5, 8, 9 - 16, 19
28, 29, 32, 34, 35 | Element Arguments
Set Identities |
| 5.3
| 1, 6
4, 7, 9, 10: If true, Use an element argument; give counterexample if false
21, 23, 25, 26, 29 Use set identities
| More Element Arguments
& Set Identities |
5.1 #19
5.3 # 39
| | Formal Language
|
| 6.1 |
2, 3, 4, 5, 7, 8, 9
10, 11, 12, 15, 17, 18, 20 | Probability
Counting Lists |
| 6.2 |
1, 3, 4, 6ab, 8, 9, 11, 12, 14, 15, 17, 19, 30, 31, 32, 34, 35, 36 | Trees & Permutations |
| 6.3 |
1, 2, 3, 4, 6, 9, 10, 11, 14, 15, 16, 17, 19, 20, 23, 24, 25, 28 | Addition Rules &
Inclusion Exclusion |
| 6.4 |
1, 2a, 3, 5, 6, 8, 10, 13, 14, 15, 19, 21, 22, 23
7,9,20 are good practice also if needed | Combinations
without repeated elements
Permutations
with repeated elements |
| 6.5 |
1, 2b, 3, 15a, 16a
10,11??? | Combinations with
repeated elements
|
| 4.1 |
1 - 5, 7, 10-16 sequences and explicit formulas
18, 24 - 38 summation notation and product notation practice
59, 60, 65, 66 binary and hexadecimal; also rewrite the algorithm using div and mod notation | Sequences
|
| 4.2 |
3, 4, 6, 8 Introductory examples
9 -- 16 proof by induction
19 - 25 using summation formulas |
Mathematical Induction
Sums of Sequences
|
| 4.3 |
1, 3, 4 sequences and series
16, 17, 20a inequalities |
Mathematical Induction
|
| 8.1 |
1-8, 9, 11, 13, 32, 34, 35
10, 12 are good practice also if needed, but no answer in the text |
Recursively Defined
Sequences
|
| 8.2 |
1-10, 12, iteration
24-33 mathematical induction
41 |
Recurrence Relations
|
| 8.3 |
1, 2
8, 11 second order linear homogeneous recurrence relations with distinct roots
|
Recurrence Relations
|
| 8.3 |
If you are doing more practice problems in 8.3
#9, #10, #11 are appropriate disctinct root problems
#13, #14, #15 are appropriate double root problems |
Recurrence Relations
|
| 7.1 |
1, 3, 4 as of Wednesday
6, 7, 11, 12, 13, 20, 21, 25, 27 |
Functions
|
| 7.3 |
1, 2, 3, 4, 5, 8, 10, 12, 17, 18, 19, 20, 21, 31, 33, 34, 37, 38, 39, 40, 41 |
Functions &
Inverse Functions
|
| 7.4 |
1, 2, 3, 5, 9, 10, 12, 13, 14, 17, 26, 27, 28, 30, 31 |
Pigeon Hole Principle
|
| 10.1 |
1, 3, 4, 5, 8, 9, 11, 14, 17, 19, 22, 23, 25, 29, 30, 31 |
Relations
|
| 10.2 |
1, 3, 4, 6, 12, 14, 15, 18, 21, 23, 26, 31
9, 11 find reflexive, symmetric, and transitive closures |
Properties of Relations
|
| 10.3 |
1, 2, 4, 6, 7, 8, 10, 11, 12, 15, 17, 19, 20, 22, 24 |
Equivalence relations |
| 7.6 |
1, 3, 17, 18 are assigned
6, 7 are challenge questions - (try them but do not panic if you can't do them!) |
Cardinality of Sets |
| 11.1 |
1 - 5, 7, 8, 9,15, 16, 22, 25, 27, 28, 33 - 37, 41
Applications handout | Graph Theory |
| 11.2 |
1-4,8,9,11-19,22,23,25
Look at problem 36. The correct answer is 2572 miles.
There are a LOT choices to try, so you don't need to try it
UNLESS you have some insight as to the good paths to narrow down the choices to investigate,
but this is a good example of a realistic although small graph theory problem.
And it provides good insight why some reasonably good if not perfect algorithms are needed,
because trial and error can be prohibitively long as the problem gets large. | Graph Theory |
| 11.3 |
2, 3, 4, 5, 6,9, 10, 15, 19, 20
Visit the transitive closure calculator link under chapter 10 on the main math 22 page to see
a nice application of adjacency matrices. | Graph Theory |
| 11.4 |
1-8, 10, 11, 14, 16 | Graph Theory |
| 11.5 |
3, 5, 7-14, 22, 23, 25, 30, 32-42 | Trees |
| 11.6 |
1-9, 11, and use the algorithm in #25 to do #5 & #6
you do not need to prove the algroithm in #25 - just use it. | Spanning Trees |
|
|
