This page is undergoing major construction,
most links are currently broken. They will be fixed ...
| Topic | Comment | |
| Foundations | Computability, Logic, Sets. | Ch1-5 |
| Computation | ||
| Turing Machines | Universality and undecidability. | 6up pdf | (Primitive) Recursive Functions | Closure properties, bounded search, coding, Ackermann function. | 6up pdf |
| LOOP Programs | Comparison to prec functions, levels 0, 1, 2. | 6up pdf |
| Completeness | Turing, many-one, one-one reductions, degrees. | 6up pdf |
| Arithmetical Hierarchy | Projections and complements, definability theory. | 6up pdf |
| Deterministic Complexity | Tractable problems, deterministic complexity classes. | 6up pdf |
| Nondeterministic Complexity | NP, projections, examples. | 6up pdf |
| Hardness | Polynomial time reductions, hard and complete problems. | 6up pdf |
| Kolmogorov Complexity | Program size complexity, incompressibility, Omega. | 6up pdf |
| Physics and Computation | Landauer, reversible computation, entropy, physical computation. | 6up pdf |
| Finite State Machines | ||
| Deterministic Machines | Scan algorithms, accessibility and minimality. | 6up pdf |
| Nondeterministic Machines | Deterministic simulation, pattern matching. | 6up pdf |
| Minimization | Quotients and covers. | 6up pdf |
| Minimization algorithms. | 6up pdf | |
| Pattern Matching | Matching strings. | 6up pdf |
| General pattern matching. | 6up pdf | |
| Logic | ||
| Formal Systems | Motivation, axioms, derivations, Frege's system. | 6up pdf |
| Propositional Logic | Boolean functions, circuits, propositional logic. | 6up pdf |
| Algorithms for propositional logic, DPLL. | 6up pdf | |
| Equational Logic | Equational reasoning, Birkhoff's theorem, Boolean algebras. | 6up pdf |
| Predicate Logic I | Predicate calculus, structures, interpretations. | 6up pdf |
| Predicate Logic II | Semantics, completeness, compactness, incompleteness. | 6up pdf |
| Model Checking | Verification, Kripke structures, CTL, LTL. | 6up pdf |
| Sets | ||
| Set Theory | Sets, Cantor, Frege, Zermelo-Fraenkel | 6up pdf |
| Three Theorems | Cardinality, three theorems. | 6up pdf |
| Ordinals | Ordinals, well-orderings, transfinite induction. | 6up pdf |
| Relations and Functions | ||
| Relations | Cartesian products, relations, properties. | 6up pdf |
| Algorithms for Relations | Closures, equivalence relations. | 6up pdf |
| Functions | Functions, functionals, iteration. | 6up pdf |
| Hash functions, universal hashing, perfect hashing. | ||
| Induction | ||
| Induction | IND, LEP, well-orders, recursive datatypes, recursive functions | 6up pdf |
| Iteration | Orbits and fixed points, Collatz, Ducci, Floyd's trick, Knaster-Tarski | 6up pdf |
| Combinatorics | ||
| Basic Combinatorics | Combinations, permutations, binomials, occupancy, inclusion/exclusion. | 6up pdf |
| Fibonacci | Recurrence equations, Fibonacci numbers. | 6up pdf |
| Moebius | Necklaces, bracelets, Lyndon words, Moebius inversion. | 6up pdf |
| Actions and Counting | Group actions, Burnside, Polya-Redfield. | 6up pdf |
| Enumerations | Semigroup actions, enumeration, ranking, unranking. | 6up pdf |
| Randomness | Pseudo-randomness, physics, practical RNGs. | 6up pdf |
| Shortest paths, Dijkstra, Floyd-Warshall, Bellman-Ford. | ||
| Strongly connected components, biconnected components. | ||
| Algebra | Modular Arithmetic | Euclidean algorithm, Chinese remainder theorem, RSA. | 6up pdf |
| Groups | Subgroups, Lagrange's theorem, Cayley's theorem. | 6up pdf |
| Polynomials | Evaluation, interpolation, roots. | 6up pdf |
| Finite Fields | Irreducible polynomials, primitive elements. | 6up pdf |
| FF Applications | GPS, Sigma Automata. | 6up pdf |
| Cryptography | Permutation codes, one-time pads, RSA. | 6up pdf |
| Primality testing, Pratt, Solovay-Strassen. | ||
| Cellular Automata and FSRs | ||
| Feedback Shift Register | GPS, Fibonacci, Galois feedback shift registers. | 6up pdf |
| Cellular Automata | One- and two-dimensional cellular automata, orbits. | 6up pdf |
| CA and FSMs | CA and regular languages. | 6up pdf |
| CA and Algebra | Patterns and generating functions. | 6up pdf |
| CA and Computation | Computation on CA, universal CA. | 6up pdf |
| Reversibility | Reversible CA, Hedlund, decision algorithms. | 6up pdf |
| Miscellany | ||
| Ehrenfeucht-Mycielsky | Non-learning, disjunctiveness, balance. | 6up pdf |
| Sigma Automata | Additive cellular automata, Fibonacci polynomials. | 6up pdf |