Math 19/CS 21
Discrete mathematics in Computer Science
Fall Term 2003
Schedule
This schedule will be updated frequently. Always check it just before beginning your homework.
|
Date |
Reading Due |
Homework Due |
Class topic |
|
Sept. 24 |
|
|
Organization, Intro. to Counting |
|
Sept. 26 |
1.1 |
P7 #1, 2, 4, 5, 10, 12, 13, 15 |
Permutations and subsets |
|
Sept. 29 |
1.2 |
P16 #2, 5, 6, 7, 8, 9, 13, 18, 19. Optionally, if you are having problems with n choose k, do problem 10 |
Binomial Coefficients |
|
Oct. 1 |
1.3 |
P24 #3a,c, 5, 6, 8, 10, 11, 14, 17, 18, 19 |
Counting Equivalence Classes |
|
Oct. 3 |
1.4 |
P34 #1, 2, 4, 5, 6, 8, 13, 16 |
Cryptography and modular arithmetic |
|
Oct. 6 |
2.1 |
Sec 2.1 #1, 2, 3, 5, 6, 7, 8, 9, 15 |
Inverses mod n and GCDs |
|
Oct. 8 |
2.2 |
Sec 2.2 #1, 2, 4, 6, 7, 8, 9, 11, 12, 13, 16 |
The RSA cryptosystem |
|
Oct. 10 |
2.3 |
Sec 2.3 #1, 2, 4, 5, 7, 9, 11 |
Some details of RSA encryption |
|
Oct. 13 |
2.4 |
Sec. 2.4 # 1, 2, 3, 4, 6, 8, 10, 14, 16 |
Truth Tables |
|
Oct. 14 |
|
Class in X-hour, no homework due |
Variables and quantifiers |
|
Oct. 15 |
3.1 |
Sec 3.1 #3, 4, 5, 6, 12, 13, 15 |
Rules of Inference and proofs |
|
Oct. 17 |
3.2 |
Sec 3.2 #1, 2, 4, 5, 7, 8, 12, 14, 15 |
No class today |
|
Oct. 20 |
3.3 |
Sec 3.3 #1, 3, 4, 6, 7, 9, 10, 14, 15 |
Mathematical Induction |
|
Oct. 20 |
|
Exam 1 7PM-9PM room 102 Bradley |
Note room change |
|
Oct. 22 |
4.1 |
Sec 4.1 # 1, 3, 5, 6, 7, 12 |
Recurrences |
|
Oct. 23 |
|
Tutorial 4:00-5:45 room 104 Bradley |
Note room change |
|
Oct. 24 |
4.2 |
Sec. 4.2 #1, 3, 5, 6, 8, 9, 10, 11, 16 |
Graphs and trees |
|
Oct. 27 |
6.1 |
Sec. 6.1 #1, 2, 3, 4, 7, 9, 12, 13, 17 |
Spanning Trees |
|
Oct. 28 |
|
New
Tuesday Tutorial Time and place |
5:30-7:30,
Room 103 Gerry |
|
Oct. 29 |
6.2 |
Sec. 6.2 # 1, 3, 5, 8, 9, 11, 12, 14, 15 (you may leave out the time analysis). |
Growth Rates of Solutions of Divide and Conquer Recurrences |
|
Oct. 31 |
4.3 |
Sec. 4.3 # 1, 4, 6ab, 7ab, 8, 10 |
The Master Theorem |
|
Nov. 3 |
4.4 (ignore optional parts) |
Sec 4.4 # 1, 2, 3, 7, 8, 9, 10 For problems 7-10, assume n is a power of 2. Note that this makes the ceiling function irrelevant. |
More general kinds of recurrences. |
|
Nov. 5 |
4.5 |
Sec 4.5 #1, 2, 3, 4, 5, 6, 7 |
The problem of selection |
|
Nov. 7 |
4.6 |
Sec 4.6 #1, 2, 3, 4, 5 |
Introduction to Probability |
|
Nov. 10 |
5.1 |
Exam
2 7PM-9PM |
|
|
Nov. 10 |
5.1 |
5.1 #3, 4, 6, 7, 8, 9, 11, 12 |
Unions and Intersections of Events |
|
Nov. 12 |
5.2 |
5.2 # 2, 3, 5, 6, 8, 9, 10, 12, 14 |
Conditional Probability |
|
Nov. 24 |
5.3 |
5.3 # 2, 3, 4, 6, 7, 8, 9, 10, 12 |
Random Variables |
|
Nov. 17 |
5.4 |
5.4 #2, 3, 5, 7, 8, 9 11, 13, 15. 17 |
Expected parameters of Hashing |
|
Nov. 19 |
5.5 The second from k-j+1 |
5.5 # 1, 2, 3, 4, 5, 6, 8, 9, 11, 14 last line on p229 should be the sum equal to 1 to k of 1 over k-j+1 |
Conditional expected value, Randomness in Algorithms |
|
Nov. 21 |
5.6 |
5.6 # 1, 2, 3, 4, 7, 8, 11, 13, 15, 17 |
Variance |
|
Nov.24 |
5.7 |
5.7 # 1, 2, 4, 5, 7, 9, 12,13, 14, 19 |
Eulerian and Hamiltonian Tours |
|
Nov. 25 |
|
No Class in X-hour |
|
|
Nov. 26 |
|
No class, College Holiday, as is Nov. 28 |
|
|
Dec. 1 |
6.3 |
6.3 # 1, 3, 5, 6, 7, 9, 12, 14 |
Matching Theory |
|
Dec. 3 |
6.4 |
6.4 #1, 2, 3, 4, 6, 7, 8, 12, 13 |
Q&A and review; course evaluations |
|
Dec. 8 |
|
Final Exam 1:30 PM |
|