EEN318 J (Algorithms) Autumn 2019
Mon, Wed, 5:05-6:20 in MM-202

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 ecegrader at gmail.com

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: Sun 1st September
Just to make you remember how to program data structures.
2 Due: Wed 18th September
Named places in a hash table.
3 Due: Sat 2nd November
Exploring the national road network.
4 Due: Thur 14th November
Finding the shortest path by road.
5 Due: Sun 1st December
Implement an AWT similar to the one studied in classes 19 and 20.
6 Due: Sun 8th December
Graphical display of your shortest path results.

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

Class History

Class 1  ‑ Mon 19‑8‑2019   Quick introductions.
Topics we will cover,
Special note for Mac users.
Today's experiment with random access file input.
Class 2  ‑ Wed 21‑8‑2019 Binary chop search on a text file,
Our first experiment with a hash table.
Class 3  ‑ Mon 26‑8‑2019 A much better hash table, resolving clashes with linked lists.
Class 4  ‑ Wed 28‑8‑2019 A statistics gathering hash table.
Class 5  ‑ Wed 4‑9‑2019 The Poisson distribution, good and bad hash functions,
The int that can't be negated.
Class 6  ‑ Mon 9‑9‑2019 Named places Format, Data file.
String methods version 1, version 2.
Class 7  ‑ Wed 11‑9‑2019 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.
Recursive methods for graph exploration.
Class 8  ‑ Mon 16‑9‑2019 Exploring a graph recursively,
Looking for the shortest path with a priority queue.
Class 9  ‑ Wed 18‑9‑2019 The min-heap data structure and its algorithms:
add an item, remove the smallest.
Animated heap operations,
Animated heapsort.
Class 10  ‑ Mon 23‑9‑2019 Shortest path with a min-heap,
Animated shortest path with a heap.
Building a graph from the geographical files,
    intersections.txt,
    connections.txt,
    named-places.txt,
    The file formats.
The Floyd-Warshall algorithm.
Class 11  ‑ Wed 25‑9‑2019 More Floyd-Warshall,
Using the CPU's concept of infinity,
Details of quicksort,
A partition method animated,
Complete quicksort animation.
Class 12  ‑ Mon 30‑9‑2019 More on the heap algorithms,
File operations: sorting on disc.
Class 13  ‑ Wed 2‑10‑2019 Test day.
Class 14  ‑ Mon 7‑10‑2019 Quicksort, the original publication, selecting pivot, on a linked list.
Radix sort.
Class 15  ‑ Wed 9‑10‑2019 The mystery file - processing binary files.
Lots of iostream/fstream details
Class 16  ‑ Mon 14‑10‑2019 Eliminating recursion, using a stack of activation records.
What happens if we use a queue instead?
Normal recursion,
Recursion eliminated,
Stack replaced by queue.
Class 17  ‑ Wed 16‑10‑2019 Serializing and reconstructing graphs and trees.
Class 18  ‑ Mon 21‑10‑2019 What we learned from the test.
Use a queue for shortest path when all arcs have the same cost.
Class 19  ‑ Wed 23‑10‑2019 The design of an Abstract Windows Toolkit.
Class 20  ‑ Mon 28‑10‑2019 Details of the AWT case study.
Rebalancing an unbalanced tree - very inefficient.
Class 21  ‑ Wed 30‑10‑2019 The 2-3-tree, always balanced automatically.
Class 22  ‑ Mon 4‑11‑2019 Deleting from a 2-3-tree.
Class 23  ‑ Wed 6‑11‑2019 Processing complex inputs through lexical analysis, parsing, and interpretation.
A simple interpreter.
Class 24  ‑ Mon 11‑11‑2019 A basic input system,
and a lexical analyser.
Class 25  ‑ Wed 13‑11‑2019 review of 2-3-trees and recursion elimination.
Class 26  ‑ Mon 18‑11‑2019 Second test.
Class 27  ‑ Wed 20‑11‑2019 Parsing programs.
Break
Class 28  ‑ Mon 2‑12‑2019 Here is the complete language processing program,
and a test input file for it.