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

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 5th September:
Just to make you remember how to program data structures.
2 Due Tuesday 10th October:
Hash Table of Named Places.
3 Due Friday 27th October:
Manually navigate the country.
4 Due Monday 4th December:
Find the shortest route.
5 Due Monday 11th December:
Sort race.
6 Due Thursday 21st December:
Final good-looking shortest path program.
Last time for any submissions: ???

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 21‑8‑2017    Introductions and things.
Topics we will think about.
Special note for mac users.
Beginning the tour: fast searching, hash tables, non-text data files.
Class 2  Wed 23‑8‑2017 Continuing the tour: DFS and BFS (maze, words),
shortest path, interesting algorithms, complexity, fast sorting, heaps,
OO in C++, recursion elimination, tree evaluation, bit operations.
Class 3  Mon 28‑8‑2017 Making a hash function and trying it out
Unix utilities sort, wc, grep; i/o redirection <, >, and pipe |
Starting to investigate the distribution of collisions.
Class 4  Wed 30‑8‑2017 We make a visual examination of hash value distribution for different table sizes.
The poisson distribution. The effect of a bad hash function.
The int that can't be negated; Unsigned ints are deceptive and dangerous.
Named places Format, Data file.
String methods version 1, version 2.
Wed 6‑9‑2017 XXX
Mon 11‑9‑2017 XXX
Wed 13‑9‑2017 XXX
Mon 18‑9‑2017 XXX
Wed 20‑9‑2017 XXX
Class 5  Mon 25‑9‑2017 About the second assignment.
Classes used in a hash table implementation.
Time vs Memory is the big trade-off.
Monitor the fullness of an HT as it grows, resize (by rehashing everything) when too full,
Just why we double the size (of vectors too).
Class 6  Wed 27‑9‑2017 Open Hashing/Closed Addressing or Closed Hashing/Open Addressing.
Introducing the Floyd-Warshal shortest path algorithm.
Class 7  Mon 2‑10‑2017 F-W finds lengths shortest paths from everywhere to everywhere in cubic time,
but given the lengths, the paths themselves are very easy to construct.
main.cpp, intmatrix.h, intmatrix.cpp, citytable.h, citytable.cpp.
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 8  Wed 4‑10‑2017 Calling a destructor accidentally, and how to avoid it.
Making use of the IEEE-754 infinity.
intersections.txt, connections.txt, named-places.txt, The file formats.
Class 9  Mon 9‑10‑2017 Implementing sparse arrays.
A good data structure for our road map.
Imagine the map is just a tree: finding shortest paths is easy.
One small change makes it work for DAGs and general graphs, but not very efficiently.
Class 10  Wed 11‑10‑2017 Solving shortest path by simulating an army of ants.
The Priority Queue and a more direct solution.
Introducing Heaps as a priority queue implementation.
Class 11  Mon 16‑10‑2017 Big example: watch the priority queue as shortest path is solved.
A Heap is a good PQ implementation - Heap operations demonstrated.
Heaps can be efficiently implemented in arrays - no tree pointers at all.
Class 12  Wed 18‑10‑2017 Constructing a usable graph from input files.
Heap operations in concrete detail.
Discovering heapsort and that it is O(NlogN).
Class 13  Mon 23‑10‑2017 The last piece of the puzzle - Adjusting the Heap
Thinking about what mystery.dat might contain,
and how we might store this file more efficiently.
Class 14  Wed 25‑10‑2017 Lots of iostream/fstream details.
Compressing data quite a bit, and a bit further.
All the tiles, and what they cover, and a rough diagram, and a basic viewer.
Class 15  Mon 30‑10‑2017 Finally compressing the weather data file, and
now Binary Chop search on a file.
Class 16  Wed 1‑11‑2017 First Test. a sample.
Class 17  Mon 6‑11‑2017 Facebook wants you!
Merge-sort in depth, part 1: on linked lists, and why we need an extra array when sorting an array.
Class 18  Wed 8‑11‑2017 Merge-sort in depth, part 2: on arrays.
Radix sort too.
Class 19  Mon 13‑11‑2017 Quick-sort:
A popular partitioning method. The whole algorithm.
The first appearance of Quicksort: paper, algorithm part 1, part 2.
Class 20  Wed 15‑11‑2017 More quicksort; more partitioning methods, loop invariants and variants; optimisations.
Class 21  Mon 27‑11‑2017 Counting sort
2-3-trees: the idea, searching, and inserting.
Class 22  Wed 29‑11‑2017 More 2-3-trees.
Class 23  Mon 4‑12‑2017 Deleting from a 2-3-tree with pictures.
Class 24  Wed 6‑12‑2017 Second Test. A sample from last year.
Class 25  Mon 11‑12‑2017 Practise with various things.
Class 26  Wed 13‑12‑2017 Final Examination, all make-ups.
Class 27  Mon 18‑12‑2017 table, an introduction to dynamic programming and greedy algorithms.
Class 28  Wed 20‑12‑2017 Some reminders:
Polymorphism 1, 2a, 2b, 3a, 3b, 4;
a vector, with templates.
A little quiz.