| 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). | |||||
| 5 | Due: Wednesday 20th November Implement a 2-3-tree, here are the deletion worksheets again. | |||||
| 6 | Due: Friday 6th December (very strict) Extend assignment 3 to find the shortest path efficiently, print driving instructions and graphically display the route. | |||||
| 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: makebmp.cpp, makebmp.h and makebmpdemo.cpp. 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:
| ||||||
| 2-3-trees, properties and building them, a first picture. | ||||||
| Insertion into a 2-3-tree, all the details. | ||||||
| Complete analysis of insertion and search time: best case for 23tree = best case for binary tree, worst case for 23tree = 1.06 × best case for binary tree. Tricks for implementation and the red-black tree's embarrassing secret. | ||||||
| What exactly is structured programming? What does unstructured programming look like? Why is it bad? Deletion from a 2-3-tree, and the worksheets | ||||||
| B-trees and B+-trees. A perfectly ordinary program with recursion, and we get rid of it. | ||||||
| The non-recursive program we had at the end on Wednesday, the same without the unnecessary position. A thoughtless attempt to replace the stack with a queue, That working; to use a queue, each function must remain separate. Handling complex structured input, our target, a precise specification. | ||||||
| More on the propagation and elimination of back holes. Back to handling complex input: the stages to come. Stage one, Stage two. We got as far as p_value (first parsing function) but know what the others have to produce. | ||||||
| Pre-test review. Completing the almost-good-enough parsing of our small programming language. This is the code. I added some trivial extras. | ||||||
| Second mid-term. Possible topics: hash tables, binary files, 2-3-trees, recursion elimination. | ||||||
| A special reading assignment. Make sure you understand the "Estimate of time taken" section, starting on page 11 and ending at the end of page 12. With totally different words, phrasing, and style explain why NlogN is the best possible. And what is a Nest? What is it doing? What would we call it today? What would we use instead? Answer those three questions and submit your answers as assignment number 7 on blackboard. | ||||||
| Break | 26th to 29th | |||||
| A little bit about converting between RGB and HLS colour descriptions. And the end of the little language implementation. | ||||||
