| 1 | Due Wed 15th Sept. | Hash table based word frequency counter. | ||||
| 2 | Due Mon 11th Oct. | Shortest path through a simplified map. | ||||
| 3 | Due Wed 27th Oct. | Display the elevation maps, marking large towns. | ||||
| 4 | Due Tues 16th Nov. | Make and test a priority queue. | ||||
| 5 | Due Mon 13th Dec. | Find and nicely display the shortest route from one place to another in the U.S.. | ||||
| 6 | Due Mon 6th Dec. | Scripting: provide functions that allow a program to accept either an expression or a group of simple statements as user input, and evaulate or execute them. |
| Class 1 | Wed 25‑8‑2010 | Introductions, an overview of what we'll be studying, quick reminders of binary chop search and O(nlogn). | ||||
| Class 2 | Mon 30‑8‑2010 | Experiments with hash functions, a statistical program to check the quality of random distribution: why doesn't multiplying the characters of a string together work properly? The problem of the number that has no absolute value. | ||||
| Class 3 | Wed 1‑9‑2010 | Proper examination of hash functions. Clashes are unavoidable, hash tables must be arrays of linked list pointers connecting all strings with the same hash value. Discovering the Poisson distribution in the results. Calculating the evil int. | ||||
| Class 4 | Wed 8‑9‑2010 | The change in performance characteristics as a hash table is filled; the simplicity of resizing to maintain constant time access. Qualitative comparison with binary trees. The "* *" confusion in C++, implementing a variable capacity hash table. | ||||
| Class 5 | Mon 13‑9‑2010 | What can we do with these files? (Files: alphaplaces, intersections, majorroads, usaW125N50D5). We need to work out how to process non-text data files. | ||||
| Class 6 | Wed 15‑9‑2010 | Comparing iostream,
stdio, and
unistd. Extracting meaningful data from a binary (non-text) file. | ||||
| Class 7 | Mon 20‑9‑2010 | First thoughts on the problem of finding the best route from A to B on a road map: the simplified case of the map looking like a tree. | ||||
| Class 8 | Wed 22‑9‑2010 | More consideration of shortest path algorithm, a tidy recursive version, replacing recursion with a single to-do list: everything is exactly the same if the to-do list behaves like a stack, "depth first" search. Wondering what would happen if the to-do list were a queue. | ||||
| Class 9 | Mon 27‑9‑2010 | Templates and Abstract Data Types contrasted with concrete implementations. The basic Breadth-First Search method map2: pos, neg. | ||||
| Class 10 | Wed 29‑9‑2010 | What happens when roads are not all the same length? Breadth first search requires us to invent a Priority Queue. Considered implementations: unordered linked list with search to remove; ordered linked list with search to insert; ordered binary tree, and how easy removal turns out to be. | ||||
| Class 11 | Mon 4‑10‑2010 | The problem with shallow copying especially when destructors are properly defined, complexities of defining assignment operators and copy constructors. Why objects should "always" be passed to functions as references. | ||||
| Class 12 | Wed 6‑10‑2010 | Counting sort is not a general purpose sorting algorithm. Remembering fast (that is, O(N log N)) sorting algorithms: sort by making a binary tree; Merge-sort classical recursive, and more efficient with nested loops. | ||||
| Class 13 | Mon 11‑10‑2010 | Software engineering techniques: loop invariant, pre-condition, post-condition, and loop variants. Mergesort and Quicksort, pivot selection. | ||||
| Class 14 | Wed 13‑10‑2010 | More quicksort pivot selection considerations. Partitioning methods: the clean three-partition method with its obvious loop variant and invariant. | ||||
| Class 15 | Mon 18‑10‑2010 | Steps in creating a graphics project. Using I/O functions under windows. Beginning to deal with formulas and scripts: using a tree as the representation. | ||||
| Class 16 | Wed 20‑10‑2010 | Creating the tree to represent a formula ("parse tree") within a program; printing and evaluating the formula. Inductive logic to demonstrate correctness of recursive design. (step 1), (step 2), (step 3). | ||||
| Class 17 | Mon 25‑10‑2010 | Test Day. | ||||
| Class 18 | Wed 27‑10‑2010 | Cursory test review. Adding variables, assignment, prints, and semicolons to the formulas to make something like a scripting language. Dividing and conquering: making a tokeniser so the parser is untroubled by little details. Starting to make parsing functions. | ||||
| Class 20 | Wed 3‑11‑2010 | The usefulness of layered software design. here we are: basic input system, then tokeniser, then many layers of parser. | ||||
| Class 21 | Mon 8‑11‑2010 | Reminders about priority queues. Parsing even more expressions, priorities, parentheses, etc. | ||||
| Class 22 | Wed 10‑11‑2010 | A Parallel Plan for a Large Project. Function calls, semicolons, and for &&, etc. | ||||
| Class 23 | Mon 15‑11‑2010 | Traditional K&R C. Function declarations, assumed 'int', block has strictly declarations then executable statements, no // comments, 'const' and 'void' on very shaky ground, the evil macros do. | ||||
| Class 24 | Wed 17‑11‑2010 | ANSI C (or C-99). structs, typedefs, void-*, malloc. | ||||
| Class 25 | Mon 22‑11‑2010 | Inheritance, etc. | ||||
| Wed 24‑11‑2010 | Voluntary review session, not a regular class. | |||||
| Class 26 | Mon 29‑11‑2010 | Second Test. | ||||
| Class 27 | Wed 1‑12‑2010 | More inheritance, polymorphism, virtual methods. |
