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