| NEW: Requirements for submitting assignments. | ||||||
| 1 | Due 5.00 pm, Wednesday 20th January | |||||
| Solve the Jurassic Practal. | ||||||
| 2 | Due 5.00 pm, Wednesday 27th January | |||||
| Code your fractal design as simply and compactly as you can. | ||||||
| 3 | Due Sunday 7th February | |||||
| Produce a quadratic solution to the "secret" problem. | ||||||
| 4 | With all possible speed | |||||
| The crocodile challenge. | ||||||
| 5 | Due Wed 16th March | |||||
| Solve the Mystery Fractal. | ||||||
| 6 | Due Sat 19th March | |||||
| AVL tree measurements. | ||||||
| 7 | Due Sun 10th Apr | |||||
| 2-3-tree measurements. with a diagram to make the measurements clear. | ||||||
| 8 | Due Thur 21 Apr | |||||
| Turing machine designs. | ||||||
| + | Due Wed 4 May - Extra Credit Assignment | |||||
| A program to reduce lambda expressions to ground form. | ||||||
| Class 1 | Mon 11‑1‑2016 | Quick introductions, etc. To come: Clever algorithms, with graphs (spanning, flow, etc), and balancing trees, and data compression. Counting things, discovering unsolvable problems and unknowable things. Dynamic programming: Russian missile example 1, 2, 3, 4. The Jurassic Praktal, a Julia set. The GUI interface toolkit object-oriented software engineering project. | ||||
| Class 2 | Wed 13‑1‑2016 | Some serious dynamic programming, introducing the magic oracle. The missile defense system, it turns out to be an instance of the longet descending subsequence problem. D.P. reduces it from exponential to quadratic. Forming clubs of dinosaurs, same as combinatoric C(n, r). D.P. reduces it from exponential to O(n*r). Look for a sequence of binary decisions; look for a recursion and let it tell you how to fill in a table in advance. | ||||
| Class 3 | Wed 20‑1‑2016 | Deriving the D.P. missile defense froom basic principles: find the sequence of boolean decisions,
(and in this case adapt them to what's-the-best decisions), remove the random element by adopting
a sensible ordering, write it as a recursive function, replace the magic oracle with multiple
recursions, change the function into an array and use the recursions to show you the pattern for
filling it. The Brute Force version: for all possible combinations (of missiles that will be hit), validate - is this combination valid; quantify: is this combination better than our previous best. | ||||
| Class 4 | Mon 25‑1‑2016 | The pattern behind the fractal. How compactly can we encode it? The most efficient way (fewest coins) to make change for a given amount, we already know the greedy algorithm is based on an unsafe assumption. A magic oracle would certainly make it easy, but so does dynamic programming. Can I make change? How do I make change? What is the best way? How many ways are there? All essentially the same D.P. algorithm with really tiny changes. Boolean Satisfiability A logic circuit: Brute force is easy but exponential. A magic oracle mames it linear. We don't know a good real solution. What makes Boolean Satisfiability so different from change giving? | ||||
| Class 5 | Wed 27‑1‑2016 | Tractable (P for Polynomial) and Intractable (non-P) problems. The secret (for now) problem. The missile problem, the optimal change problem, and others all seemed exponential but a magic oracle would make them linear, and some clever programming (D.P.) made them quadratic without the need for magic. Bool-sat seems exponential, a magic oracle would make it linear, but as far as we know it remains exponential in reality. Is there something significant there? The "secret" problem seems exponential, again a magic oracle would make it linear, and this time the general version is still exponential as far as we know. A slightly restricted version of it (all numbers are integers of a "reasonable" size) has a quadratic solution. A magic oracle adds Non-Determinism to algorithms. A problem that could be solved in P time if we could really use that non-determinism is known as NP. All P problems are NP. A great many non-P problems are also NP. If we could find a P algorithm for bool-sat (we haven't) then we could use it to create a P solution to the "secret" problem, because we can convert any question of the "secret" type into a question of the bool-sat type that has the same answer. The same applies into a lot of NP problems - the NP-complete set. A question of any NP-complete type can be converted into an eqivalent (has the same answer) problem of any other NP-complete type. If we ever find a P solution to any one of them, we will have a P solution to all of them. | ||||
| Class 6 | Mon 1‑2‑2016 | Transforming problem domains. If the transformation takes non-P time, it is no use. Simplifying some domains: 2-CNF-SAT is easy, (completed). But 3-CNF-SAT is NP-complete. | ||||
| Class 7 | Wed 3‑2‑2016 | The very basic starting point. Height-balancing for ordinary binary trees - the AVL algorithms introduced. | ||||
| Class 8 | Mon 8‑2‑2016 | An AVL balanced tree, illustrating that an insertion can cause
imbalance to appear at any level. The worst case search time for any node in an AVL tree with N nodes is 1.44×log2(N)-0.33; that's just 44% more than the best case for any binary tree. 1.44 is 1/log2(φ), where φ = (sqrt(5.0)+1)/2. We completely deduced the AVL balancing method, and found that after any insertion, at most one rebalancing is ever required, and after rebalancing the tree will be back to its pre-insertion height. | ||||
| Class 9 | Wed 10‑2‑2016 | 2-3-trees. | ||||
| Class 10 | Mon 15‑2‑2016 | For a binary tree the best possible arrangement for searches gives
number of pointers to follow = log2(N) and number of comparisons
to make = log2(N). But we don't know how to achieve such perfect
balance. How do our less perfect attempts match up? We already know that an AVL tree is guaranteed to be between log2(N) and 1.44×log2(N). Minimum edit distance: E1, E2, Completed grid, Solution 1, Solution 2, All solutions. | ||||
| Class 11 | Wed 17‑2‑2016 | The secret problem revealed: Integer Knapsack, "Quadratic" with D.P. A slightly different style: Maximum Sum Contiguous Subsequence, Naturally quadratic but linear with D.P. | ||||
| Class 12 | Mon 22‑2‑2016 | Another mysterious fractal. Removing items from a 2-3-tree. | ||||
| Class 13 | Wed 24‑2‑2016 | How many cases do we need to cover when deleting from a 32tree?
first,
second,
third level of consideration. An Enumerator. | ||||
| Class 14 | Mon 29‑2‑2016 | Enumerations of many infinite sets, they all turn out to have exactly the same size. Until we come upon real numbers. | ||||
| Class 15 | Wed 2‑3‑2016 | Real numbers are not enumerable, restated. It's all just zeros and ones. There must be uncomputable numbers. There must be uncomputable functions (better thought of in programmer's terms as insoluble problems). And at last we identify an insoluble problem, Turing's Halting Problem. | ||||
| Break | ||||||
| Class 16 | Mon 14‑3‑2016 | What I mean by a compact solution. Putting it all together: The logic of the diagonalisation method proving that there are more real numbers than natural numbers. Looking at endless streams of ones and zeros shows us that #R = 2^#N, and there must be properly meaningful functions that can not be computed. The inescapability of the halting problem, but if a computer has N bits of state (storage), then a much bigger computer with more than 2^N bits of storage could solve its halting problems for it. 2^N is always bigger than N, even when N is infinite, so even an infinite computer could not solve its own halting problems. | ||||
| Class 17 | Wed 16‑3‑2016 | Google's too-late announcement. Other uncomputables as a consequence of the halting problem: can't predict run-time errors, can't detect infinite loops, can't even tell whether a program will ever print "cow!". Review of a whole pile of things. | ||||
| Class 18 | Mon 21‑3‑2016 | Mid-term test. | ||||
| Class 20 | Mon 28‑3‑2016 | Some old notes about uncomputable things. Turing Machines. | ||||
| Class 21 | Wed 30‑3‑2016 | More on Turing machines. Introducing the lambda calculus. | ||||
| Class 22 | Mon 4‑4‑2016 | Running turing machines (some new stuff added after class). The second fractal challenege revealed, hilbert curves: iteration 2, iteration 3, iteration 4, iteration 5, iteration 6, iteration 7, the algorithm revealed. More lambda calculus, up to the representation of numbers. | ||||
| Class 23 | Wed 6‑4‑2016 | An alpha conversion on λx.body renaming x to y may only be performed
if y does not appear free in body. A beta reduction on (λx.body val) may only be performed if no variable that appears free in val also appears bound in body. Given λx.B, any appearance of x in B is bound. Any appearance of a variable that is not bound is free. Developing arithmetic: Increment, Add, multiply, power, ... how would that sequence progress? Ackermann's function, O(A(N,N)) is a pretty bad big O to have. | ||||
| Class 24 | Mon 11‑4‑2016 | Parsing and Interpretation. | ||||
| Class 25 | Wed 13‑4‑2016 | ANNOUNCEMENT! Continuing with the lambda calculus: representing data structures; that enables a decrement operation, and hence subtraction. | ||||
| Class 26 | Mon 18‑4‑2016 | The Y combinator, pulling recursion out of thin air. Writing real, useful programs in the lambda calculus. Conway's game of life: building computers out of streams of little "birds" (they're officially called "gliders", but they clearly do not glide at all). | ||||
| Class 27 | Wed 20‑4‑2016 | Functional programming. Tries, a nice easy last topic. |
