The quizzes will be at the beginning of class each Thursday,
except for the first week and the day of the first midterm.
Each quiz will consist of slight modifications to several of the
homework problems assigned for that day (covering material from the previous week).
For example, the quiz on January 19th (Day 4),
will be comprised of slight modifications to several of the homework problems assigned for that day
(covering material from the
first week 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 |
| January 20 (Day 4) |
- 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.
- Solow: 1.4, 1.5, 2.15, 2.18, 2.19, 2.22
|
Homework
Quiz
|
| January 27 (Day 6) |
- BF:2.9, 2.10, 2.13, 2.15, 2.16
- LO: 1.7, 1.10, 1.16 (why or why not?),
1.23
- Solow: 3.7, 3.11, 3.15, 4.6, 4.11, 9.3, 9.7, 9.8, 9.17
|
Homework
Quiz
|
| February 2 (Day 8) |
The homework set will not be tested on a quiz, but will be good practice
for the first midterm.
- LO: 2.8, 2.14, 2.18, 2.19, Review Questions 7, 9
- NT: 1.3, 1.8 1.11, 1.17
- Solow: 5.2, 5.7, 5.14
|
Homework
|
| February 9 (Day 10) |
- What is the product of gcd(a,b) and lcm(a, b). Give an explanation using
the prime factorization of a and b.
- What is the check-digit of the ISBN whose first nine digits are 156592856?
- If I give you a purported ISBN and ask whether it is valid, explain what possible
answers you can provide by verifying the check digit (yes, no, maybe)?
- Which of the following are possible answers to the problem 1238423487234 * 230498230498234 and why?
- 285454422418489283558544756
- 285454422414889283558544756
- 285454422414889273558544756
- 285454425414889283558544756
- NT:2.1
|
Homework
Quiz
|
| February 16 (Day 12) |
- SF 1.2, 1.3, 1.6 (specializing the sets means to
give specific sets as counterexamples), 1.9
- Solow: 5.15
|
Homework
Quiz
|
| February 23 (Day 14) |
- 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)
|
Homework
Quiz
|
| March 9 (Day 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?
- 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.
- IS:2.1, 2.2, 2.3.
- IS Review questions: 1, 2, 4, 7
|
Homework
Quiz
|
| March 16 (Day 20) |
- IS:Review questions: 10, 11
- EO:1.5, 1.10, 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.)
|
Homework
Quiz
|
| March 24 (Final Exam) |
These questions are good practice for the final exam.
- EO:2.1, 2.16, 2.22, 2.23
|
|