EEN318 J (Algorithms) Autumn 2018
Mon, Wed, 5:00-6:15 in MM-200

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

Time/Date deadlines: Assignments must be submitted before midnight on the date due. After the due time, grades will be reduced to 90%, after another day 80%, after another day 73%, after another day 66%, then 60%, then 55%, then 50%. The maximum grade then stays at 50% until it is TEN days late, when it becomes worth ZERO.

1    Due Tuesday 4th September:
Just to make you remember how to program data structures.
2 Due Sunday 16th September
Hash table from named places file.
3 Due Monday 8th October
Building the graph of the national road network.
4 Due Sunday 28th October
A Fast Quicksort function for strings.
5 Due Monday 19th November
Find the shortest path.
6 Due Wednesday 5th December
A graphical presentation of your shortest path results.
7 Due Sunday 9th December
Parser and evaluator of expressions.
Last time for any submissions: 13th December

PC log in - use Putty or your own preferred SSH app.
Macintosh log in - use terminal and type ssh -oHostKeyAlgorithms=+ssh-dss username@rabbit.eng.miami.edu

Class History

Class 1  Mon 20‑8‑2018    Introductions and things.
Topics we will think about.
Special note for mac users.
Class 2  Wed 22‑8‑2018 Putting Peter Pan in a hash table, and dealing with clashes.
Class 3  Mon 27‑8‑2018 Two methods for handling hash clashes: closed/open hashing = open/closed addressing.
Completing our hash program and examining the disribution of linked list lengths.
The difference a bad hash function makes.
Class 4  Wed 29‑8‑2018 Comparing our results with the Poisson distribution, and what it tells us.
The int that can't be negated; Unsigned ints are deceptive and dangerous.
Named places Format, Data file.
String methods version 1, version 2.
Class 5  Wed 5‑9‑2018 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.
Building a graph,
Finding shortest paths by recursive (tree-like) exploration.
Class 6  Mon 10‑9‑2018 Recursively searching a graph can waste a lot of time reexploring the same areas.
Introducing the Priority Queue as a driver for the shortest path algorithm.
Class 7  Wed 12‑9‑2018 All about heaps as an implementation of priority queues.
Class 8  Mon 17‑9‑2018 Animated heap operations,
Animated shortest path algorithm,
Animated Heapsort,
Shortest path: record the heap index of every node.
The Floyd-Warshall algorithm.
Class 9  Wed 19‑9‑2018 Floyd-Warshall algorithm completed.
Using floating-point "infinity".
Finding a 'subset' with a particular sum.
Some more numbers.
Class 10  Mon 24‑9‑2018 intersections.txt, connections.txt, named-places.txt, The file formats.
Quicksort: the three partition (L, E, and G) method.
Class 11  Wed 26‑9‑2018 Quicksort: two more partition methods.
Methods for picking the pivot.
The first appearance of Quicksort: paper, algorithm part 1, part 2. The test system.
Animations: third partition method, complete quicksort.
Class 12  Mon 1‑10‑2018 Making your quicksort program self-testing,
The special timing function.
Quicksort on a linked list - does it make sense.
Class 13  Wed 3‑10‑2018 Mergesort on an array.
Class 14  Mon 8‑10‑2018 Radix sort and Bucket sort.
What might this file: mystery.dat contain?
Lots of iostream/fstream details.
Class 15  Wed 10‑10‑2018 All the tiles, and what they cover, and a rough diagram, and a basic viewer.
How might we store this file more efficiently.
And what about this one?
Class 16  Mon 15‑10‑2018 Review time: Hash tables, Priority queues, Shortest path, Heaps, Quicksort.
Class 17  Wed 17‑10‑2018 Test day. A sample.
Class 18  Mon 22‑10‑2018 Processing complex data input formats: custom input objects and lexical analysis.
Class 19  Wed 24‑10‑2018 Lexical analysis and the beginning of parsing.
Class 20  Mon 29‑10‑2018 Parsing expressions and statements
Class 21  Wed 31‑10‑2018 What we learned from the test.
Class 22  Mon 5‑11‑2018 Balanced trees:
Balancing a totally unbalanced tree is very inefficient. Keep it balanced from the start;
Introducing the 2-3-tree.
Class 23  Wed 7‑11‑2018 More on 2-3-trees, including a possible implementation,
Deleting from a 2-3-tree.
Class 24  Mon 12‑11‑2018 Normal Recursion,
Recursion Eliminated,
Stack replaced by Queue.
Class 25  Wed 14‑11‑2018 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  Mon 26‑11‑2018 More on Mergesort, binary files, and shortest path.
Class 27  Wed 28‑11‑2018 Second Test. Some assorted sample questions.
Topics: Fast sorting (but not quicksort), Binary files, Shortest path/priority queues.
Class 28  Mon 3‑12‑2018 Tying up some loose ends, and a bit of review.