| 1 | Due: Sat 30th August. Binary tree database with deletion. Remember the rules about what is not allowed. On top of that, no sstream. Also remember about efficiency: no unnecessary wasted effort. | |||||
| 2 | Due: Sat 13th September Interaction with a hash table of all named U.S. places. | |||||
| 3 | Due: Sat 4th October User guided step-by-step exploration of the road map. | |||||
| 4 | Due: Sun 9th November 2-3-trees with the red-black implementation trick. | |||||
| 5 | Due: Sun 23rd November Find the shortest route between two named places. | |||||
| Quick introductions. Review of Binary Trees. | ||||||
| Perfect binary trees Proving by induction that the recursive tree-printing function must work. Deleting from a tree, nodes with two children are the only complicated case. | ||||||
| The mystery function is a "hash function" - how hash functions should behave. Today's sample code: Overflow demonstration, Digital fingerprint for a whole file, Peter Pan word count. | ||||||
| Finding out the number of unique strings: split; sort; uniq -c Handle hash collisions/clashes with table entries being linked lists. Finding the distribution of linked list lengths (how many are of length X?). The Poisson distribution shows wht a perfect hash function would do. Comparing our hash to the ideal. | ||||||
| Day Off | Mon 1st Sept. | |||||
| back to last week for a moment: open/closed addressing/hashing. All officially named U.S. places, and the states. intersections.txt, connections.txt, the file formats. | ||||||
| A useful fact from topology: V + F - E - C = 0. 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. Graphs can be exlored as though trees if a closed set is used, if the closed set is implemented as a vector recursion is unnecessary. Introducing the "army of ants" method. | ||||||
| Implementing the army of ants: vector of objects each containing: place * A, * B; int length, progress. A & B are places joined by a road loop: each iteration every object's progress += 1 when progress == length note time of arrival at B, new objects for each exit. Important observation - simulation only cares about arrivals, any progress < length can be skipped. Min-heap: add new item with given prio, find and remove item with smallest prio. Implementations: Array/vector/linkedlist all have O(N) ops, tree won't be balanced. Array/vector impl of full tree ordered only so that prio(node) <= prio(left) and prio(right). Working through the operations, worst O(NlogN); seeing second half of heapsort. | ||||||
| HKN Resumé Workshop 22nd September,
Engineering Career Day on 25th September. Reminders about the importance of using pointers and references, and some of the less common parts of class definitions, and how to use the debugger. Hashing a pointer, finding the maximum int, and some more bit-wise operations. Tree-like shortest path in Nebraska. | ||||||
| A decorative but very bad program. Animated heap operations. Animated shortest path with a heap, Heap sort. The Floyd-Warshall algorithm. | ||||||
| Back to the two making-change problems, here's the blank table, Also the number of different possible frat parties. Memoisation - record all questions and answers so far computed to avoid repeated work, Dynamic programming - complete the table in advance of the questions, need to find a pattern. Usually find a recursive solution, if it involves repeated identical calls, try d.p. How Floyd-Warshall fits the pattern. | ||||||
| (Perhaps a wordier explanation of Floyd-Warshall will help). "Can it be done" questions can often solve the more useful "How do you do it" questions. Making change and knapsack are very similar. Connecting the recursive and D.P. solutions. Table for Maximal Sum Contiguous Subsequence, try to think of how to solve it. | ||||||
| Max sum contig. subs: brute force is cubic, easy improvement for quadratic, easy dynamic programming linear time solution, little realisation makes it constant space. Generating all combinations just in case there is no other way. Generating all permutations using tons of memory: loop, recursion. Sad attmept at a memory-efficient method. | ||||||
| The good way to generate permutations with comments to re-explain how it works. Easier to read without the explanation but harder to understand. The not very good way: with a loop, with a neat recursion. 2-3-trees, how they work in general, and seeing worst case time for 2-3 = best case time for binary tree, and time for search does not depend on configuration. | ||||||
| Mostly questions about the test, but some more about 2-3-tree insertions and node implementation. | ||||||
| First mid-term exam. Topics: Hash functions and hash tables, Graphs: constructing, searching, traversing, shortest path, Priority queues, Heaps and Heap-sort, Dynamic programming, 2-3-trees. Some sample questions, some are for the second test. | ||||||
| Day off | 13th | |||||
| Implementing 23nodes simple way wastes space and lots of cases to consider for insertion. How to colour a pointer. 234 trees are a logical possibility and easy to understand now, but would have more cases for insertion. Red-black trees are just an implementation trick for 23trees (really for 234trees). | ||||||
| Things to be learned from the test. Viewing the internal structure of numeric data. A mystery file, and viewing it with od. | ||||||
| Lots of things about fstreams. Binary chop search on a file, not in memory - good for giant files. The infamous file again, and finally seeing its contents. Making .bmp image files: makebmp.cpp, makebmp.h and makebmpdemo.cpp. | ||||||
| 23-tree and red-black representation: insertion and deletion in detail. | ||||||
| Python program for tree experiments - improved, works on latest python version now. | ||||||
| A program with nested recursion to be eliminated: a start. Here is the final result we reached right at the end. | ||||||
| Seeing the interruptible recursion when comparing trees, I think this is a better demonstration than you saw: see the short comment at the beginning. Processing complex structured input: making our own programming language, a start at least. | ||||||
| A more sophisticated and flexible way to make a lexical analyser. The next job is parsing: building a tree that represents the structure of a program: a beginning. This is roughly what we had at the end. | ||||||
| Where we got today with the language implementation: print. while, and { }. --------------------------------------------------------------- Here is the expanded tree experimenter python program, (here is the older version in case any of my improvements go wrong), This is how to install and run it, and this is a 23-tree diagram that you can load to get started. | ||||||
| Test review as necessary. The complete parser. | ||||||
| Second mid-term exam. Topics: 2-3-trees, Working with binary files, Recursion elimination, Parsing complex input, interpreters. The sample questions again, some are for the first test. | ||||||
| Remote class or special reading assignment. | ||||||
| Break | 25th to 30th | |||||
