| Class 1 | (Tu 20-1-2009) | Binary trees stored in arrays, eliminating overhead for pointers, Inventing the Min-Heap. Discovering Heap-Sort. | ||
| Class 2 | (Th 22-1-2009) | Developing in-place heapsort (the demo). Setting the scene for discrete event simulation. | ||
| Class 3 | (Tu 27-1-2009) | The original Quicksort specification,
a64,
a63; Entropy in information, fastest possible sort time. | ||
| Class 4 | (Th 29-1-2009) | Some Algol-60 samples, using a min-heap as the driving engine for discrete event simulations, and hence an optimal shortest path program. the plague map. | ||
| Class 5 | (Tu 3-2-2009) | The importance of enumerators, comparing infinite numbers. There are as many even numbers as there are integers, but how many is that? | ||
| (We 4-2-2009) | Last day to drop without a 'W' | |||
| Class 6 | (Th 5-2-2009) | Complicated Enumerations, especially Cantor's (notes), (C++ tester). | ||
| Class 7 | (Tu 10-2-2009) | Recursion elimination and an enumerator for trees (notes). | ||
| Class 8 | (Th 12-2-2009) | An O(n×2n) problem "Boolean Satisfiability", and the mysteriously similar "Knapsack" problem. | ||
| Class 9 | (Tu 17-2-2009) | Non-deterministic programs: solutions to knapsack and boolean satidfiability. What NP-complete means. | ||
| Class 10 | (Th 19-2-2009) | Equivalences between independent-set, CNF-satisfiability, vertex-cover, etc. | ||
| Class 11 | (Tu 24-2-2009) | Racing the sorting programs, learning what we can from them. | ||
| Class 12 | (Th 26-2-2009) | Memo-fuctions, dynamic programming, fast knapsack. counting sort. | ||
| (Mo 2-3-2009) | Academic alerts due | |||
| Class 13 | (Tu 3-3-2009) | Perfectly balanced trees, capacity analysis. 2-3-trees, guaranteed logarithmic insertion and search. | ||
| Class 14 | (Th 5-3-2009) | More of 2-3-trees, Object oriented programming as message passing. | ||
| (Fr 6-3-2009) | Last day to apply for graduation | |||
| Class 15 | (Tu 10-3-2009) | Object oriented programs as groups of independent communicating agents. Review of deletion from 2-3-tree. | ||
| Class 16 | (Th 12-3-2009) | Test. | ||
| 14th to 22nd March | Spring Break | |||
| Class 17 | (Tu 24-3-2009) | no class. | ||
| Class 18 | (Th 26-3-2009) | Radix sort, comparison with NlogN sorts. | ||
| Class 19 | (Tu 31-3-2009) | Introducing declarative (functional) programming. | ||
| Class 20 | (Th 2-4-2009) | The power of functional programming: lazy evaluation, provable programs, rapid software development. | ||
| (Mo 6-4-2009) | Last day to drop | |||
| Class 21 | (Tu 7-4-2009) | Mysteries of the Universe: #integers = #fractions = #primes = #programs = #(combination of program with possible inputs) = #computable things. | ||
| Class 22 | (Th 9-4-2009) | Equivalence of finite input decision functions, real numbers, subsets of ints. Uncomputable numbers, Turing's Thesis and the Halting Problem. | ||
| Class 23 | (Tu 14-4-2009) | Consequences of Turing's thesis, computability. | ||
| Class 24 | (Th 16-4-2009) | Tries. | ||
| Class 25 | (Tu 21-4-2009) | Gödel's Incompleteness Theorem: there are things that just can't be known. | ||
| Class 26 | (Th 23-4-2009) | Fortran, Cobol, and "Software Engineering". | ||
| Class 27 | (Tu 28-4-2009) | Carlos & Leo: COCOMO II Eliot: Smalltalk Michael & Sam: Software Development Lifecycle. | ||
| Class 28 | (Th 30-4-2009) | Erick & Abdullah: Prganizing Programmers and Development Gil & Xavier: Computer Aided Software Engineering Scott & Shane: Design Patterns. And here is the final question, slightly corrected. | ||
