1 | Due Wed 12th September. | ||||
Quicksort on Arrays. | |||||
2 | Due Fri 14th September. | ||||
Mergesort on Arrays. | |||||
3 | Due Thurs 4th October. | ||||
Place-Name and info Hash Table, and the data file. | |||||
4 | Due Thurs 18th October. | ||||
Fractal trees for video scene generation. | |||||
5 | Due Mon 12th November. | ||||
Part 1: coverage and data files,
file formats. Draw a nice map of the whole country, with a clearly visible dot at the correct location for each major town/city. | |||||
6 | Due Fri 30th November. | ||||
Part 2: An interactive virtual tour. | |||||
7 | Due Sun 9th December. | ||||
Part 3: Put it all together, find the shortest route between two places, draw a nice map, and print driving instructions. |
Class 1 | Thur 23‑8‑2012 | Quick introductions, etc. A proof that if sorting is based on comparing individual data items, it can not possibly be faster than O(N×logN). Counting sort, a sorting algorithm that is not based on comparisons. | ||||
Class 2 | Tue 28‑8‑2012 | Sorting by divide-and-conquer. From the recurrence
relations, seeing that when
the division is into halves, the time is O(N×logN). Mergesort is always O(N×logN), and Quicksort usually is. The recursive quicksort algorithm, and the up-down partitioning algorithm. | ||||
Class 3 | Thur 30‑8‑2012 | Debugging under unix Calculating the effect of a bad pivot. Quicksort as it first appeared, and implementation part 1, part 2, the test system. Student results from 2011. | ||||
Class 4 | Tue 4‑9‑2012 | The random thing, why library programmers like to avoid multiplication and division. Why bring the pivot to the front? Choosing the pivot: there is always a non-zero probability that quicksort will be quadratic. The other two partition methods. | ||||
Class 5 | Thur 6‑9‑2012 | Split and Merge for linked lists. Mergesort on arrays. Radix sort: linear, but slower than quicksort if you're sorting less than 20,000,000,000,000,000,000 ints. | ||||
Class 6 | Tue 11‑9‑2012 | Microsoft announcement. Hash functions: integer overflow on purpose. Hash tables, the high probability of failure due to collisions and coincidental birthdays. Linear probing can be a solution. | ||||
Class 7 | Thur 13‑9‑2012 | We are advised to read the manual. Evaluating linear probing. Keep the table between 25 and 50% full and you get an expected average constant time insert and search operations. Remember to resize the table by doubling and rehashing everything. | ||||
Class 8 | Tue 18‑9‑2012 | Chaining instead of probing (also known as Closed Addressing or Open Hashing), poisson graphs for good hashes Testing hash functions, and the negative that wouldn't go away. | ||||
Class 9 | Thur 20‑9‑2012 | Good ways to test a sort,
stdlib's qsort function. The mistake in htt.cpp, The complete hash test. Starting non-text "binary" file processing, C functions fopen, fclose, fread, fwrite. | ||||
Class 10 | Tue 25‑9‑2012 | Unsigned ints can be dangerous. More details of fopen, fgetc, fread, fseek, and their other friends and relations. Investigating binary files. | ||||
Class 11 | Thur 27‑9‑2012 | Filter programs with stdin connected to another program's stdout are useful. Good old printf can solve some of our problems, but C strings require some effort to use: The string.h library functions. | ||||
Class 12 | Tue 2‑10‑2012 | The discovery of America, packed into thousands of short ints. C++ isn't very good with two- (or more) dimensional arrays, sometimes you have to do it yourself. | ||||
Class 13 | Thur 4‑10‑2012 | fread and fwrite on structs for heterogeneous packed binary files, but
beware of added padding for address alignment. A map of an an annoying place to live. Vector methods. planning objects for the construction of a map data structure. | ||||
Class 14 | Tue 9‑10‑2012 | Practice with graphics, genetic engineering. An irregular quadrilateral, and making the computer draw it: picture. | ||||
Class 15 | Thur 11‑10‑2012 | Graphs, Lattices = Directed Acyclic Graphs, Trees, Linked Lists. Seven steps to a shortest-path algorithm: one, two, three, four, five, six, seven. | ||||
Class 16 | Tue 16‑10‑2012 | Recursion elimination, general and special cases. | ||||
Class 17 | Thur 18‑10‑2012 | Topics for the test. Comparing tree content: the recursion-eliminated tree printer can be stopped and started easily. Exploring Nebraska at night, developing a shortest path algorithm from a standard tree printing function, but it could be very inefficient. (a positive printable version of the map) | ||||
Class 18 | Tue 23‑10‑2012 |
Here is an ordinary stack of ints, and
here it has been made generic with templates. Here is an ordinary binary tree, with a recursive in-order print, And all the rest, pre-order, post-order, tree reconstruction, and reverse polish calculator. | ||||
Class 19 | Thur 25‑10‑2012 | Test Day. Older samples: 2007, 2009, 2010, but remember that the syllabus was updated not very long ago, so the older ones will be less useful, and the syllabus items are not always covered in the same order. | ||||
Class 20 | Tue 30‑10‑2012 | Announcement. A lattice (directed acyclic graph) to explore. Depth-first search (DFS), not recursive but driven by a stack, results in a lot of repeated exploration. Just change the stack into a queue, and Breadth-first search (BFS) is the result. BFS explores in layers, visiting everything that is N steps away before anything that is N+1 steps away. Finds shortest path quickly. | ||||
Class 21 | Thur 1‑11‑2012 | Lessons from the test. | ||||
Class 22 | Tue 6‑11‑2012 | Announcement. The distinction between concrete data types (given to you by the hardware or programming language, can't modify their behaviour, take it or leave it) and abstract data types (you know how you want them to behave, and must choose the concrete data types to implement them with), and the vague spectrum in between. Thinking about how to make an efficient Priority Queue for the shortest path algorithm. | ||||
Class 23 | Thur 8‑11‑2012 | Yet another announcement. Untidily removing something from a tree. Heaps for Priority Queues, and accidentally discovering HeapSort, another NlogN algorithm. | ||||
Class 24 | Tue 13‑11‑2012 | Heap review, adjusting priority. Sets, combinations: Boolean satisfiability. | ||||
Class 25 | Thur 15‑11‑2012 | Generating all combinations to solve the "Boolean satisfiability" problem. The same method gives an exponential solution to the "knapsack" problem, but dynamic programming yields a tractable solution. | ||||
Class 26 | Tue 20‑11‑2012 | Topics for the test.
A bunch of numbers. Inheritance, polymorphism, and run-time type identification. | ||||
Class 27 | Tue 27‑11‑2012 | Second Test. | ||||
Class 28 | Thur 29‑11‑2012 | Virtual methods, dynamic vs. static dispatch, dynamic casts: static, virtual, dynamic. |