| 1 | Due: Sunday 28th January | |||||
| Solve the mystery fractal. | ||||||
| 2 | Due: Sunday 18th February | |||||
| Create some Turing machines. | ||||||
| 3 | Due: Saturday 30th March | |||||
| Implement a lambda-expression reducer. | ||||||
| 4 | Due: Saturday 13th April | |||||
| 2-3-tree operations. | ||||||
| 5 | Due: Thursday 9th May | |||||
| Two NP-complete problems. | ||||||
| Quick introductions. A theory of everything, Boolean Satisfiability, Transforming (de Morgan, etc.). An interesting fractal design. Everything we did today. | ||||||
| This is the little detail that I couldn't remember exactly on Wednesday. Unending streams of zeros and ones. | ||||||
| The Halting Problem, a well defined problem that can never be solved. As a result, a lot of things about the future behaviour of a program are also unknowable: Will it ever print "hippopotamus"? Will it encounter a run-time error? All the same. Turing couldn't make use of knowledge of programming, so his proof (which is also more formal) required a lot more. To understand that we need to start with examining regular grammars and finite state machines. | ||||||
| Determinism and Non-determinism, FSMs for floating point numbers, deterministic, and non-deterministic. Eliminating non-determinism. Closure under composition, union, intersection, and complementation. Lexical:Regular:FSM, Syntactic:Context Free:PDA, Sematic:(Context Sensitive:LBA | Unrestricted:TM) | ||||||
| Grammars don't just recognise languages, they can be used to generate them too. Demonstration of how a context free grammar can, unlike regular grammars, balance parentheses. Why a context sensitive grammar can handle semantics by carrying information from one production to another. The clever little context sensitive grammar that recognises any number of a's followed by the same number of b's followed by the same number of c's. Complete description of how to do things with the Turing machine runner. A few simple Turing machines. | ||||||
| Dean's special event. Two more Turing machine designs: adding 1 to a binary number, and is a unary number an exact power of two and if so, which one? Trading states for symbols and vice versa in a Turing machine. Minsky machines: INC, DEC-or-JUMP, and HALT. Example designs adding and multiplying two numbers and the power of two question again. | ||||||
| The Jurassic Fractal. Fast pattern matching. Functional programming on the way to another more mysterious model for computability. The day-of-week example. | ||||||
| Pure functional programming: prime, sumbet, lists, sort, lazy, lpr, lpr1. | ||||||
| picking up where we left off: sv,
seq,
tree,
lgr,
lgrb. The Peano axioms, peano. | ||||||
| Not quite done with Wednesday's last two links. What is s really? Denotational semantics attaches the axiomatic approach to reality. | ||||||
| Denotational semantics tidied up and taken as far as we need it. | ||||||
| The Lambda Calculus.
An explanatory similarity, I hope I remember this near the beginning. (Just finished the two alternative forms of increment) | ||||||
| More lambda calculus, got as far as subtraction and data structures. Y combinator seen, but before its proper time. We need some more tools to be able to use it. | ||||||
| Conditionals and related things in lambda calculus. The expression that has the shape of a recursive factorial function but isn't. How the Y combinator makes it work exactly like a recursive factorial function. The two Church-Rosser theorems. A first look at Ackermann's function (it is the function A in this program). An orderly exploration and checking successive differences: one, two. | ||||||
| Make a zoom recording. More of Ackermann's: preparing to memoise, and memoised, faster but gets no further. The Primitive Recursive Functions. | ||||||
| Break | 11th to 15th | |||||
| Make a zoom recording. The N queens problem, backtracking and non-determinism: A, B, C, D, E, F, G. A reminder of the knapsack problem: generally O(2N) but in many cases with d.p. it is ~ O(N2). Boolean satisfiability, two forms of question: Can the output ever be zero? or What inputs make the output true? CNF-sat a sub-problem of Bool-sat. "ors of ands" trivial to solve. DNF-sat also sub-prob of Bool-sat, "ands of ors" takes exponential time. But de-Morgan's laws let us transform DNF circuits into CNF circuits. But that particular transformation takes exponential time, so it doesn't really help. The yes/no "oracle" form of Bool-sat solves the which values version one variable at a time. But the oracle form is also exponential in time, so again doesn't really help. Any knapsack problem can be transformed into an equivalent Bool-sat problem quickly. So if a fast solution for Bool-sat is ever discovered it will also be a fast solution for knapsack. Knapsack is reducible to Bool-sat; Bool-sat solves knapsack; but not necessarily the other way round. | ||||||
| Make a zoom recording. Boolean satisfiability by non-magic oracle, and the program. Oracle form of knapsack also solves the more useful "which values?" form. 2CNF can be transformed into an easy graph problem: problem, and solution. Bool-SAT solves 3CNF, and 3CNF solves Bool-SAT. Knapsack solves 3CNF. | ||||||
| The Clique problem solves 3CNF. Clique and Vertex Cover solve each other. AVL trees. | ||||||
| Being a grown-up programmer, Using the emacs editor. AVL trees in full, insertion and deletion. | ||||||
| (backspace and delete now work with emacs) Class exercise: delete from a 23tree. | ||||||
| Missiles: 1, 2, 3, 4. Largest empty square. | ||||||
| Brute force biggest-empty-square time calculated. Experiments to get some insight into matrix multiplication order. Matrix multiplication order becomes easy if you work out which groups are going to have to be multiplied together. Why working backwards really does make sense, it isn't just a rule of thumb. The gold miner, good for practice in bypassing the overlapping recursive way. Rod cutting, very common introduction but not as obvious as many others. Started longest common sub-sequence. | ||||||
| Finished longest common subsequence - hand make table, notice where changes are. Unbounded knapsack. Vertex cover for a tree. | ||||||
| Largest empty rectangle. Bell numbers. | ||||||
| Bell numbers (done properly). A pig's ear. Typesetting - even line breaks. Partition a string into palindromes. | ||||||
| NlogN really is the fastest possible time for a sort, no exceptions. Binomial heaps. | ||||||
| Transitive closure, Warshall's algorithm. Strongly connected components. First and follow sets for LL1 parsing. | ||||||
| LR0 and LALR1 automata. | ||||||
