Math 114, Discrete Structures. Fall 2004.
Tentative class schedule with homework assignments
Assignments shown in gray may change. The ones shown in black will not.
You are strongly encouraged to read ahead whenever you have time.
Most problems are worth 1 point each. Problems (usually long and/or tricky) that are worth 2 points are marked by *.
| Date | Read before class | Chapter | Sections covered or to be covered | Homework due (by 2 pm) | Optional |
|---|---|---|---|---|---|
| Aug 23 | Introduction - First class | ||||
| 1 | 1.1 Logic | ||||
| Aug 25 | 1.1: 1-15 | 1.2 Propositional equivalences | |||
| Aug 27 | 1.2: 21-25 | 1.3 Predicates and quantifiesrs | |||
| 1.4 Nested quantifiers |
|||||
| Aug 30 | 1.3: 28-38 | 1.1: 2, 10, 22, 24(ab), 28(b) | |||
| Sep 1 | 1.4: 44-51 | 1.5 Methods of proofs
Larry Cusick's tutorial on proof writing |
|||
| Sep 3 | 1.5: 56-63 | ||||
| Sep 6 | Labor Day - no classes, no office hours | ||||
| Sep 8 | 1.5: 63-73 | 1 | 1.5 Methods of proofs | 1.2: 6, 8(a), 10(a)
1.3: 2, 6, 10, 12, 48 1.4: 2, 4, 10*, 26*, 30(a,b,c) |
|
| 1.6 Sets | |||||
| Sep 10 | 1.6: 77-84 | ||||
| Sep 13 | 1.7: 86-94 | 1.7 Set operations | 1.5: 2, 4, 12, 18, 24, 28 | ||
| Sep 15 | 1.8: 97-108 | 1.8 Functions | |||
| Sep 17 | 2.2: 131-142 | ||||
| 2 | 2.2 The growth of functions | ||||
| Sep 20 | 2.4: 153-166 | 1.5: 48
1.6: 4, 10, 14, 28 1.7: 2, 4, 8, 10, 22, 26 |
1.5: 50 1.6: 16 |
||
| 2.4 The integers and division | |||||
| Sep 22 | |||||
| Sep 24 | 2.5: 169-179 | ||||
| 2.5 Integers and algorithms | |||||
| Sep 27 | 1.8: 2, 8(abcd), 12, 14(ab), 18(ac), 24, 28, 34, 60(ac)
2.2: 2(abcd) |
2.2: 4 | |||
| Sep 29 | Key terms and results ch 1: 111-113 |
Review. Recommended review problems:
1, 3, 5, 11, 13, 17, 21, 23, 27, 29, 39, 41, 47 on p.114-116. There are answers in the back of the book. We will do some other problems in class. |
|||
| Sep 30 | Extra office hours: 2-4 pm | ||||
| Oct 1 | Test 1 (covers chapter 1), Solutions | ||||
| Oct 4 | 2.6: 181-193 | 2 | 2.6 Applications of number theory | 2.4: 4, 8, 10(bc), 12(abc), 16, 28(bd), 32
2.5: 2(a), 4(a), 21(ab) |
2.4: 26 |
| Oct 6 | |||||
| Oct 8 | 3.1: 214-223 | ||||
| 3 | 3.1 Proof strategy | ||||
| Oct 11 | 3.2: 225-236 | 2.6: 2(a), 6, 10, 12, 18, 20 1.4: 28* 1.8: 10, 14(cde), 36, 60(bd) Selected solutions | |||
| 3.2 Sequences and summations | |||||
| Oct 13 | |
||||
| Oct 15 | 3.3: 238-242 | ||||
| 3.3 Mathematical induction | |||||
| Oct 18 | 3.3: 243-252 | 3.1: 2, 4, 6, 10, 16, 28, 30 Solution to #30 |
3.1: 26 | ||
| Oct 20 | 3.4: 256-260 | |
|||
| 3.4 Recursive definitions | |||||
| Oct 22 | |||||
| Oct 25 | 4.1: 301-310 | 4 | 4.1 The basics of counting | 3.2: 2, 4(d), 10(b), 14(b), 16(b), 18(a) 3.3: 4, 6, 8, 22, 34, 52 |
Chicken McNuggets Problem |
| Oct 27 | 4.2: 313-318 | 4.2 The pigeonhole principle | |||
| Oct 29 | |||||
| Nov 1 | 4.3: 321-324 | 3.4: 2(b), 4(c), 12 4.1: 6, 8, 16, 18*, 26, 30, 36 Solution to #18 |
|||
| 4.3 Permutations and combinations | |||||
| Nov 3 | Key terms and results ch 2: 206-207 ch 3: 290-291 |
Review. Recommended review problems: 19, 21, 23, 25, 27, 29, 33 on p. 209-210, 1, 3, 11, 13, 15, 19, 23, 35, 37, 43, 53 on p. 292-297, 7, 17, 25 on p. 310-311 |
|||
| Nov 5 | Test 2 (covers 2.4-2.6, 3.1-3.4, 4.1), Solutions | ||||
| Nov 8 | 4.4: 327-333 | 4 | 4.3 Permutations and combinations | 4.2: 2, 8, 14, 16, 22, 32, 40 Selected solutions 4.3: 2, 8, 22(ab) |
4.2: 10 |
| 4.4 Binomial Coefficients | |||||
| Nov 10 | |||||
| Nov 12 | 4.5: 335-341 | 4.5 Generalized Permutations and Combinations | |||
| Nov 15 | 7.1: 471-479 | 7 | 7.1 Relations and their properties | 4.3: 6(abc), 14, 18, 28, 30 4.4: 4, 6, 8, 12, 20, 24 Selected solutions |
100! problem 4.4: 22 |
| Nov 17 | 7.5: 507-512 | 7.5 Equivalence relations | |||
| Nov 19 | |||||
| Nov 22 | 8.1: 537-543 | 8 | 8.1 Introduction to graphs 8.2 Graph terminology |
4.5: 2, 4, 6, 8, 14, 22 7.1: 2, 4(ab), 6(d) 3 problems on Dirichlet's principle Selected solutions |
|
| Extra office hours: 3:30-4:50 (in addition to the regular office hours 12-1:30) | |||||
| Nov 23 | Extra office hours: 12-2 | ||||
| Nov 24 | Thanksgiving recess - no classes, no office hours | ||||
| Nov 26 | |||||
| Nov 29 | Extra office hours: 3:30-4:50 (in addition to the regular office hours 12-1:30) | ||||
| 8.2: 545-554 | 8 | 8.2 Graph terminology | 7.5: 2, 4, 10, 12, 20(c), 26 counting problem 8.1: 4, 8, 14 Selected solutions |
7.5: 54 counting problems |
|
| Dec 1 | |||||
| Dec 3 | Key terms and results ch.4: 349 review 7.1, 7.5, 8.1, 8.2 |
Review. Recommended review problems:
1, 5, 13, 15, 23, 27, 33, 35, 37(a) on p. 350-352, 3, 11, 21, 43 on p. 513-515, 1, 3 on p. 533, 13, 21 on p. 544-545, 1, 5, 13, 25(ab), 27 on p. 554-555; Optional: 37(bc) on p. 352, and 7 on p. 625 |
|||
| Dec 6 | Test 3 (covers 4.2-4.5, 7.1, 7.5, 8.1, 8.2), Solutions | 8.2: 2, 6, 8, 12, 16, 18(abcde), 20, 24(ab), 26, 28(b) Selected solutions |
8.2: 18(f), 24(d) | ||
| Dec 8 | Review - Last clas Practice final - problem 14 has been corrected Solutions - solutions to 10, 13, and 15 have been corrected |
||||
| Dec 9 | Consultation day. Office hours: 1-5 pm | ||||
| Dec 10 | Consultation day. Office hours: 11 am - 3 pm | ||||
| Dec 13 | Final exam (cumulative), 11 am - 1 pm, in SR-6 room 14 Solutions |
||||