EEN318 T (Algorithms) Autumn 2014
Mon, Wed 5:00-6:15 in MM-203

The Book

Examinations:

Assignments

Email as a single readable document, your code, any important information, and a demonstration that it runs (e.g. screenshot) to grader318 at rabbit.eng.miami.edu
1      Due Wed 3rd September.
A tree, just to get you back in the swing of things.
2 Due Sat 27th September.
Self-sizing case-insensitive object-oriented hash table.
3 Due Thurs 30th October.
Geographical map display.
4 Due Thurs 20th November.
Your own private quicksort-mergesort race.
5 Due Thurs 4th December.
Make an AVL tree.
6 Due Sat 13th December.
Final shortest path, integrated with assignments 2 and 3.
Deadline: Nothing (except final project) can be accepted for grading after Sunday 14th.

Class History

Class 1  ‑ Mon 25‑8‑2014   Quick introductions. Reminders about how to do things in unix. Don't forget to use the "man pages".
Class 2  ‑ Wed 27‑8‑2014 C++ documentation, thoughts about case-insensitive comparisons, ctype.h
Remembering trees, the importance of a tree being well balanced, coming up with a usable definition of well balanced, and wondering how to solve the important recurrence relation Min(0) = 0; Min(1) = 1; Min(s) = 1 + Min(s-1) + Min(s-2).
Class 3  ‑ Wed 3‑9‑2014 Experimenting with a hash function: getting the basic idea. Trying to avoid clashes (two words with same hash value) but not quite getting the right experiment. Also getting useful help from gdb the debugger.
Class 4  ‑ Mon 8‑9‑2014 Quick trick to count the unique words in a text file.
Expanded Hash Experiment, really measuring the occurrences of hash table clashes.
Class 5  ‑ Wed 10‑9‑2014 Gathering better statistics, random but guaranteed unique strings,
gathering those statistics, and what they tell us.
The terrible number that can't be negated.
Class 6  ‑ Mon 15‑9‑2014 Dealing with the unnegatable int, the unsigned int type and how it can be dangerous.
Open addressing = closed hashing (using linear probing) compared to closed addressing = open hashing (using linked lists).
Using the Poisson distribution to test the quality of a hash function.
Looking at data in its internal binary format, big endian and little endian representations.
Class 7  ‑ Wed 17‑9‑2014 stdio.h's fopen, fgetc, fputc, and fclose for anything's-possible file processing.
C++'s fstream can do it too, sometimes more friendlily.
Bitwise operations and the strange trick for seeing binary representations.
places
Class 8  ‑ Mon 22‑9‑2014 tellg, tellp, seekg, seekp: added to yesterday's notes.
named-places.txt, intersections.txt, connections.txt. The file formats.
All the map tiles, and what they cover.
The heirarchy of structures: linked list, tree, graph.
Starting to think about searching a graph. Maybe a recursive tree search can be adapted....
Class 9  ‑ Wed 24‑9‑2014 pos_type, time_t, etc.
Nebraska, at night,
The first shortest path algorithm, based on a recursive tree search with the addition of a been_here flag in each node to avoid loops.
An identically functioning non-recursive version using our own stack of "reminder"s.
Class 10  ‑ Mon 29‑9‑2014 Microsoft visiting 7th - 8th October: notice one, notice two.
Stack-based shortest path algorithm, must try every possible path from A to B in order to find the shortest, save the stack on each arrival.
Distanceless map: Queue-based shortest path algorithm, very fast - only visits each place once, but only works when all roads are the same length.
Priority Queue based algorithm: we need a good implementation of one.
Class 11  ‑ Wed 1‑10‑2014 Short demonstration of graphics programming.
Examination of various possible implementations of a Priority Queue, which is essential for an effective shortest path algorithm.
Introducing the Heap.
Class 12  ‑ Mon 6‑10‑2014 Definitions of heaps and related things.
A binary min heap turns out to be a particularly good design for a priority queue.
One particular concrete implementation of a binary min heap, using only a single array for data.
Working through the algorithms for adding and removing items.
Class 13  ‑ Wed 8‑10‑2014 The heap algorithms in detail. Ways to make them really efficient.
Discovering Heapsort, a very reliable O(NlogN) sorting algorithm, as a result.
Class 14  ‑ Mon 13‑10‑2014 Considerations in getting the most speed out of your algorithm implementations: Registers - CPU cache - main memory ("ram") - pages on disc. Locality of Reference makes a difference, and with linked lists there is none. New and delete are not slow, but they do take some time. Quicksort does require O(log N) extra space, but that is nothing. A quick reminder of mergesort for linked lists.
Class 15  ‑ Wed 15‑10‑2014 Review day.
Class 16  ‑ Mon 20‑10‑2014 Test Day. Topics to be ready for.
Class 17  ‑ Wed 22‑10‑2014 Full examination of merge-sort on arrays: starting point, and the ending point.
Class 18  ‑ Mon 27‑10‑2014 Quick-sort on arrays: all the work is in splitting so that merge doesn't have to be done.
The first partition algorithm.
Class 19  ‑ Wed 29‑10‑2014 A magnetic tape drive, and a computer room.
Quicksort as it first appeared, and implementation part 1, part 2, the test system.
All sorts of other partitioning methods.
Class 20  ‑ Mon 3‑11‑2014 Improving the performance of a binary tree: how can we possibly get it balanced?
Class 21  ‑ Wed 5‑11‑2014 AVL trees, and Average performance for a plain binary tree.
Class 22  ‑ Mon 10‑11‑2014 2-3-trees and their perfect balance, red-black trees as an implementation, and generalising to 2-3-4-trees.
Class 23  ‑ Wed 12‑11‑2014 Inheritance, public, protected, private, polymorphism, virtual, and so on in an example.
Safe typecasts.
Class 24  ‑ Mon 17‑11‑2014 More constructors and destructors. Assignment and the copy constructor (initialisation) is not the same thing as assignment) can both be redefined for any class. The shallow copying done by default causes great trouble when there is a destructor, so ALWAYS make object parameters be references (no copying) if the object conatins anything created by new. Pure virtual methods as guarantors of functionality.
See how we can make a function that can sort arrays of any kind of object.
See the mysterious errors at the end when we don't use a reference parameter for an object (print is the function of interest).
Class 25  ‑ Wed 19‑11‑2014 Review day with Paul.
Break
Class 26  ‑ Mon 1‑12‑2014 Test Day.
Class 27  ‑ Wed 3‑12‑2014 Deletion from trees, and the beginning of a useful algorithm.
Class 28  ‑ Mon 8‑12‑2014 A serious look at some dynamic programming.
Sun 14‑12‑2014 Last day anything (except for final project) can be accepted for grading.
Mon 15‑12‑2014 Voluntary pre-final review, in the 118 lab room, 5 p.m.
Wed 17‑12‑2014 The final.