The quizzes will be at the beginning of class each Thursday,
except for November 10 (Midterm 2) and November 24 (Thansgiving)
and will consist of several of the
homework problems assigned for that day (covering material from the previous week).
For example, the quiz on September 29th (Day 3),
will be comprised of several of the homework problems assigned for that day (covering material from the
first day of class).
These assignments are a minimum; you'll be well-rewarded by doing additional problems.
You need to have lots of practice in solving problems.
Consider doing all review problems in Bender, and selected problems
from Schaum's 2000 Solved Problems in Discrete Mathematics.
| Day homework is due |
Homework |
Homework solutions (Author) |
| September 29 (Day 3) |
- BF:1.3, 1.5, 1.13, 1.15, 2.3, 2.6, 2.7 (answer to 2.7 in book is wrong)
- Modify the half-adder circuit to use only AND, OR, and NOT gates.
- Prove that the square of an odd integer is an odd integer.
- Prove that the difference of two odd integers is an even integer.
|
ps
pdf
(Doug)
|
| October 6 (Day 5) |
- BF:2.9, 2.10, 2.13, 2.15, 2.16
- LO:1.4, 1.7, 1.10, 1.15, 1.17, 1.23 (answer to 1.15 in book is wrong; see corrections)
- Write the contrapositive, inverse, and converse of the statement "If n is an
integer for which n*n is even, then n is even."
- Prove, by contradiction, that there are an infinite number of primes. (Hint: Assume that
n is the largest prime.
Then consider n!+1. What is the remainder when divided by any prime number?)
- Prove, by contradiction, that there are at least two people on the planet who were
born on the same second of the same hour of the same day of the same year in the twentieth
centry. (You can assume that there were at least 4 billion--2**32--people born in that century)
|
ps
pdf
(Jan)
|
| October 13 (Day 7) |
- LO:2.6, 2.18, 2.19, 2.20 Review questions: 7, 9
- NT:1.3, 1.8, 1.11, 1.17
(see corrections of book answers for 2.19 and 1.11)
|
ps
pdf
(Jan)
|
| October 20 (Day 9) |
- NT:1.21, 1.27, 2.2 (see corrections to answer 2.2) , 2.4, 2.10, 2.13
|
ps
pdf
(Doug)
|
| October 27 (Day 11) |
- SF:1.1,1.2, 1.8, 1.12 (Note, set specialization means to create example sets).
|
ps
pdf
(Doug)
|
| November 3 (Day 13) |
- SF:1.15, 1.16, 1.19, 1.20, 2.4, 2.6, 2.9, 2.12.
Prove using the element method that, for all subsets,
P, Q, R of U, Q-(P ∩ R) = Q-(P ∩ Q ∩ R)
|
ps
pdf
(Jan)
|
| November 10 (Day 15) |
- SF:2.15, 2.16, 2.17, 2.18.
- IS:1.7, 1.16, 1.4 (Prove 1.4 twice, once by induction,
and the second time using the perturbation method. Hint for
the perturbation method: you might find it useful to use the
perturbation method with a summand of k^3 rather than k^2).
- All pumpkins are the same weight; we can prove this by induction
on the number of pumpkins in a given set.
Here's how:
If there's just one pumpkin then it's the
same weight as itself, so the basis is trivial.
For the induction hypothesis, assume that there
are n pumpkins numbered 1 to n. By the induction
hypothesis, pumpkins 1 through n-1 are the same weight,
and similarly pumpkins 2 through n are the same weight.
But the middle pumpkins, 2 through n-1 can't change weight
when they're in different groups. So pumpkins 1 and n must be
the same weight as well, by transitivity. Thus all n pumpkins
are the same weight; QED.
What, if anything, is wrong with
this reasoning?
- Following is an algorithm that (slowly, but correctly) multiplies two numbers.
Procedure Product(i, j)
Precondition: ____________________________________________
__________________________________________________________
__________________________________________________________
__________________________________________________________
Begin
total = 0
i2 = i;
Loop
Loop Invariant: ______________________________________
______________________________________________________
______________________________________________________
______________________________________________________
Exit when i2 = 0
total =total + j
i2 = i2 - 1
Endloop
End
Postcondition: total is equal to i * j
Fill in the Precondition and Loop Invariant necessary to prove the Postcondition.
- The following are true for the predicate P:
- P(2)
- P(n) -> P(n-1) (for n >= 1)
- (P(2) AND P(n)) -> P(2n)
Show by induction that P(i) is true for all non-negative integers i.
|
ps
pdf
(Doug)
|
| November 17 (Day 17) |
- IS:2.1 (Need not answer monotic or eventually monotonic), 2.2, 2.3.
- IS Review questions: 1, 2, 4, 7
|
ps
pdf
(Jan)
|
| December 1 (Day 20) |
- IS Review questions: 10, 11
- EO:1.6, 1.14, 1.15, 1.22
- In a group of 30 people, must at least 3 have been born in the same month. Why?
- In a group of 30 people, must at least 4 have been born in the same month. Why?
- A programmer writes 500 lines of computer code in 17 days. Must there have been at least one day when the programmer wrote 30 or more lines of code. Why?
- Let S be a set of ten integers chosen from 1 through 50.
Show that the set contains at least two different (but not necessarily disjoint)
subsets of four integers that add up to the same number.
(For instance, if the ten numbers are {3, 8, 9, 18, 24, 34, 35, 41, 44, 50},
the subsets can be take to be {8, 24, 34, 35} and {9, 18, 24, 50}.
The numbers in both of these add up to 101.)
|
ps
pdf
(Jan)
|