MAT 241: Discrete Mathematics

Fall 2020

Basic Information

Instructor: Jed Yang,
Office hours: Tuesday and Friday 13:30–14:30; or by appointment (instructions)
Lectures: Mod B (MWF 09:10–10:00) in Zoom
Course website: https://www.mathcs.bethel.edu/yang/mat241.20f/

Calendar

Daily/weekly schedule to be updated throughout the term; topics and exam dates are tentative and subject to change.

Before class, please read the textbook section(s) to be covered. Do the preview homework exercises. After class, start doing the review homework assigned that day as soon as possible. Unless otherwise stated, homework will be due at the beginning of next class.

Week Monday Wednesday Friday

Unit 1: sets, logic, proofs

1 1. 08/31 M
Introduction
hw02: Getting started
2. 09/02 W
1.1–1.3 introduction
hw03: A more typical homework
3. 09/04 F
2.1 sets
hw04: 2.1.2 # 1, 15bd, 16f, 18d.
2.1.4 # 1, 6ace, 11bc, 12d, 17a.
Read Why should I read a math book? on Moodle.
DMGN: Chapter 3, Logic.
2.2.4 # 1bdegkm.
2.3.4 # 2, 6a, 11, 13ac.
2.3.9 # 1, 2, 3, 4a, 7b.
2 (Labor Day) 4. 09/09 W
2.2–2.3 propositional logic
hw05: 2.2.4 # 1aln.
2.3.4 # 12.
2.3.9 # 4e, 8bc, 9bd, 10, 11, 13, 19, 21adf.
2.4.3 # 1, 2, 5a, 10ab.
Read Appendix G xor extended version.
5. 09/11 F
2.4 equivalence, inference
hw06: 2.4.3 # 8, 9, 10d, 11, 12b, 14.
Read Why are definitions important? on Moodle.
2.5.3 # 2, 3, 5, 9, 11, 14ab.
3 6. 09/14 M
2.5 boolean algebras
hw07: 2.5.3 # 4, 6 (idempotence only), 13, 15, 18abe, 23, 25.
Read Why should I memorize? on Moodle.
2.6.2 # 1ac, 2b, 3bd, 9bc, 13af, 18b.
7. 09/16 W
2.6 predicate logic
hw08: 2.6.2 # 1df, 2d, 4b, 9d, 14c, 19de, 21.
Watch What good is boolean algebra? on Moodle.
DMGN: Chapter 4, Elementary Number Theory.
3.1.3 # 1, 4ac.
3.2.6 1ad, 8c.
8. 09/18 F
3.1 proofs
3.2 elementary number theory
hw09: 3.1.3 # 4b.
3.2.6 # 1b, 8a, 10, 11, 13, 14.
DMGN: Chapter 5, Proof.
Re-read Appendix G xor extended version.
3.3.10 # 1a, 4, 10, 15, 20, 22.
4 9. 09/21 M
3.3 proof strategies
hw10: 3.3.10 # 9, 12, 16, 19, 27, 30, 37, 39*, 42, 44.
Read only some subsections.
3.4.7 # 1b, 7, 10, 15ad.
* 39: extra credit part will not be graded.
10. 09/23 W
3.4.{1,4,5} some applications
hw11: 3.4.7 # 1ad, 8, 11, 12*, 14*, 15bc, 17, 20, 21.
DMGN: Chapter 6, Mathematical Induction.
3.5.6 # 1a*.
* 12: you may use Mathematica or WolframAlpha.
* 14: must use Theorem 3.46.
* 1a: use the same formatting style as in textbook examples (proof of Theorem 3.54, Example 3.35, etc.). Clearly label the step where you use the inductive hypothesis.
11. 09/25 F
3.5.{1,2} induction
hw12: 3.5.6 # 1c, 3, 5*, 9*, 11, 27a.
Continue to signpost your induction proofs as in the textbook, with clearly defined $P(n)$, clearly labelled base step, inductive step, and a conclusion sentence; also clearly label where you use the inductive hypothesis.
* 5: think and then read the solution; do not hand in.
* 9: show details (scratch work) of your discovery process.
5 12. 09/28 M
3.5.{3,4} more induction
hw13: 3.5.6 # 16, 27cd.
3.6.3 # 6, 9, 11, 12, 13, 15, 16, 21.
Install and become familiar with Mathematica.
13. 09/30 W
3.6 creating proofs
hw14: 3.6.3 # 3, 4, 7, 14, 29, 34, 41.
DMGN: Chapter 7, (skip Counting 1 and jump to) Algorithms.
4.1.3 # 1*, 2, 4.
* 1: think first and then read the solution; do not hand in.
Note: use the pseudocode notation from the book. Do not hand in Java or C code (so no curly braces, || for or, % for mod, int, etc.).
Read first 5 sections of "topics and tips" for exam1, linked below.
14. 10/02 F
4.1 expressing algorithms
hw15: 4.1.3 # 10, 15.
Read 4.2.1, do exercises below (without using tools from 4.2.2), then read 4.2.2.
4.2.3 # 1*, 2*, 3, 4ac, 5ad.
* 1, 2: use Mma, with notebook on Moodle as a starting point.
Read logistics section of "topics and tips" for exam1.
Unit 2: algorithms, counting, recursion

6 15. 10/05 M
4.2.{0,1,2} algorithmic complexity
hw16: study for exam. Math Lab is open Mon/Tue for review.
16. 10/07 W
exam 1 (topics and tips)
hw17: 4.2.3 # 6, 12, 15, 16, 19c, 20d.
4.2.5 # 1cd, 2, 3, 5, 7ab.
~~3.5.6 # 29 (just the base step).~~
(fall break)
7 17. 10/12 M
4.2.4 searching
~~3.5.5 multidimensional induction~~
hw18: 4.2.3 # 20b.
4.2.5 # 7cd, 8ac.
4.3.4 # 1*, 2*, 3, 4b, 7a, 9b.
* Download program from textbook website and run with Java. Use a computer in CC230 (the MathCS Lab) or your own computer if you have Java runtime system installed. Use built-in texts.
18. 10/14 W
4.3 pattern matching
hw19: 4.3.4 # 4c, 6c, 7c, 10b, 11b, 14cd, 15.
Use the format from the book; show tables where appropriate; and list entries in the BM Last table in alphabetical order.
Write neatly or type up your solution and export as PDF.

Read 4.4 and 5.1 up to 5.1.4.
DMGN: Counting 1, Chapter 8 (but skip Counting 2).
5.1.6 # 1c, 2, 3, 5, 8, 10, 12.
19. 10/16 F
4.4 undecidability
5.1.$\{n:n\leq4\}$ counting
hw20: 5.1.6 # 19, 21, 26, 28, 30, 31.
Read rest of 5.1.
5.1.6 # 22, 27, 33, 40.
5.1.8 # 2, 4, 7, 10, 18c.
8 20. 10/19 M
5.1 counting
hw21: 5.1.6 # 44a.
5.1.8 # 15, 19, 25, 29, 30.
Read the vcp overview; download the binaries, unzip, and run vcp.jar (do this in CC230 if you do not have Java installed); read the exposition and run the animations for the modules on Binomial Theorem, Counting Subsets, and Tulip. This is not optional.
5.2.3 # 1, 2, 4, 15.
21. 10/21 W
5.2 double counting
hw22: Read (and follow) the advice in items 11–13 of extended version of Appendix G.
5.2.3 # 5, 7, 8, 16, 19.
DMGN: Counting 2, Chapter 9.
5.3.3 # 1, 2, 3, 8, 11, 17, 26cd.
22. 10/23 F
5.3.1 pigeonhole principle
5.3.2 inclusion-exclusion
hw23: 5.2.3 # 17.
5.3.3 # 9, 10, 15, 16*, 18, 28.
* Here and always, provide enough details and justification.
DMGN: Chapter 10, Recursion.
7.1.7 # 1, 4, 7, 8.
9 23. 10/26 M
7.1 recursion
(7.1.6 is optional as it requires some Calc 2.)
hw24: 5.2.3 # 10.
7.1.7 # 2, 10, 11, 12a, 13, 14, 18, 20*.
* 20: Do not hand in.
7.2.5 # 1, 2, 3bd, 4b.
(advising day) 24. 10/30 F
7.2.{0,1} recurrence relations
hw25: 5.2.3 # 18.
7.2.5 # 3a (simplify fully), 5a, 7.
Read.
7.2.5 # 11ab, 12ac, 16*.
* 16: produce (as always, with detailed justification) the recurrence relation, but do not solve the recurrence relation.
10 25. 11/02 M
7.2.{2,3,4} LHRRwCCs
hw26: 5.2.3 # 3, 11*, 20, 24.
* 11: use a combinatorial proof.
7.2.5 # 12d, 15, 16, 18bd, 19b, 21.
No new reading.
26. 11/04 W
(catch-up)
hw27: 5.2.3 # 23ab*.
* 23: this is wrong; fix it in two ways: (a) by changing the LHS slightly; (b) by changing $\binom{n}{2}$ to $\binom{n+1}{2}$; give combinatorial proofs to both.
5.3.3 # 12, 14.
DMGN: Chapter 11, Finite-State Machines.
9.2.3 # 1abc, 2, 3, 4, 12ab.
27. 11/06 F
theory of computation
9.2 deterministic finite automata

Unit 3: theory of computation, graph theory

11 28. 11/09 M
exam 2 (topics and tips)
hw29: 9.2.3 # 5ab, 6c, 9, 15, 17cd.
9.3.2 # 1abc, 5acd, 7ab.
29. 11/11 W
9.3 regular grammars
hw30: 9.3.2 # 6e, 8a, 11.
Worksheet # 2bcd.
Do not memorize Table 9.8.
9.4.3 # 1, 2, 3, 4.
30. 11/13 F
9.4 regular expressions
hw31: 9.4.3 # none.
Worksheet # 4abcd.
DMGN: Chapter 12, Graphs.
10.1.3 # 2acd, 3a, 5a, 6f, 7, 8, 9*.
* 9: there may be other even-degree vertices.
12 31. 11/16 M
10.1 graphs
hw32: 10.1.3 # 4c, 11*, 13, 15, 17, 19, 20.
* 11: explicitly transform this to a graph theory problem and then solve.
10.4.3 # 10 (we defined "isomorphism" in class, so you need NOT read 10.4).
10.2.3 # 1, 3bcd, 5ab*.
* 5: as always, justify your answer.
32. 11/18 W
10.2 walks and connectivity
hw33: 10.2.3 # 7c, 11*, 13, 15, 16, 17.
* 11a: you may use a calculator or Mathematica.
10.3.3 # 1, 3, 5, 7.
33. 11/20 F
10.3 Euler and Hamilton
hw34: 10.3.3 # 8, 12, 13, 14, 15, 16.
10.5.4 # 3*, 9, 10ab, 18.
* 3: Recommendation: use Sandbox; first add all vertices in alphabetical order as the textbook so the labels are right; then add in all edges; then start dragging. When done, you may submit a screenshot (saved as PDF) or draw it by hand. To aid grading, your graph must have correct vertex labels.
As always, feel free to help each other understand the problem, but execute your solution yourself: it is unlikely that two students will arrive at exactly the same configuration. Do not plagiarize.
13 34. 11/23 M
10.5 major graph theorems
hw35: 10.5.4 # 2, 10e, 11, 16, 17.
DMGN: Chapter 13, Trees.
11.1.1 # 6, 8, 12, 15 (do not assume the graph is a tree), 16 (read proof, do not hand in).
(Thanksgiving)
Some games to keep you company:
- Proper drawings of planar graphs

- Colouring maps with four colours
(Thanksgiving)
14 35. 11/30 M
11.1 trees
hw36: 11.1.1 # 1, 2, 4, 18, 19.
11.3.4 # 1, 2.
36. 12/02 W
9.6.1 context-free grammars
11.3.1 parse trees
hw37: 11.3.4 # 4, 5, 6.
Do these review problems to prepare for class:
3.2.6 # 15 (induction on $k$), 20.
There are no preview problems. You may pre-read or not, up to you. We will prove Thm 3.50 in class.
37. 12/04 F
3.4.6 RSA cryptosystem
hw38: 3.4.7 # 9, 23*, 24*, 25*.
* Mathematica commands FactorInteger and Mod may be useful.
Read 7.3 but skip the proof of the master theorem, which we will do in class.
7.3.1 # 4*, 6, 9*.
* 4: read the proof of 3 and tweak it very, very slightly.
* 9: copy the solution for 9b and extend the table with 3 more rows.
15 38. 12/07 M
7.3 the master theorem
- merge sort visualization

hw39: 7.3.1 # 15–19, 21.
Use Thm 7.17, not Thm 7.16.
DMGN: Chapter 14 and 15 (skip Functions and Relations).
39. 12/09 W
(wrap-up)

40. 12/11 F
exam 3 (topics and tips)

Final Exam: 12/14 Monday 14:45–16:45 (topics and tips)

Week	Monday	Wednesday	Friday
Unit 1: sets, logic, proofs
1	1. 08/31 M Introduction hw02: Getting started	2. 09/02 W 1.1–1.3 introduction hw03: A more typical homework	3. 09/04 F 2.1 sets hw04: 2.1.2 # 1, 15bd, 16f, 18d. 2.1.4 # 1, 6ace, 11bc, 12d, 17a. Read Why should I read a math book? on Moodle. DMGN: Chapter 3, Logic. 2.2.4 # 1bdegkm. 2.3.4 # 2, 6a, 11, 13ac. 2.3.9 # 1, 2, 3, 4a, 7b.
2	(Labor Day)	4. 09/09 W 2.2–2.3 propositional logic hw05: 2.2.4 # 1aln. 2.3.4 # 12. 2.3.9 # 4e, 8bc, 9bd, 10, 11, 13, 19, 21adf. 2.4.3 # 1, 2, 5a, 10ab. Read Appendix G xor extended version.	5. 09/11 F 2.4 equivalence, inference hw06: 2.4.3 # 8, 9, 10d, 11, 12b, 14. Read Why are definitions important? on Moodle. 2.5.3 # 2, 3, 5, 9, 11, 14ab.
3	6. 09/14 M 2.5 boolean algebras hw07: 2.5.3 # 4, 6 (idempotence only), 13, 15, 18abe, 23, 25. Read Why should I memorize? on Moodle. 2.6.2 # 1ac, 2b, 3bd, 9bc, 13af, 18b.	7. 09/16 W 2.6 predicate logic hw08: 2.6.2 # 1df, 2d, 4b, 9d, 14c, 19de, 21. Watch What good is boolean algebra? on Moodle. DMGN: Chapter 4, Elementary Number Theory. 3.1.3 # 1, 4ac. 3.2.6 1ad, 8c.	8. 09/18 F 3.1 proofs 3.2 elementary number theory hw09: 3.1.3 # 4b. 3.2.6 # 1b, 8a, 10, 11, 13, 14. DMGN: Chapter 5, Proof. Re-read Appendix G xor extended version. 3.3.10 # 1a, 4, 10, 15, 20, 22.
4	9. 09/21 M 3.3 proof strategies hw10: 3.3.10 # 9, 12, 16, 19, 27, 30, 37, 39, 42, 44. Read only some subsections. 3.4.7 # 1b, 7, 10, 15ad. 39: extra credit part will not be graded.	10. 09/23 W 3.4.{1,4,5} some applications hw11: 3.4.7 # 1ad, 8, 11, 12, 14, 15bc, 17, 20, 21. DMGN: Chapter 6, Mathematical Induction. 3.5.6 # 1a. 12: you may use Mathematica or WolframAlpha. * 14: must use Theorem 3.46. * 1a: use the same formatting style as in textbook examples (proof of Theorem 3.54, Example 3.35, etc.). Clearly label the step where you use the inductive hypothesis.	11. 09/25 F 3.5.{1,2} induction hw12: 3.5.6 # 1c, 3, 5, 9, 11, 27a. Continue to signpost your induction proofs as in the textbook, with clearly defined $P(n)$, clearly labelled base step, inductive step, and a conclusion sentence; also clearly label where you use the inductive hypothesis. * 5: think and then read the solution; do not hand in. * 9: show details (scratch work) of your discovery process.
5	12. 09/28 M 3.5.{3,4} more induction hw13: 3.5.6 # 16, 27cd. 3.6.3 # 6, 9, 11, 12, 13, 15, 16, 21. Install and become familiar with Mathematica.	13. 09/30 W 3.6 creating proofs hw14: 3.6.3 # 3, 4, 7, 14, 29, 34, 41. DMGN: Chapter 7, (skip Counting 1 and jump to) Algorithms. 4.1.3 # 1, 2, 4. 1: think first and then read the solution; do not hand in. Note: use the pseudocode notation from the book. Do not hand in Java or C code (so no curly braces, `\|\|` for or, `%` for mod, `int`, etc.). Read first 5 sections of "topics and tips" for exam1, linked below.	14. 10/02 F 4.1 expressing algorithms hw15: 4.1.3 # 10, 15. Read 4.2.1, do exercises below (without using tools from 4.2.2), then read 4.2.2. 4.2.3 # 1, 2, 3, 4ac, 5ad. * 1, 2: use Mma, with notebook on Moodle as a starting point. Read logistics section of "topics and tips" for exam1.
Unit 2: algorithms, counting, recursion
6	15. 10/05 M 4.2.{0,1,2} algorithmic complexity hw16: study for exam. Math Lab is open Mon/Tue for review.	16. 10/07 W exam 1 (topics and tips) hw17: 4.2.3 # 6, 12, 15, 16, 19c, 20d. 4.2.5 # 1cd, 2, 3, 5, 7ab. ~~3.5.6 # 29 (just the base step).~~	(fall break)
7	17. 10/12 M 4.2.4 searching ~~3.5.5 multidimensional induction~~ hw18: 4.2.3 # 20b. 4.2.5 # 7cd, 8ac. 4.3.4 # 1, 2, 3, 4b, 7a, 9b. * Download program from textbook website and run with Java. Use a computer in CC230 (the MathCS Lab) or your own computer if you have Java runtime system installed. Use built-in texts.	18. 10/14 W 4.3 pattern matching hw19: 4.3.4 # 4c, 6c, 7c, 10b, 11b, 14cd, 15. Use the format from the book; show tables where appropriate; and list entries in the BM Last table in alphabetical order. Write neatly or type up your solution and export as PDF. Read 4.4 and 5.1 up to 5.1.4. DMGN: Counting 1, Chapter 8 (but skip Counting 2). 5.1.6 # 1c, 2, 3, 5, 8, 10, 12.	19. 10/16 F 4.4 undecidability 5.1.$\{n:n\leq4\}$ counting hw20: 5.1.6 # 19, 21, 26, 28, 30, 31. Read rest of 5.1. 5.1.6 # 22, 27, 33, 40. 5.1.8 # 2, 4, 7, 10, 18c.
8	20. 10/19 M 5.1 counting hw21: 5.1.6 # 44a. 5.1.8 # 15, 19, 25, 29, 30. Read the vcp overview; download the binaries, unzip, and run `vcp.jar` (do this in CC230 if you do not have Java installed); read the exposition and run the animations for the modules on Binomial Theorem, Counting Subsets, and Tulip. This is not optional. 5.2.3 # 1, 2, 4, 15.	21. 10/21 W 5.2 double counting hw22: Read (and follow) the advice in items 11–13 of extended version of Appendix G. 5.2.3 # 5, 7, 8, 16, 19. DMGN: Counting 2, Chapter 9. 5.3.3 # 1, 2, 3, 8, 11, 17, 26cd.	22. 10/23 F 5.3.1 pigeonhole principle 5.3.2 inclusion-exclusion hw23: 5.2.3 # 17. 5.3.3 # 9, 10, 15, 16, 18, 28. Here and always, provide enough details and justification. DMGN: Chapter 10, Recursion. 7.1.7 # 1, 4, 7, 8.
9	23. 10/26 M 7.1 recursion (7.1.6 is optional as it requires some Calc 2.) hw24: 5.2.3 # 10. 7.1.7 # 2, 10, 11, 12a, 13, 14, 18, 20. 20: Do not hand in. 7.2.5 # 1, 2, 3bd, 4b.	(advising day)	24. 10/30 F 7.2.{0,1} recurrence relations hw25: 5.2.3 # 18. 7.2.5 # 3a (simplify fully), 5a, 7. Read. 7.2.5 # 11ab, 12ac, 16. 16: produce (as always, with detailed justification) the recurrence relation, but do not solve the recurrence relation.
10	25. 11/02 M 7.2.{2,3,4} LHRRwCCs hw26: 5.2.3 # 3, 11, 20, 24. 11: use a combinatorial proof. 7.2.5 # 12d, 15, 16, 18bd, 19b, 21. No new reading.	26. 11/04 W (catch-up) hw27: 5.2.3 # 23ab. 23: this is wrong; fix it in two ways: (a) by changing the LHS slightly; (b) by changing $\binom{n}{2}$ to $\binom{n+1}{2}$; give combinatorial proofs to both. 5.3.3 # 12, 14. DMGN: Chapter 11, Finite-State Machines. 9.2.3 # 1abc, 2, 3, 4, 12ab.	27. 11/06 F theory of computation 9.2 deterministic finite automata
Unit 3: theory of computation, graph theory
11	28. 11/09 M exam 2 (topics and tips) hw29: 9.2.3 # 5ab, 6c, 9, 15, 17cd. 9.3.2 # 1abc, 5acd, 7ab.	29. 11/11 W 9.3 regular grammars hw30: 9.3.2 # 6e, 8a, 11. Worksheet # 2bcd. Do not memorize Table 9.8. 9.4.3 # 1, 2, 3, 4.	30. 11/13 F 9.4 regular expressions hw31: 9.4.3 # none. Worksheet # 4abcd. DMGN: Chapter 12, Graphs. 10.1.3 # 2acd, 3a, 5a, 6f, 7, 8, 9. 9: there may be other even-degree vertices.
12	31. 11/16 M 10.1 graphs hw32: 10.1.3 # 4c, 11, 13, 15, 17, 19, 20. 11: explicitly transform this to a graph theory problem and then solve. 10.4.3 # 10 (we defined "isomorphism" in class, so you need NOT read 10.4). 10.2.3 # 1, 3bcd, 5ab. 5: as always, justify your answer.	32. 11/18 W 10.2 walks and connectivity hw33: 10.2.3 # 7c, 11, 13, 15, 16, 17. 11a: you may use a calculator or Mathematica. 10.3.3 # 1, 3, 5, 7.	33. 11/20 F 10.3 Euler and Hamilton hw34: 10.3.3 # 8, 12, 13, 14, 15, 16. 10.5.4 # 3, 9, 10ab, 18. 3: Recommendation: use Sandbox; first add all vertices in alphabetical order as the textbook so the labels are right; then add in all edges; then start dragging. When done, you may submit a screenshot (saved as PDF) or draw it by hand. To aid grading, your graph must have correct vertex labels. As always, feel free to help each other understand the problem, but execute your solution yourself: it is unlikely that two students will arrive at exactly the same configuration. Do not plagiarize.
13	34. 11/23 M 10.5 major graph theorems hw35: 10.5.4 # 2, 10e, 11, 16, 17. DMGN: Chapter 13, Trees. 11.1.1 # 6, 8, 12, 15 (do not assume the graph is a tree), 16 (read proof, do not hand in).	(Thanksgiving) Some games to keep you company: - Proper drawings of planar graphs - Colouring maps with four colours	(Thanksgiving)
14	35. 11/30 M 11.1 trees hw36: 11.1.1 # 1, 2, 4, 18, 19. 11.3.4 # 1, 2.	36. 12/02 W 9.6.1 context-free grammars 11.3.1 parse trees hw37: 11.3.4 # 4, 5, 6. Do these review problems to prepare for class: 3.2.6 # 15 (induction on $k$), 20. There are no preview problems. You may pre-read or not, up to you. We will prove Thm 3.50 in class.	37. 12/04 F 3.4.6 RSA cryptosystem hw38: 3.4.7 # 9, 23, 24, 25. Mathematica commands `FactorInteger` and `Mod` may be useful. Read 7.3 but skip the proof of the master theorem, which we will do in class. 7.3.1 # 4, 6, 9. * 4: read the proof of 3 and tweak it very, very slightly. * 9: copy the solution for 9b and extend the table with 3 more rows.
15	38. 12/07 M 7.3 the master theorem - merge sort visualization hw39: 7.3.1 # 15–19, 21. Use Thm 7.17, not Thm 7.16. DMGN: Chapter 14 and 15 (skip Functions and Relations).	39. 12/09 W (wrap-up)	40. 12/11 F exam 3 (topics and tips)
Final Exam: 12/14 Monday 14:45–16:45 (topics and tips)

Course Information

Official course description: Covers a collection of topics useful to mathematics and computer science majors. The unifying factor is that topics deal mainly with finite collections of mathematical objects (graphs, trees, finite state machines, etc.). Also includes examination of sets, logic, Boolean algebras, proof techniques, algorithm analysis, counting, and recursion.
Prerequisites: MAT 124M: Calculus 1
Textbook:
- (required) Eric Gossett, Discrete Mathematics with Proof, 2nd edition, 2009, ISBN: 9780470457931.
- (optional) Eric Gossett, Discrete Math: The Graphic Novel, 2016, ISBN: 9781524948566.

Overview

Goals. Discrete Mathematics is a course in Bethel's curriculum designed with three related driving goals:

to provide foundational knowledge, skills, and maturity required to suceed in subsequent math and computer science courses. In fact, this course is a (transitive) prerequisite for roughly half of the required Math or CS courses in our majors.
to help develop process skills in learning, doing, and communicating mathematics.
content: to introduce the wonderful mathematical world of discrete (as opposed to continuous) objects.

Topics. We will consider topics such as proofs, algorithms, counting, recursion, models of computation, graphs, and trees.

Objectives. We will use learning the content as an opportunity to develop mathematical skills. Specifically, I will guide you in learning to:

Learn mathematics: through reading and interrogating a mathematical textbook.
Do mathematics: through problem-solving, not rote practice.
Communicate mathematics: through writing and presenting ideas, proofs, and solutions.

Structure and Adjustments

This is a remote, synchronous course:

We will meet via Zoom. The Zoom link can be found at the top of our Moodle page.
Besides this change, this course will resemble a normal, in-person semester as much as possible.
In particular, you will attend thrice-weekly class sessions to interact with course content, your peers, and the instructor.
Your active participation in class is required and expected.

Due to the uncertain and ever-changing conditions the world is in, additional adjustments may need to be made. Thus:

The instructor reserves the right to make reasonable adjustments to the syllabus if necessary. These changes, if any, will be communicated to students in writing. The instructor will make a good-faith effort to help students adversely affected by such changes.
Each student is asked to make a good-faith effort to try to adapt.

We will get through this semester together.

Grading

Your grade will be determined by a weighted arithmetic mean of various components with weights listed in the table on the right.

component	weight
Participation	5%
Homework and quizzes	30%
Midterm exams	45%
Cumulative final exam	20%

The total score will be converted to a letter grade whose lower bounds are: 93% A, 90% A-, 87% B+, 83% B, 80% B-, 77% C+, 72% C, 69% C-, 66% D+, 60% D, 0% F.

Note that there is no preset curve of how many of each letter grade will be given. If you all do A-level work, you will each get an A. As such, you are encouraged to help each other in the pursuit of perfection.

In many courses I intentionally make one exam harder than others, which gives me information (in a mathematical sense) in separating an A performance from an A- performance. Typically, I will let you know and adjust that exam scores upward. What this means is that you should NOT care about how hard an exam is. If you do A-level work, you will get an A, regardless of the raw numerical score prior to adjustment.

Besides possibly adjusting scores upward for difficult exams, I also reserve the right to lower the grade cutoffs. Both of these help you. I will not hurt you by adjusting your exam scores downward or increasing the grade cutoffs.

Requirements

Whatever you do, work at it with all your heart, as working for the Lord, not for human masters, since you know that you will receive an inheritance from the Lord as a reward. It is the Lord Christ you are serving.
- Colossians 3:23–24 NIV

I will be trying to make these verses true for me as I work with you throughout this course, and I hope that you will, too.

Attendance and participation. I expect you to attend class. You may not notice me taking attendance during class meetings, but I will notice if you are not in class. Occasional absences will not impact your grade because what I look for is not mere attendance, but engagement and participation.

Indeed, coming to class is not just about showing up; it is also about being fully engaged in the learning experience. If you have a question, others in the class may also be wondering the same thing. So, please speak up and ask questions anytime you need to. Not only will you be helping yourself, but also you will be helping your peers. Attending office hours is another great opportunity to ask questions.

Be mindful of others. Refrain from using mobile phones or laptops for activities unrelated to the learning process. There is research that suggests taking notes by hand is better for long-term retention (P. A. Mueller and D. M. Oppenheimer, The pen is mightier than the keyboard, Psychological Science 25 (2014), 1159–1168).

In general, your are expected to keep your video on most of the time to make your engagement more clear. Let me know if there are legitimate reasons why you need to be off-camera frequently.

It is my sincere hope that every one of you get all the points for attendance and participation.

Reading. One of the specific course objectives is not just to learn mathematics (content), but learn how to learn mathematics (skill). Specifically, you will learn how to read a mathematical textbook.

Reading a math textbook is different from reading a novel. You must interrogate it. Ask questions. Work through exercises. Think about every sentence.

It will take time to get used to reading properly, but it will pay dividends if you do not give up. To hold you accountable to the reading, there will often be preview exercises due as part of daily homework based on the reading, before the topic is discussed in class.

Homework. Homework will be assigned most days. The goal of the homework is to give you an opportunity to continuously engage directly with the material. Some of the homework questions are meant to be challenging and to stretch you; simply put, I believe that the homework is where you will do the vast majority of your learning in this class. Grapple with the questions; talk to classmates about solution strategies if you are feeling stuck; do the homework.

Each homework must be scanned and uploaded to Moodle. Instructions for scanning will be given to you.

Homework is due at the beginning of the next class after it was assigned, unless otherwise stated. In general, late work is not accepted. If there are special circumstances, talk to the instructor. To alleviate your anxiety from accidentally forgetting to submit homework before class, illness, emergencies, or other situations beyond your control, the lowest four (4) assignments will be dropped.

Because communicating results to others is an important skill, showing your work is as important as getting an answer. In many instances, credit will only be given if your work accompanies your answer. Some of the points will be given for completing the assignment; most will be awarded for showing work and correctness. You are encouraged to collaborate, but what you turn in must be your own work. See "Learning integrity" and the collaboration policy below.

Presentations. Learning how to communicate mathematics is one of the three course objectives. You will generally communicate by writing (homework). Occasionally, there may be opportunities to present ideas verbally. Presentations are required but will not be graded. Instead, students are asked to put in a genuine effort. Penalties for failure to participate in presentations will be made known when these opportunities are introduced.

Exams. There are several in-class midterm exams (see calendar for a tentative schedule), weighted equally. Subsequent exams will mainly focus on the material covered since the previous exam, but can include previous material too. There will be a final exam during the official final exam period covering the entire course.

There are no make-up exams except in circumstances recognized by the instructor as beyond the control of the student. To receive this consideration, the instructor must be notified of the problem before the exam unless this is impossible, in which case as soon as possible.

Time outside of class. I expect a typical student to spend about two to three hours outside of class for each hour in class. Some students need to spend a bit more than that (which is okay). If you are spending more than 12 hours per week on this course outside of class time, please come talk to me so we can find ways to help you learn the material without spending so much time.

Illness. You should make every effort to attend class when you are healthy. If you become ill, for your well-being, you should not come to class. Yes, this sounds like common sense, but it is tempting to try and power through as normal so as not to fall behind. If you become ill, or know that you will need to miss class for some reason, please contact me as soon as you are able, and we will work together to plan how you will keep up and/or make up any missed work.

Policies

Learning integrity.

Search me, O God, and know my heart;
Try me, and know my anxieties;
And see if there is any wicked way in me,
And lead me in the way everlasting.
- Psalm 139:23–24 NKJV

Collaborative work is an integral part of many successful ventures. As such, I expect that you should collaborate with your classmates a lot during your time in this course. However, it is important to understand that there is a big difference between thinking about and solving a problem as part of a group (which is good, both educationally and morally) and copying an answer or letting someone else copy your answer (which is bad, educationally and morally, and has punitive consequences).

In short, I trust you to maintain the utmost level of academic integrity in this course. Please do not break this trust; if you do, there will be repercussions. The formal policy below lays this out explicitly, and supplements Bethel's academic honesty policy.

Collaboration policy.

You may collaborate on the homework assignments to the extent of formulating ideas as a group, but you may not collaborate in the actual writing of solutions (unless explicitly allowed in the instructions).
In particular, you may not work from notes taken during collaborative sessions.
You may not consult any materials from any previous offerings of this course or from any other similar course offered elsewhere unless explicitly permitted.
You may not look up solutions in any form, including from solution manuals or online repositories.
You are required to completely understand any solution that you submit and, in case of any doubt, you must be prepared to orally explain your solution to me. If you have submitted a solution that you cannot verbally explain to me, then you have violated this policy.

Accommodation policy. Disability-related accommodations are determined by the Office of Accessibility Resources and Services (OARS). Students are responsible to contact the Office of Accessibility Resources and Services. Once OARS determines that accommodations are to be made, they will notify the student and the instructor via e-mail. Students choosing to use the disability-related accommodations must contact the instructor no later than five business days before accommodations are needed. The instructor will provide accommodations, but the student is required to initiate the process for the accommodations.

Concerns and appeals. If you have any concerns regarding the course, your grades, or the instructor, see the instructor first. If needed, see Bethel's academic appeals policy.

Getting Help

If you need help there are multitude of resources you can use:

Yourself. If you're stuck on a problem or struggling with a concept from class, take a break and think about something else (e.g., your Hebrew assignment, the economics of Star Trek) for a few hours and then try a fresh start.
Your classmates. You are each other's best resource: talking through the course material with someone else who is also trying to master it is a great way for you both to learn. (And don't discount the learning that you will do while trying to explain to a classmate an idea covered during class that you think you understand; I can't count the number of times that I've discovered that I didn't really understand something until I tried to teach it to someone.) The homework assignments are meant to challenge you, and figuring some of them out together is a great approach.
Math Lab. The Math Department offers support for students enrolled in math classes by providing a Math Lab. Hours, as well as logistics for attending (in person or remotely) will be provided on Moodle. If you are having any difficulty with your homework in this class, please seek help from the tutors in Math Lab. The Math Lab is not only a great place to get help from tutors, but also is the perfect place to meet other students from class, do homework, and check your work. Plan Math Lab hours into your weekly schedule and develop this habit early on in the course.
The instructor. Come to my (remote) office hours or email to make an appointment. Please read and follow instructions.