EEN318 R (Programming 3) Autumn 2012
Tues, Thurs at 2:00 pm in MM113

Policies, rules, etc.

The Book

Examinations:

Assignments

     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 History

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.