| 1 | Due: Saturday 2nd September Tree database with deletion. | |||||
| 2 | Due: Saturday 16th September Put all the named places in a hash table. | |||||
| 3 | Due: Friday 20th October An on-disc hash table for compressed named places. | |||||
| 4 | Due: Saturday 11th November Exploring the map of the United States manually. | |||||
| 5 | Due: Saturday 18th November Automatically finding the shortest path through the map. | |||||
| 6 | Due: Saturday 2nd December Subset sum by two different methods. | |||||
| Introductory Bits. Removing data from a binary tree without ruining the balance. The essential take-aways from today's class. | ||||||
| New accounts all added. Username = UM email before @, new passwords = C number with capital C. Announce assignment. Stringstreams: iss0.cpp, iss.cpp. The basic unadorned original hash function, Digital fingerprints, An almost correct hash table. The essential take-aways from today's class. | ||||||
| Hundreds of hippopotamusses in Peter Pan - we had clashes. Resolving clashes - buckets are linked lists. Useful little utilites, wc, sort, uniq: getting an accurate word count. Graphs of the Poisson distribution. How hash functions can go bad. Checking our distribution against the ideal. Keeping the fullness in a good range, efficiently resizing a hash table. The dangers that unsigned ints can cause. Why we always double (or at least multiply) the size when enlarging vectors and hash tables. The essential take-aways from today's class. | ||||||
| All named U.S. places, and the states. strtod and strtol from cstdlib, use old C strings. String methods. 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 out whether a path exists or not, recursion works if we remember where we've been. Finding length of a path recursively too, return float, -1.0 for failure. The essential take-aways from today's class. | ||||||
| The recursive algorithm. circular struct definitions, Reading and creating the internal representation of the map, all places in a hash table. Use a vector to record roads followed and places visited. Keep track of distance so far, save the vectors for the best solution yet. A queue would be very much more efficient than the recursive search, but it requires that all roads have the same length. The essential take-aways from today's class. | ||||||
| Important things for assignments. Examples of some less used C++ features. Exceptions: one, two, three. The essential take-aways from today's class. | ||||||
| (No video on today's zoom recording, rear camera not working, I reported it). Save order for a tree - prefix and rebuild. Simulated ants, don't really care where they are most of the time. The Priority Queue ADT, considering various implementations. The min-heap, full binary tree, only top-to-bottom ordering. Min-heap in an array (or vector), no need for pointers. Heaps: major operations review. The essential take-aways from today's class. | ||||||
| (No video on today's zoom recording, rear camera not working, I reported it again). Special heapable objects, not so great for this: index, prio, and node. Animated heap operations. Animated shortest path with a heap, Discovering heap-sort. The essential take-aways from today's class. | ||||||
| The Floyd-Warshal algorithm. A Mysterious File. Lots of details about iostream/fstream. The essential take-aways from today's class. | ||||||
| A bit about how binary files reduce data size and speed up retrieval. Making a binary file from the named places text file. Binary chop search on a binary disc file. The essential take-aways from today's class. | ||||||
| First test date. Updated HKN tutoring times. Compressing a string: .cpp and .h How would we make a disc-based hash table? ISAM too Decoding the mystery file. The essential take-aways from today's class. | ||||||
| The essential Unix commands and pico/nano editor controls,
and the vim cheat sheet. Separate compilation reminder. Probabilistic methods do a better job of compressing strings. A slightly different way to construct a tree, and why it is useful. A reminder about stack frames or activation records. Recursion elimination. The essential take-aways from today's class. | ||||||
| Back to recursion elimination. And a self-tracing version for educational purposes. What happens if the stack is replaced with a queue? Something this is useful for: the build-up, and the real thing. In simple cases, we don't need to go to all the trouble of creating activation records: stack, and queue. Depth-first with iterative deepening is usually better than a queue. Quick introduction to an up-coming topic via "how many ways can I give change for N cents?" The essential take-aways from today's class. | ||||||
| Review for the test for as long as is needed. | ||||||
| First test day, A sample. Topics:
| ||||||
| Completing the which coins question:
plain,
traced,
complete,
memo,
dynamic. Only a limited number of possible questions but it takes a long time anyway. Memoisation - make sure you never ask the same question twice. Leads to the more elegant style of Dynamic Programming - solve all possible problems first. The knapsack or subset sum problem. The essential take-aways from today's class. | ||||||
| More words on assigment 3. The "brute force" solution to the knapsack problem. The combinatoric function C(n, r) by dynamic programming. How many shortest paths in a regular grid? by d.p. again. The essential take-aways from today's class. | ||||||
| Exploring the natural balance of a binary tree. For most N there is no perfectly balanced binary tree. Introducing the 2-3-tree, how to search it and how to add new data to it. How to implement those 2-3-tree algorithms. The essential take-aways from today's class. | ||||||
| Issues that arose from the first mid-term. Things about the 4th assignment: the file formats and intersections.txt and connections.txt. | ||||||
| Deletion from a 2-3-tree, the easy parts. Persistent data structures. Saving linked data structures to a file. The essential take-aways from today's class. | ||||||
| A different 6th assignment than I had originally planned. Deleting from a 2-3-tree, the whole thing. A more object-oriented style, a binary tree in Python. Reinforcing some O.O. things: ok to start, but not ok here. Five minutes introducing the next topic. The essential take-aways from today's class. | ||||||
| Dealing with complex input: proper expressions or even programs. Separate stages and separate little functions for parsing are essential. And a quick look at some unfortunate aspects of C and C++'s syntax. Where we got to today. The essential take-aways from today's class. | ||||||
| Parsing all the different kinds of statements is easy for a cleanly designed language. Then dealing with operator priorities requires a clever idea. This is where we got, after adding a step that we didn't have time for. The essential take-aways from today's class. | ||||||
| Pre-test review. Be prepared with questions and topics. | ||||||
| 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. 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 99 on blackboard. | ||||||
| Second mid-term, the possible topics are: Heap sort, Exploring or shortest path in a graph other than by breadth first search, Woring with files, both text and binary, Simple dynamic programming problems, and Recursion Elimination. Samples: an assortment of questions, and an old test, ignore quicksort and mergesort. | ||||||
| Dealing with priorities actually involved restructuring the rules. Finishing parsing, and now actually executing our programs: our little programming language completed. Fast to-the-power-of-int and the seive or Eratosthenes. | ||||||
| What we should learn from the test. B-trees and B+-trees, especially designed for storage on disc. A little bit about 2-3-4-trees and red-black trees. I looked it up, 2-3-trees were invented in 1970, red-black in 1978, so it is the 2-3's that deserve the credit. |
