Math 113

Discrete Structures, Spring 2021 (Section S01)
Current week
Instructor: David Perkinson (schedule)
Text: Discrete Structures, by Ormsby and Perkinson. (Last update: 1/14/23.)
Exercises: compiled homework problems.
Additional (optional) resource: Discrete Mathematics: Elementary and Beyond, by Lovász, Pelikán, and Vesztergombi
Syllabus
For details on office hours, the evening group problem sessions, and drop-in tutoring, see the top of our Moodle page.
Exams
  • Exam 1: Distributed Monday, February 15 and due Wednesday, February 17. Review sheet.
  • Exam 2: Distributed Wednesday, March 17 and due Friday, March 19. Review sheet.
  • Final Exam: This will be a 3-hour exam, distributed by email at 9 a.m. and due by 11 p.m. Pacific on Thursday, May 13. Review sheet.
Week 1: January 25 - 29
Monday: Welcome and warm up.
To do list for Wednesday.
Here is an article about Ron Graham, a renown pioneer in discrete mathematics: Ron Graham. The video Graham's number, linked to in that article, is recommended.
Group problems: Boards.
Wednesday: Beginning counting.
Lecture/quiz (remember to hit the SUBMIT QUIZ button at the end).
Group problems: Boards.
Friday: The language of sets.
Lecture/quiz.
Group problems: Boards.

Video of the week  The eight queen problem

Week 2: February 1 - 5
Monday: Additive and multiplicative counting.
Lecture/quiz.
Turn in: HW2M.
Group problems: Boards.
Wednesday: Functions.
Lecture/quiz.
Turn in: HW2W.
Ouroboros at Bybee and 37th?
Group problems: Boards.
Friday: Permutations and combinations.
Lecture/quiz.
Turn in: HW2F.
Group problems: Boards.

Video of the week   Counting to 1000 on two hands

Week 3: February 8 - 12
Monday: Equivalence relations.
Lecture/quiz (review).
Turn in: HW3M.
Group problems: Boards.
Wednesday: Pascal's triangle and the binomial theorem.
Lecture/quiz (review).
Turn in: HW3W.
Group problems: Boards.
Friday: Induction.
Lecture/quiz (review).
Turn in: HW3F.
Group problems: Boards.

Video of the week   43,252,003,274,489,856,000 Rubik's Cube Combinations

Week 4: February 15 - 19
Monday: Exam distributed today (review sheet).
Class canceled due to weather. Please check your email for a revised schedule.
Wednesday: Something awesome.
Class canceled due to weather.
Turn in exam. The exam is now due at noon on Thursday (tomorrow) via Gradescope.
Friday: Inclusion/exclusion.
Lecture/quiz (review).
Turn in: HW4F.
Group problems. Boards.

Video of the week   5 Unusual Proofs (created by Kelsey Houston-Edwards, Reed class of 2013)

Week 5: February 22 - 26
Monday: Pigeonhole principle.
Lecture/quiz (review).
Turn in: HW5M.
Group problems. Boards.
Wednesday: Graphs: vertices, edges, degree.
Lecture/quiz (review).
Turn in: HW5W.
Group problems. Boards.
Friday: Paths and cycles.
Lecture/quiz (review).
Turn in: HW5F.
Group problems. Boards.

Video of the week  The Mandelbrot Set - Numberphile

Week 6: March 1 - 5
Monday: Trees.
Lecture/quiz (review).
Turn in: HW6M.
Group problems. Boards.
Wednesday: Dyck paths and parentheses.
Lecture/quiz (review).
Turn in: HW6W.
Group problems. Boards.
Friday: Full binary trees.
Lecture/quiz (review).
Turn in: HW6F.
Group problems. Boards.

Video of the week   River crossings, vertex covers, and Alcuin numbers

Week 7: March 8 - 12
Monday: Noncrossing partitions.
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW7M. (Images for LaTeX: 231.png, LaTeX: rook231.png.)
Wednesday: Break (no class).
Friday: Parking functions.
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW7F.

Video of the week  Associahedra: The Shapes of Multiplication

Week 8: March 15 - 19
Monday: Catalan structures and trees.
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW8M.
Wednesday: Exam review. Exam distributed today (review sheet).
Group problems. Boards.
Turn in: HW8W.
Friday: Something awesome.
Turn in exam.
Group problems. Boards.

Video of the week   Hand sanitizer, toilet paper, and \(1/e\).

Week 9: March 22 - 26
Monday: Probability spaces.
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW9M.
Wednesday: Independence.
Lecture/quiz (review).
Group problems. Boards.
No homework due.
Friday: Conditional probability.
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW9F.
Simpson's paradox article.

Week 10: March 29 - April 2
Monday: Expected value.
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW10M.
Wednesday: Special random variables
Lecture/quiz (review).
Group problems. Boards.
Dice.
Turn in: HW10W.
Friday: Divisibility and primes.
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW10F.

Video of the week   Why it's impossible to tune a piano.

Week 11: April 5 - 9
Monday: Distribution of primes.
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW11M.
Wednesday: Fermat's little theorem.
Lecture/quiz (review).
Group problems. Boards,
Turn in: HW11W.
Friday: Euclidean algorithm. (Feel free to skip the "Extended Euclidean algorithm" at the end of this section.)
Lecture/quiz (review).
Euclidean algorithm examples.
Group problems. Boards.
Turn in: HW11F.

Video of the week   Gaps between primes.

Week 12: April 12 - 16
Spring break. No class this week.

Week 13: April 19 - 23
Monday: Modular arithmetic.
Lecture/quiz (review).
Group problems. Boards.
No homework due today.
Wednesday: Euler's totient function.
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW13W.
Friday: Sunzi's theorem.
Lecture/quiz (review).
A nice application of Sunzi's theorem: Card trick.
Group problems. Boards.
Turn in: HW13F.

Video of the week   Secret codes.

Week 14: April 26 - 30
Monday: Recurrence relations and the difference operator. (Reading starts on p. 58.)
Lecture/quiz (review).
Group problems. Boards.
Turn in: HW14M.
Wednesday: Generating functions. (Reading starts on p. 65.)
Lecture/quiz (review).
Group problems. Boards,
Turn in: HW14W.
Friday: Review.
Group problems. Boards.
Turn in: HW14F.

Video of the week   Catalan numbers via generating functions.

Week 15: May 3 -7
Reading week.

Week 16: May 10 - 14
The final Exam will be a 3-hour exam, distributed by email at 9 a.m. and due by 11 p.m. Pacific on Thursday, May 13. Review sheet.

The \(\LaTeX\) document preparation system