Klaus Sutner

Discrete Math Primer

Meeting times for Floyd's cycle-finding algorithm.

Errata for DMP 2025

Functions, page 23	Repeated squaring should produce a, a²,a⁴,a⁸,a¹⁶,...,a²⁵⁶. It takes 9 multiplications to get a²⁶⁰. See #52 on Ed.

Videos

Note: Make sure to watch the first video before you start working on DMP.

Introduction	A few comments about how to handle DMP (18 min).
Math Profs	A solution to the math profs puzzle (15 min).
8 Queens	Using logic to solve the 8 queens problem (20 min).
Sets Bool	Sets and Boolean operations (19 min).
Sets Numbers, Lists	Numbers and lists as sets (16 min).
Mystery Function	The mystery bijections in functions (14 min).
Cycle Finding	Iteration and Floyd's cycle finding algorithm (16 min).
Cellular Automata	Pretty cellular automata pictures (21 min).

Miscellany

Here is some extra material for the curious, it expands on the topics covered in the online course, but some of it is quite advanced and definitely not required for DMP. If you have a bit of extra time during the summer, take a look. The first paper below is a short summary of the course, and was written by a student in 2021, you can use it as a study guide.

If you have a lot of time, there is much, much more at CDM Resources. The first blocks on induction, combinatorics, algebra and computation cover quite a bit of the material in 15-151, 15-251 and beyond. This material it is meant for students who already have a strong background and find the DMP less than challenging. In other words, if you find DMP boring, take a look, otherwise its better to wait.

Notes 21	DMP notes written by a student in 2021.
MP Proof	A computer generated proof for the math prof puzzle, by a student in 2023.
Logic CP Q12	Another computer generated proof, this one for logic checkpoint 12, by a student in 2022.
Cube Puzzle	A little geometry puzzle. An animated solution, by a student in 2024.
5 Houses	A slightly harder logic puzzle.
Ducci Sequences	Extended discussion of Ducci sequences.
Trellis Automata	The math underlying an old pinball game.
Conway Fractran	Conway's fraction based programming language.
Surreals	Conway's surreal numbers, or: the mother of all inductions.
Formal Proofs	More details on formal proofs, some examples.