Computation & Discrete Math
Resources
These notes come from a number of courses I have taught over the years. They have grown by accretion rather than systematic top-down planning, hence there is some amount of repetition and overlap, as well as fairly obvious gaps. The difficulty also ranges widely, you might want to skip some parts entirely. If you find typos and/or errors, please let me know.
Induction, Iteration, Recursion
| sources | topic |
|---|---|
| Induction, Floyd cycle finding, Pollard's rho, Goodstein sequences | |
| Recursion, Droste, Hanoi, Sierpinski | |
| Iteration 1, Floyd cycle finding, Pollard's rho, Goodstein sequences | |
| Iteration 2, Ducci, Collatz, pseudo-randomness | |
| Iteration 3, Mandelbrot, fixed points |
Combinatorics
| slides | topic |
|---|---|
| Combinatorics | |
| Enumeration | |
| Fibonacci numbers, Fibonacci monoid/group | |
| Inclusion-Exclusion | |
| Moebius function, algebraic proof | |
| Generating functions |
Algebra
| slides | topic |
|---|---|
| pdf pdf | Basic number theory |
| pdf pdf pdf | Magmas, semigroups, groups |
| pdf pdf | Group actions, Polya-Redfield counting |
| Semirings and rings | |
| Polynomial rings, interpolation, evaluation | |
| pdf pdf pdf pdf | Finite fields, implementation, encryption, codes |
| p-Adic numbers, circuits |
Computation
| sources | topic |
|---|---|
| Primitive recursive functions | |
| Coding functions | |
| Loop programs | |
| Wild computation | |
| Register machines | |
| Register Machines by Shepherdson and Sturgis, 1963 | |
| Turing's eponymous machines | |
| Turing machines by A. Turing, 1936 | |
| Other models of computation | |
| Decidability and semi-decidability | |
| Fundamentals of computation | |
| Oracles and reductions | |
| Arithmetical hierarchy | |
| pdf pdf | Intermediate degrees and priority arguments |
| Fractran by J. Conway, 1987 | |
| Universal (2,3) Turing machine by A. Smith, 2020 | |
| Algortihms by Y. Moschovakis, 2002 | |
| Hardness in discrete dynamics, KS 1989 |
Finite State Machines
| sources | topic |
|---|---|
| Finite state machines | |
| Closure properties | |
| State complexity | |
| Minimization of DFA | |
| Fast minimization algorithms | |
| Kleene algebras | |
| Regular expressions | |
| String matching algorithms | |
| Second-order logic, finite/infinite words | |
| Monadic second-order logic, Buechi, Rabin, Muller automata | |
| Safra determinization | |
| Examples for Safra determinization | |
| Automatic sequences, Prouhet-Thue-Morse | |
| Decimation and kernels | |
| Automatic structures, model checking | |
| Rational and synchronous relations | |
| Presburger arithmetic, quantifier elimination | |
| Presburger arithmetic, automatic structure | |
| Examples automaticity elementary cellular automata> | |
| FSM paper by Rabin and Scott, 1959 | |
| Fast minimization by J. Hopcroft, 1971 | |
| Fast minimization by A. Valmari, 2012 | |
| code | C++ minimization code by Valmari |