| 1 | Due Thurs 3rd September: A tree, just to get you back in the swing of things. | ||||||
| 2 | Due Wed 30th September: Geographical Hash Table. | ||||||
| 3 | Due Wed 28th October: Map Display. | ||||||
| 4 | Due Wed 4th November: Integrate geographical hash table and map drawer. | ||||||
| 5 | Due Wed 18th November: Question 2 from the test. | ||||||
| 6 | Due Wed 9th December: Mergesort an array of people. | ||||||
| 7 | Due Wed 16th December: Full shortest road-trip program. | ||||||
| Last day for any submissions: Thur. 17th December. | |||||||
| Class 1 | Tue 25‑8‑2015 | Quick introductions, etc. Reconsidering the choices of data structure and algorithm available for fast retrieval from a simple database. Reminders of some C++ things: ints being faster to work with than strings, the different varieties of int, etc. | ||||
| Class 2 | Thur 27‑8‑2015 | Discovering hash functions and digital fingerprints:
first exploration. Second step: how common are clashes? Will we be lucky? (use of the debuger, /home/www/ replaces the beginning of a URL) | ||||
| Class 3 | Tue 1‑9‑2015 | Chaining together little utilities to do significant things; how carelessly written hash functions can be really bad; the mysterious int that can't be negated; more experiments. | ||||
| Class 4 | Thur 3‑9‑2015 | A serious implementation of a hash table, where clashes are not a problem, but
good distribution is still vital. The poisson distribution used to check the
quality of the hash function. The final version: I have found the mistake, but I've left this unchanged so you can try the challenge of correcting it. | ||||
| Class 5 | Tue 8‑9‑2015 | Graphs of many hash table fullness experiments. That, plus some mathematics, show that the ideal hash table has a λ (fullness) somewhere between 0.5 and 1. Working out that when resizing a vector, adding to the size is not very good, but multiplying the size (typically by 2) gives excellent performance. The same can be done to a hash table to keep its λ in the ideal range. A bunch of places to put into a hash table. | ||||
| Class 6 | Thur 10‑9‑2015 | Open Hashing = Closed Addressing, usually uses linked lists. Closed Hashing = Open Addressing, usually using linear probing. All the tricks that fstreams can do. another file. Creating an empty hash index file. Reading the names that will eventually go into it. | ||||
| Class 7 | Tue 15‑9‑2015 | Creating and Searching a hash-table indexed disc file (using closed hashing). | ||||
| Class 8 | Thur 17‑9‑2015 |
named-places.txt,
intersections.txt,
connections.txt.
The file formats. All the map tiles, and what they cover. | ||||
| Class 9 | Tue 22‑9‑2015 | Google event announcements: one, two. Finding the shortest/only path through a tree text, picture | ||||
| Class 10 | Thur 24‑9‑2015 | Map Two text, picture, backwards. It's a lattice
(directed acyclic graph), but the same algorithm sort-of works. Except that it just finds a path, not necessarily the shortest one. We produce a breadth-first search by eliminating the recursion and replacing the stack with a queue. | ||||
| Class 11 | Tue 29‑9‑2015 |
Normal Recursion, Recursion Eliminated, Stack replaced by Queue. | ||||
| Class 12 | Thur 1‑10‑2015 | Map Three text, picture. Now the edges have weights. Nebraska, at night. | ||||
| Class 13 | Tue 6‑10‑2015 | The map and grid for the cubic "all pairs" shortest path method. | ||||
| Class 14 | Tue 13‑10‑2015 | Potential test day. | ||||
| Class 15 | Thur 15‑10‑2015 | Actual test day. | ||||
| Class 16 | Tue 20‑10‑2015 | Floating point "infinity", and evading the optimiser. Very special trees for programming languages. | ||||
| Class 17 | Thur 22‑10‑2015 | Adventures with expressions, split up into separate files for readability: token.h, token.cpp, lexan.h, lexan.cpp, node.h, node.cpp, hashtable.h, hashtable.cpp, mainprogram.cpp. how to compile and run it if you want to. | ||||
| Class 18 | Tue 27‑10‑2015 | Better structure: world.h, parse.cpp, evaluate.cpp, prog.cpp. | ||||
| Class 19 | Thur 29‑10‑2015 | Better structure:
world.h,
parse.cpp,
evaluate.cpp,
prog.cpp. Delegation to a prototype object is an alternative to inheritance of a class, but not in C++. Longjmp and setjmp used to handle errors in world.h and evaluate.cpp. Make = and ; be very low priority operators, and you've got something you can program. | ||||
| Class 20 | Tue 3‑11‑2015 | Grammars and languages, evaluating expressions on the fly. | ||||
| Class 21 | Thur 5‑11‑2015 | Mergesort on arrays. Quicksort's partitioning. | ||||
| Class 22 | Tue 10‑11‑2015 | Three different partitioning methods. The importance of the selection and positioning of the pivot. The first appearance of Quicksort: paper, algorithm part 1, part 2, the test system. | ||||
| Class 23 | Thur 12‑11‑2015 | Radix sort, in special cases can be faster than NlogN. Useful tricks with the bitwise operators: bit-arrays (or bitvectors) and such. | ||||
| Class 24 | Tue 17‑11‑2015 | Heaps. Logarithmic insertion and removal, no memory overhead. Heapsort: worst case NlogN time and constant memory. Heaps make priority queues. | ||||
| Class 25 | Thur 19‑11‑2015 | The nature of C++'s object-orientedness: inheritance, protected/private, virtual
methods, static vs dynamic typing, polymorphism. Our starting point, 2a, 2b, 3a, 3b, the type-cast problem. | ||||
| Class 26 | Tue 1‑12‑2015 | Second Test. | ||||
| Class 27 | Thur 3‑12‑2015 | dynamic typecasts, base class, derived class, inhertiance, polymorphism, static dispatch, dynamic dispatch, virtual method (size of object bigger), pure virtual. | ||||
| Review | Sat | Saturday 5th at 12 noon. In EB 216 or 237 or 304. It will be made easy to find. | ||||
| Class 28 | Tue 8‑12‑2015 | Override, overload, default constructor, operator=, copy constructor, the trouble with shallow copies,
interface, empty interface, static const. The sample for today. | ||||
| Final | Thur 10‑12‑2015 |
|
