Math 114. Discrete Structures. Fall 2017.
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 *.
| Important Deadlines | |||||
|---|---|---|---|---|---|
| Sep 5 | Last day to add a course without a permission number | ||||
| Sep 12 | Last day to drop a course online | ||||
| Sep 14 | Last day to drop a course without a "W" on your transcript | ||||
| Sep 19 | Last day to add a course with a permission number | ||||
| Nov 14 | Last day to withdraw from a course with a serious and compelling reason | ||||
| Date | Read before class | Chapter | Sections covered or to be covered | Homework due (by 12:30 pm) | Optional |
| Aug 22 | Introduction - First class | ||||
| 2 | 2.4 The Integers and Division | ||||
| Aug 24 | 2.4, 2.5 | 2.5 Integers and Algorithms | |||
| Aug 29 | 2.6 | 2.6 Applications of Number Theory | |||
| Aug 31 | 2.7 | 2.7 Matrices | 2.4: 4, 10(def), 12(abc), 16, 28(bd), 32, 36(abc), 54, 56;
2.5: 2(ab), 4(ab), 21(ab). |
2.4: 26, 27;
2.5: 6, 16, 17, 18. |
|
| Sep 5 | 3.2, 3.3 | 3 | 3.2 Sequences and Summations 3.3 Mathematical Induction |
||
| Sep 7 | 3.4 | 3.4 Recursive Definitions and Structural Induction | 2.6: 2(abc), 6, 10, 12, 14, 18, 20;
2.7: 2, 4(ac), 10, 14, 28. |
2.6: 16*,17*. | |
| Sep 12 | 4.1 | 4.1 The Basics of Counting | |||
| Sep 14 | 4.2 | 4 | 4.2 The Pigeonhole Principle | 3.2: 10, 16, 20, 30;
3.3: 20, 26 (may use 25), 40, 60; 3.4: 4, 8, 12, 18 |
Optional Problems on M.I. |
| Sep 19 | 4.3 | 4.3 Permutations and Combinations | |||
| Sep 21 | - | Review | 4.1: 16, 18*, 22, 26, 30, 36;
4.2: 4, 12, 14, 32. |
Optional Problems on Pigeonhole Principle | |
| Sep 26 | - | Test 1 (chapters 2 and 3) | |||
| Sep 28 | 4.4 | 4 | 4.4 Binomial Coefficients | 4.3: 10, 12, 14, 16, 22*, 24, 26, 28, 32 | 4.3: 36, 40, 42 |
| Oct 3 | 4.5 | 4.5 Generalized Permutations and Combinations | |||
| Oct 5 | 6.1 | 6 | 6.1 Recurrence Relations | 4.4: 6, 8, 10, 20, 22, 24, 28, 30 | 4.4: 38 |
| Oct 10 | 6.2 | 6.2 Solving Recurrence Relations | |||
| Oct 12 | 6.5 | 6.5 Inclusion-Exclusion | 4.5: 10*, 12, 14, 18, 20, 22, 24, 30, 40;
6.1: 10, 24 |
4.5: 44, 46, 50, 52; 6.1: 22, 26, 28 |
|
| Oct 17 | 6.6 | 6.6 Applications of Inclusion-Exclusion | |||
| Oct 19 | 8.1, 8.2 | 8 | 8.1 Introduction to Graphs start 8.2 Graph Terminology |
6.2: 4(ade), 12, 14, 20;
6.5: 2, 6, 8, 12, 14, 16, 18 |
|
| Oct 24 | 8.3 | finish 8.2 8.3 Representing Graphs and Graph Isomorphism |
|||
| Oct 26 | - | Review | 6.6: 4, 6, 10, 12, 14, 16, 26;
8.1: 4, 8, 14, 18 |
6.6: 18, 22, 24 | |
| Oct 31 | - | Test 2 (chapters 4 and 6) | |||
| Nov 2 | 8.4 | 8 | 8.4 Connectivity | 8.2: 6, 18, 24, 26, 28(abcd), 35, 42;
8.3: 12, 14, 28, 36, 38 |
8.2: 32, 44;
8.3: 42, 44 |
| Nov 7 | 8.5 | 8.5 Euler and Hamilton Paths | |||
| Nov 9 | 8.6 | 8.6 Shortest-Path Problems | 8.4: 12, 14, 16, 18(a,b), 20, 22, 24, 28 | 8.4: 38, 40 | |
| Nov 14 | 8.7 | 8.7 Planar Graphs | |||
| Nov 16 | 8.8 | 8.8 Graph Coloring | 8.5: 4, 14, 18, 20, 28, 34, 40, 62;
8.6: 2, 6(a), 8(c), 10(c) |
8.5: 48, 64;
8.6: 18, 20 |
|
| Nov 21 | 9.1 | 9 | 9.1 Introduction to Trees | ||
| Nov 23 | Thanksgiving recess - no classes, no office hours | ||||
| Nov 28 | 9.2 | 9 | 9.2 Applications of Trees | 8.7: 8, 12, 20, 22, 26;
8.8: 4, 6, 12(for the graph in ex. 6), 20, 22(c) |
8.7: 16, 18, 28;
8.8: 22(a,b,d)** |
| Nov 30 | Review | 9.1: 2, 12, 14, 16, 18;
9.2: 2, 4, 20, 22 |
9.1: 24, 26;
9.2: 6, 24, 26* |
||
| Dec 5 | Test 3 (chapters 8 and 9) | ||||
| Dec 7 | Consultation day. Office hours: 8:00 am - 1:00 pm | ||||
| Dec 8 | Consultation day. Office hours: by appointment | ||||
| Dec 12 | Final exam (cumulative): 1:15-3:15 pm. | ||||