EEN318 J (Algorithms) Autumn 2020
Mon, Wed, 5:05-6:20 in LC-180

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
The subject must be: YOUR NAME, ECE318, ASSIGNMENT N
(where N is the assignment number of course.)

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. 6 Sept.
More tree operations.
2 Due: Tue. 29 Sept.
Named places hash table.
3 Due: Sun. 25 Oct.
Manually exploring the national road network.
4 Due: Sun. 15 Nov.
Find the shortest path by road.
5 Due: Fri. 4 Dec.
Graphical display of your 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 17‑8‑2020   Quick introductions.
Reminders about tree operations.
Class 2  ‑ Wed 19‑8‑2020 Deleting from a tree and balancing an unbalanced one
(The animated tree app to try things out).
Class 3  ‑ Mon 24‑8‑2020 Inventing the hash table: what could go wrong?
Class 4  ‑ Wed 26‑8‑2020 Diagram of a hash table.
The poisson distribution.
How a hash function can be bad, and how we'd know.
Named places Format, Data file.
String methods version 1, version 2.
Class 5  ‑ Mon 31‑8‑2020 The int that can't be negated.
The dangers of using unsigned ints.
Alternative scheme for a hash table: Linear probing = closed hashing = open addressing.
The abstract data type Dictionary.
Typed notes from today.
Class 6  ‑ Wed 2‑9‑2020 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 exploration methods.
Class 7  ‑ Wed 9‑9‑2020 Using a queue to explore a graph.
Inventing the priority queue.
A Min-Heap as an implementation of a priority queue.
Today's scratchy notes.
Class 8  ‑ Mon 14‑9‑2020 Heaps: major operations.
Animated heap operations.
Discovering heap-sort.
Class 9  ‑ Wed 16‑9‑2020 The heap-sort algorithm.
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 idea of an adjacency matrix.
Class 10  ‑ Mon 21‑9‑2020 The Floyd-Warshall algorithm.
The Floyd-Warshall algorithm in C++.
Using floating-point "infinity".
How many subsets of R things from a collection of N, by Dyanmic Programming.
Class 11  ‑ Wed 23‑9‑2020 Finding a 'subset' with a particular sum.
Some more numbers.
Todays notes.
Class 12  ‑ Mon 28‑9‑2020 Number of paths in a grid
Cutting a plank of wood optimally
Number of ways of making change
Today's notes.
Class 13  ‑ Wed 30‑9‑2020 Review day.
Class 14  ‑ Mon 5‑10‑2020 Test day, A sample.
Class 15  ‑ Wed 7‑10‑2020 Merge-sort on an array, part one.
Class 16  ‑ Mon 12‑10‑2020 Merge-sort on an array, part two.
Quicksort methods, part one.
Class 17  ‑ Wed 14‑10‑2020 The first appearance of Quicksort: paper, algorithm part 1, part 2. The test system.
Animations: third partition method, complete quicksort.
The three-way partitioning method.
Quicksort on a linked list.
Class 18  ‑ Mon 19‑10‑2020 Processing binary files:
The mystery file - processing binary files.
Lots of iostream/fstream details
Today's notes,
Today's sample program.
Class 19  ‑ Wed 21‑10‑2020 Eliminating recursion:
Original recursive version,
Using a stack of activation records,
With a queue replacing the stack.
Class 20  ‑ Mon 26‑10‑2020 depth and breadth first traversals of a tree.
saving and reconstructing a tree.
Class 21  ‑ Wed 28‑10‑2020 Examining the balance of a random binary tree.
Introducing the 2-3-tree.
Class 22  ‑ Mon 2‑11‑2020 What we learned from the test, and the solutions.
Binary files: today's notes.
Class 23  ‑ Wed 4‑11‑2020 Preparation for dynamic programming, binary files, recursion elimination, breadth-first search.
Today's notes.
Class 24  ‑ Mon 9‑11‑2020 Second Test. Some assorted sample questions.
Possible topics: mergesort, quicksort, binary files, recursion elimination, breadth/depth first search, dynamic programming.
Class 25  ‑ Wed 11‑11‑2020 A basic input system,
and a lexical analyser.
What we had at the end of class.
Class 26  ‑ Mon 16‑11‑2020 The final version of our programming language interpreter
testfile.txt, its input file.
Class 27  ‑ Wed 18‑11‑2020 Test one, test two. No new question.