Math 114. Discrete Structures. Spring 2022.
Tentative class schedule with homework assignments
This schedule is subject to change. Assignments shown in gray italics 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 | |||||
|---|---|---|---|---|---|
| Feb 2 | Last day to ADD classes without permission | ||||
| Feb 15 | Last day to DROP classes without a serious and compelling reason and without a grade of W (withdrawal) listed on university transcript | ||||
| Apr 20 | Last day to DROP classes for a serious and compelling reason | ||||
| See registration calendar for other important dates | |||||
| Date | Read before class | Chapter | Sections covered or to be covered | Homework due 11:59 PM | Optional (for extra credit) |
| Jan 21 | Introduction - First class | ||||
| 2 | 2.6 Matrices | ||||
| Jan 24 | 4.1 | 4 | 4.1 Divisibility and Modular Arithmetic | ||
| Jan 26 | 4.2 | 4.2 Integer Representations and Algorithms | |||
| Jan 28 | 4.3 | 4.3 Primes and Greatest Common Divisors | |||
| Jan 31 | - | ||||
| Feb 2 | 4.4 | 4.4 Solving Congruences | Homework 1
2.6: 2, 4(ac), 10, 14, 26 4.1: 4, 10(def), 20 4.2: 2(ab), 4(ab) 4.3: 4(abc) Homework template (optional) |
4.2: 8, 18, 19, convert 73453218 to its hexadecimal expansion and AB07B316 to its octal expansion | |
| Feb 4 | 4.5 | 4.5 Applications of Congruences | |||
| Feb 7 | 4.6 | 4.6 Cryptography | |||
| Feb 9 | 5.1 | 5 | 5.1 Mathematical Induction | Homework 2
4.3: 14, 24(bd), 28, 33(ab), 40(abc) 4.4: 4, 8, 10, 16, 20, 26 4.5: 15, 20(ab) |
4.3: 22, 23 4.4: 18*,19* |
| Feb 11 | 5.2 | 5.2 Strong Induction and Well-Ordering | |||
| Feb 14 | 5.3 | 5.3 Recursive Definitions and Structural Induction | |||
| Feb 16 | 6.1 | 6 | 6.1 The Basics of Counting | Homework 3
4.6: 4, 8 5.1: 20, 22, 32, 62, 78 5.2: 10, 12, 14 |
5.1: 46 (may use 45), 54
More optional problems on M.I. 5.2: 18 |
| Feb 18 | 6.2 | 6.2 The Pigeonhole Principle | |||
| Feb 21 | President's Day - no classes, no office hours | ||||
| Feb 23 | - | 6 | 6.2 The Pigeonhole Principle | Homework 4
5.3: 4, 8, 12, 18 6.1: 16, 22*, 26, 30, 34, 40 |
5.3: 36, 38
6.1: 44, 50 |
| Feb 25 | 6.3 | 6.3 Permutations and Combinations | |||
| Feb 28 | - | Test 1 (sections 2.6-5.3) | |||
| Mar 2 | 6.4 | 6 | 6.4 Binomial Coefficients and Identities | Homework 5
6.2: 4, 12, 14, 36 6.3: 10, 12, 14, 22*, 28 |
Optional Problems on Pigeonhole Principle
6.3: 36, 42, 44 |
| Mar 4 | 6.5 | 6.5 Generalized Permutations and Combinations | |||
| Mar 7 | - | ||||
| Mar 9 | 8.1 | 8 | 8.1 Applications of Recurrence Relations | Homework 6
6.3: 16, 24, 32 6.4: 6, 8, 20, 22*, 28* 6.5: 12, 14, 18, 22 |
6.4: 10, 24, 30, 38
6.5: 20, 50, 62 |
| Mar 11 | 8.2 | 8.2 Solving Linear Recurrence Relations | |||
| Mar 14 | 8.5 | 8.5 Inclusion-Exclusion | |||
| Mar 16 | 8.6 | 8.6 Applications of Inclusion-Exclusion | Homework 7
6.5: 10*, 24, 30, 40 8.1: 8, 12, 14 8.2: 4(adef)*, 12, 14, 20, 22 |
6.5: 44, 46 8.1: 6, 10 8.2: 40 |
|
| Mar 18 | 10.1 | 10 | 10.1 Graphs and Graph Models | ||
| Mar 21 | 10.2 | 10.2 Graph Terminology and Special Types of Graphs | |||
| Mar 23 | - | Homework 8
8.5: 2, 6, 8, 12, 14, 16, 18 8.6: 4, 6, 10, 12, 14, 16, 26 |
8.6: 18, 22, 24 | ||
| Mar 25 | 10.3 | 10.3 Representing Graphs and Graph Isomorphism | |||
| Mar 28 | - | Test 2 (sections 6.1-8.6) | |||
| Mar 30 | 10.4 | 10 | 10.4 Connectivity | Homework 9
10.1: 16, 20 10.2: 6, 18, 20, 22, 26*, 36, 40, 42*, 56 |
10.2: 50, 60, 62, 64 |
| Apr 1 | - | ||||
| Apr 4 | 10.5 | 10.5 Euler and Hamilton Paths | |||
| Apr 6 | 10.6 | 10.6 Shortest-Path Problems | Homework 10
10.3: 6, 12, 18, 20, 26, 36, 38 10.4: 12, 14(ab), 20, 24, 32, 34, 36 |
10.3: 32*, 42, 44, 64 10.4: 18, 22, 30, 46, 56 |
|
| Apr 8 | - | ||||
| Apr 11 | Spring break | ||||
| Apr 13 | |||||
| Apr 15 | |||||
| Apr 18 | 10.7 | 10 | 10.7 Planar Graphs | ||
| Apr 20 | - | Homework 11
10.5: 4, 14, 18, 20, 28, 34, 40 10.6: 2, 6(b), 8(c), 10(c) |
10.5: 48, 62, 64 10.6: 18, 20 |
||
| Apr 22 | 10.8 | 10.8 Graph Coloring | |||
| Apr 25 | 11.1 | 11 | 11.1 Introduction to Trees | ||
| Apr 27 | - | Homework 12
10.7: 6, 8, 12, 16, 24, 26 10.8: 4, 6, 8, 12(for the graphs in ex. 6 and 8), 20, 28 |
10.7: 18, 28, 36 10.8: 26 |
||
| Apr 29 | |||||
| May 2 | 11.2 | 11.2 Applications of Trees | |||
| May 4 | - | Homework 13
11.1: 2, 12* |
11.1: 4, 14, 16, 18, 20, 24, 26 | ||
| May 6 | |||||
| May 9 | Test 3 (chapter 10 and 11.1) | ||||
| May 11 | Review, Questions and Answers | ||||
| May 12 | Final exam preparation and faculty consultation day. Consultation hours: 9:30-10:30 in PB 340 | ||||
| May 13 | Final exam preparation and faculty consultation day. Consultation hours: 9-11 in PB 340 | ||||
| May 18 | Final exam (cumulative): 11:00 am - 1:00 pm. | ||||