| 1 | Due: Friday 30th August Tree database with deletion. | |||||
| 2 | Due: Friday 13th September Store and test named places and intersections. | |||||
| 3 | Due: Saturday 5th October Complete the graph and find a route the quick and easy way. | |||||
| 4 | Due: Wednesday 30th October Create a (partial) automatic program code generator. (sample input), (sample output). | |||||
| Quick introductions. istringstream (isstream and osstream) for handling input effectively, their str methods. The mysterious hash function for digital finger-prints, probability of being wrong. Result reduced by modulus (%) to become position in an array. Resolving clashes with linear probing, keeping the hash table at a healthy size. Very short reminder about deleting items from a binary tree. | ||||||
| Hash tables: h1: a starting place, but it has a serious error that does undetected, h2: using the safe array technique to reveal that error, h3: fixed it using unsigned ints in the hash function, but now there are 2 hippopotamusses in Peter Pan, The dangers of unsigned ints, -3 > O. h4: they were caused by collisions, two words with the same hash value, linked lists fix that. The Poisson distribution, what a perfect hash function would deliver. h5: our program drawing a graph of its distribution when λ is around 4 (the output), h6: and when λ is about 1 (the output), seems perfect. h7: calculating the Poisson values shows it for certain (the output). How a bad hash function can accidentally be made. <cstdlib>'s strtol and strtod. Suggested exercise, try to make your own version of each, using C++ strings. | ||||||
| Look at h8.cpp, then see what the actual lengths are. All officially named U.S. places, and the states. intersections.txt, connections.txt, the file formats. A map of nebraska, (also at night), and as a a text file. And as a tree, (also at night), and as a a text file. And as a lattice, (also at night), and as a a text file. | ||||||
| Finding the best route by road from A to B in a road map. 1, Manual exploration - check the graph is correct, 2, We know how to search a tree, what if we tried that on a graph?, 3, The closed set - prevent endless cycles, 4, Reminder of a little trick to make the output readable. | ||||||
| Day Off | 2nd Sept | |||||
| Speed, power of two size, don't lose influence. 5, Pretend successes are failures, 6, A breadth-first search might find the best solution earlier, 7, Successes become failures again. | ||||||
| 8, Ants!, 9, Quiter ants, 10, Keep track of the path followed, 11, Too many parameters - get rid of them, 12, Another useful trick reminder, never missing a return. Recursive version keeping paths in vectors inefficient, must find every path. Ant simulation inefficient, every unit of time must be considered for every active stream of ants. Don't need to record the paths, deduce from shortest distances only, working backwards. With the ants, most simulated steps to nothing, we only care about arrival at a node. How can we do that? What we now know is a priority queue will do it, but how can one be implemented efficiently? Full binary trees can be stored extra-efficiently in arrays, that's half the answer. The heap data structure (actually a min-heap). | ||||||
| Min-heap operations and big-Os in detail. Special heapable objects, not so great for this: index, prio, and node. Animated heap operations. Animated shortest path with a heap, An interesting by-product. | ||||||
| The Floyd-Warshall algorithm. A recurring theme. (a slightly different version that shows more but is more cluttered). How many different parties can a fraternity have? | ||||||
| Review of things connected with Dijkstra's algorithm. Fraternity parties: recursive, timing, memoised, dynamic. Change-giving: how many coins do you need in order to pay a given amount of money? can it be done, natural recursion. | ||||||
| More dynamic programming, considering brute force methods too: Minimum coin change giving completed - memoised, proper dynamic programming, which coins are needed?. Number of minimum length paths in a regular grid. Knapsack, very close to subset sum. | ||||||
| Automatic code generator for the tedious stuff: input and output. (mention subset sum) Maximum sum contiguous subsequence. Cutting diamonds. Travelling salesman, O(N!), no viable solution known (not dynamic programming). Generating permutations. | ||||||
| A mystery file. Lots of things about fstreams. Binary files. The infamous file again. | ||||||
| Making .bmp image files. Binary chop search on a file. Quicksort on the same file. (not quite right, find the error before Monday) | ||||||
| A new class you should know about for next Spring. How to deal with spaces in the binary chop example. Count records, reads, writes, total operations. A different way of building a tree, and why it is useful. | ||||||
| (Recorded) Exploring the natural balance of a tree. How can we balance a tree? Don't. New trees (empty) are perfectly balanced, just make sure that no operation can unbalance a tree that is already balanced. two-three-trees, sort of animated. | ||||||
| Day off | 14th | |||||
| (assignment 4 has been set) Whatever test review is necessary. | ||||||
| First test day, A sample. Topics:
| ||||||
| Break | 26th to 29th | |||||
