EEN318 J (Algorithms) Autumn 2016
Mon, Wed, 5:00-6:15 in MM202

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 Fri 16th Sept:
Hash Tables.
2 Due Sun 2nd Oct:
Shortest path, part one.
3 Due Mon 7th Nov:
Shortest path, part two.
4 Due Sun 27th Nov:
Shortest path, part three.
5 Due Mon 5th Dec:
Empirically best mergesort.
6 Due Tue 13th Dec:
Final Graphical Shortest path.
7a Due Tue 13th Dec:
Optional - Solve this problem for 5 extra credit exam points.
7b Due Tue 13th Dec:
Optional - Solve this problem for 5 extra credit exam points.
Last time for any submissions: Thurs 15th December at noon.

Class History

Class 1  Mon 22‑8‑2016   Quick introductions, etc.
Maps as data structures, data.
As a reminder, the beginning, and a slight improvement (a static method).
Class 2  Wed 24‑8‑2016   Comparing the qualities of different implementations of the A.D.T. Map.
Investigating hash functions, digital fingerprints, and a superior map implementation.
Class 3  Mon 29‑8‑2016   Static members are useful too.
The birthday coincidence trick. Hash tables are the same. We will not be able to make a hash table for natural data that does not have clashes (two keys hashing to the same value).
Open Hashing = Closed Addressing, usually uses linked lists.
Closed Hashing = Open Addressing, usually using linear probing.
Class 4  Wed 31‑8‑2016   Hash tables with linked lists to render chashes harmless. Graceful degradation instead of catastrophic failure.
Empirical statistics, Theoretical statistics (old draft, lost original, this includes a subtle misstep).
Unisgned ints are deceptive and dangerous.
Named Places.
Class 5  Wed 7‑9‑2016   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.
Class 6  Mon 12‑9‑2016   The STL vector class.
Extending a class to add a new method.
A non-recursive but inefficient algorithm for finding the shortest path in a graph.
Class 7  Wed 14‑9‑2016   Depth first search with a stack, breadth first search with a queue, best first search with a priority queue.
Best first search to find the shortest path through a graph.
Special Friday at 4:30 Discussion/Help session, location t.b.a.
Class 8  Mon 19‑9‑2016   Shortest path using a priority queue demonstration.
The Floyd-Warshall Algorithm: all-to-all shortest paths in O(N3) by Dynamic Programming.
Building a square secret base. Brute Force is O(N5), dynamic programming is O(N3).
Class 9  Wed 21‑9‑2016   Some numbers.
Special Thursday at 3:30 Discussion/Help session, Music school like last time.
Class 10  Mon 26‑9‑2016   The final problem again, solving the integer knapsack problem with dynamic programming.
Exploring a "binary" (not human readable) data file.
Class 11  Wed 28‑9‑2016   Another mystery file: the discovery of America.
A lot of fstream operations.
named-places.txt, intersections.txt, connections.txt. The file formats.
All the map tiles, and what they cover, and a rough diagram with longitude and latitude.
Special Friday at 5:00 Discussion/Help session, Music school like last time.
Class 12  Mon 3‑10‑2016   A windows version of the graphical viewer.
Class 13  Mon 10‑10‑2016   Planned test review
Class 14  Wed 12‑10‑2016   Free-form review
Class 15  Mon 17‑10‑2016   Test Day.
Class 16  Wed 19‑10‑2016   Special notice for mac users.
More dynamic programming: selling logs, defeating space invaders, maximum sum contiguous subsequence.
Class 17  Mon 24‑10‑2016   What we (hope we) learned from the test.
numbers, starting a deeper examination of merge-sort.
Class 18  Wed 26‑10‑2016   All the way with mergesort, recursive vs non-recursive, at what size does it make sense to use a quadratic sort instead?
Class 19  Mon 31‑10‑2016   Heaps (mostly minheaps) - Add, Remove Smallest - ideal for priority queues, implementation as a full binary tree in an array saves all the space used by pointers.
Class 20  Wed 2‑11‑2016   Adjusting priority in a heap, the Heapable base type.
Quicksort in detail, the original partitioning algorithm.
Class 21  Mon 7‑11‑2016   The first appearance of Quicksort: paper, algorithm part 1, part 2, the test system.
Other partitioning algorithms.
To consider: Alphabet, and Enclosure.
Class 22  Wed 9‑11‑2016   Topological sorts and convex hulls.
2-3-trees - always perfectly (height) balanced.
Class 23  Mon 14‑11‑2016   IBM visit on Thursday.
2-3-trees - effective implementation methods, thinking about removing from a 23tree.
Class 24  Wed 16‑11‑2016   Deletion from a 2-3-tree.
Minimum edit distance.
Class 25  Mon 28‑11‑2016   Heap practice.
Plain old Heap practice (might not always stop correctly).
Diamond - D.P. practice.
Special Monday at 7:00 Discussion/Help session, Music school like last time.
Class 26  Wed 30‑11‑2016   Second Test.
Dynamic Programming; Quicksort, Mergesort, Heapsort; Heaps; 2-3-Trees.
Class 27  Mon 5‑12‑2016   Reviews, Practice, Questions, and Soothing Words.