Math 114. Discrete Structures. Spring 2023.
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 1 | Last day to ADD classes without permission | ||||
| Feb 14 | Last day to DROP classes without a serious and compelling reason and without a grade of W (withdrawal) listed on university transcript | ||||
| Apr 19 | 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 20 | Introduction - First class | ||||
| 2 | 2.6 Matrices | ||||
| Jan 23 | 4.1 | 4 | 4.1 Divisibility and Modular Arithmetic | ||
| Jan 25 | 4.2 | 4.2 Integer Representations and Algorithms | |||
| Jan 27 | 4.3 | 4.3 Primes and Greatest Common Divisors | |||
| Jan 30 | - | ||||
| Feb 1 | 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 3 | 4.5 | 4.5 Applications of Congruences | |||
| Feb 6 | 4.6 | 4.6 Cryptography Suggested reading: The Adventure of the Dancing Men by Arthur Conan Doyle |
|||
| Feb 8 | 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 10 | 5.2 | 5.2 Strong Induction and Well-Ordering | |||
| Feb 13 | 5.3 | 5.3 Recursive Definitions and Structural Induction | |||
| Feb 15 | 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 17 | 6.2 | 6.2 The Pigeonhole Principle | |||
| Feb 20 | President's Day - no classes, no office hours | ||||
| Feb 22 | - | 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 24 | 6.3 | 6.3 Permutations and Combinations | |||
| Feb 27 | - | Test 1 (sections 2.6-5.3) | |||
| Mar 1 | 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 3 | 6.5 | 6.5 Generalized Permutations and Combinations | |||
| Mar 6 | - | ||||
| Mar 8 | 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 10 | 8.2 | 8.2 Solving Linear Recurrence Relations | |||
| Mar 13 | 8.5 | 8.5 Inclusion-Exclusion | |||
| Mar 15 | 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 17 | 10.1 | 10 | 10.1 Graphs and Graph Models | ||
| Mar 20 | 10.2 | 10.2 Graph Terminology and Special Types of Graphs | |||
| Mar 22 | 10.3 | 10.3 Representing Graphs and Graph Isomorphism | 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 24 | - | ||||
| Mar 27 | - | Test 2 (sections 6.1-8.6) | |||
| Mar 29 | 10.4 | 10 | 10.4 Connectivity | Homework 9
10.1: 16, 20 10.2: 6, 18, 20, 22, 26* |
10.2: 50 |
| Mar 31 | Cesar Chavez Day - no classes, no office hours | ||||
| Apr 3 | Spring break | ||||
| Apr 5 | |||||
| Apr 7 | |||||
| Apr 10 | - | 10 | 10.4 Connectivity | ||
| Apr 12 | 10.5 | 10.5 Euler and Hamilton Paths | Homework 10
10.2: 36, 40, 42*, 56 10.3: 6, 12, 18, 20, 26, 36, 38 |
10.2: 50, 60, 62, 64
10.3: 32*, 42, 44, 64 |
|
| Apr 14 | 10.6 | 10.6 Shortest-Path Problems | |||
| Apr 17 | 10.7 | 10.7 Planar Graphs | |||
| Apr 19 | - | Homework 11
10.4: 12, 14(ab), 20, 24, 32, 34, 36 10.5: 4, 14, 18, 20, 28, 34, 40 |
10.4: 18, 22, 30, 46, 56 10.5: 48, 62, 64 |
||
| Apr 21 | 10.8 | 10.8 Graph Coloring | |||
| Apr 24 | - | ||||
| Apr 26 | 11.1 | 11 | 11.1 Introduction to Trees | Homework 12
10.6: 2, 6(b), 8(c), 10(c) 10.7: 6, 8, 12, 16, 24, 26 |
10.6: 18, 20 10.7: 18, 28, 36 |
| Apr 28 | - | ||||
| May 1 | |||||
| May 3 | 11.2 | 11.2 Applications of Trees | Homework 13
10.8: 4, 6, 8, 12(for the graphs in ex. 6 and 8), 20, 28 11.1: 2, 12* |
10.8: 26 11.1: 4, 14, 16, 18, 20, 24, 26 |
|
| May 5 | - | ||||
| May 8 | Test 3 (chapter 10 and 11.1) | ||||
| May 10 | Review, Questions and Answers | ||||
| May 11 | Final exam preparation and faculty consultation day. Consultation hours: 9:30-10:30 am and 2-3:15 pm | ||||
| May 12 | Final exam preparation and faculty consultation day. Consultation hours: 11 AM-12 pm and 2-3 pm | ||||
| May 17 | Final exam (cumulative): 3:30 - 5:30 pm. | ||||