ECE318 J (Algorithms) Autumn 2021
Mon, Wed, 5:05-6:20 in MM 203

The Book

Examinations:

Assignments

Email as a single readable document, your code, any important information, and a demonstration that it runs (e.g. text capture or screenshot) to 318grader at rabbit.eng.miami.edu
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: Sat 3rd September.
More tree operations.
2 Due: Sat 24th September.
Hash table for finding "named places".
3 Due: Sat 22nd October.
Interactively exploring the road network.
4 Due: Wed 9th November.
Find the shortest path.
5 Due: Sun 4th December.
Graphical shortest path program.
* Thur. 15th December.
Absolute latest for submitting anything.

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 22‑8‑2022   Quick introductions and the syllabus.
Removing an item from a binary tree (reminder).
Introduction to hashing.
Class 2  ‑ Wed 24‑8‑2022 Digital fingerprints and associated probabilities.
Signed char, short int, int, long int, long long int.
The int that can't be negated.
Unsigned ints are useful but dangerous.
Something practical: counting the occurrences of words in Peter Pan.
Class 3  ‑ Mon 29‑8‑2022 Comparing the distribution we get to the ideal (Poisson).
An example of a bad hash function.
Why we double the size of a vector/hash table when it grows.
Class 4  ‑ Wed 31‑8‑2022 String methods.
Graphs of the Poisson distribution.
ADTs (Abstract Data Types), dictionary and stack.
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.
Trying to explore a graph as though it were a tree (just a start).
Class 5  ‑ Wed 7‑9‑2022 Running through the tree-based algorithm.
Adapting it to work for general graphs.
Making it tell us what the shortest path was.
Using a queue to get a breadth-first exploration.
Class 6  ‑ Mon 12‑9‑2022 How to read the Nebraska-style map files.
The ADT Priority Queue.
Using a priority queue to drive the exploration algorithm.
Finding the shortest path from all the distances.
Possible implementations of a priority queue.
Introducing the Min-Heap.
Class 7  ‑ Wed 14‑9‑2022 Implementing add, get, and adjust on a min-heap stored in an array,
Heaps: major operations.
Animated heap operations.
Animated shortest path with a heap,
Discovering heap-sort.
Class 8  ‑ Mon 19‑9‑2022 Finishing heapsort.
The Floyd-Warshall algorithm.
The problem with using INT_MAX as the "infinite" cost value.
Class 9  ‑ Wed 21‑9‑2022 The Floyd-Warshall algorithm in C++.
Using floating-point "infinity",
Two (and higher) dimensional arrays in C++.
A Mysterious File.
Lots of details about iostream/fstream.
A data file to play with.
Class 10  ‑ Mon 26‑9‑2022 Making a binary file from the weather observations,
Doing a binary chop search on that file,
A first look at the contents of the mysterious file,
And a third file to think about compressing: Strings are trouble because they contain pointers, ISAM files.
Class 11  ‑ Wed 28‑9‑2022 All the tiles, and what they cover, and a rough diagram, and a basic viewer.
intersections, connections, and "geog", the formats.
Skipping some data so we can see the whole tile.
An introduction to dynamic programming: making change.
Class 12  ‑ Mon 3‑10‑2022 Where we picked up from, more or less,
Making it into a memoised function (corrected),
and at last, A true dynamic programming solution.
The combinatoric function C(n, r) by dynamic programming.
And just starting: Finding a 'subset' with a particular sum.
Class 13  ‑ Wed 5‑10‑2022 Completing the Knapsack or Subset Sum problem, brute force and d.p.,
Maximum sum contiguous subsequence, Some more numbers.
Class 14  ‑ Mon 10‑10‑2022 Longest ascending subsequence,
Number of different shortest paths in a grid,
Minimum Edit Distance: I tried to type Cabbages but accidentally typed Daabegz instead.
Class 15  ‑ Wed 12‑10‑2022 A straightforward recursive program,
Reminding ourselves about Activation Records (or Stack Frames) and how they work,
Making a non-recursive version with a stack: depth-first search,
Changing the stack into a queue: breadth-first search.
Class 16  ‑ Mon 17‑10‑2022 Preparing for the test.
Class 17  ‑ Wed 19‑10‑2022 First Test Day, A sample.
Possible topics:
  • Hash functions and hash tables,
  • Exploring a graph, depth first and breadth first,
  • Shortest path in a graph: Dijkstra's and the Floyd-Warshall algorithms.
  • Heaps and heap-sort,
  • Priority queues,
  • Binary files.
Class 18  ‑ Mon 24‑10‑2022 What we learned from the test (questions 1 and 2).
Class 19  ‑ Wed 26‑10‑2022 Accenture Visit tomorrow: The details, and The poster.
What we learned from the test (question 3).
For a bit of contrast, here is a tree in Python.
Using stacks and queues for DFS and BFS without having to create activation records:
          sort of depth first, and breadth first.
Class 20  ‑ Mon 31‑10‑2022 DFS with iterative deepening gives BFS with less of a memory requirement.
Investigating the natural shape and balance of a binary tree.
Introducing the 2-3-tree.
Class 21  ‑ Wed 2‑11‑2022 2-3-tree insertion methods and implementation.
Class 22  ‑ Mon 7‑11‑2022 Deleting from a 2-3-tree,
2-3-4-trees and red-black trees,
How to colour a pointer, and the usually worthless parent pointer,
B-trees and B+-trees, just briefly.
Class 23  ‑ Wed 9‑11‑2022 Today's class will be conducted entirely by zoom due to the expected weather.
Beginning to deal with parsing complex input.
Class 24  ‑ Mon 14‑11‑2022 Preparing for the test.
Class 25  ‑ Wed 16‑11‑2022 Second mid-term. Topics: Binary files; Dynamic programming; Recursion elimination; BFS, DFS, etc.; 2-3-trees.
Some mixed sample questions, and another old exam.
Class 26  ‑ Mon 21‑11‑2022 Special reading assignment: try to understand the "Estimate of time taken" section, starting on page 11 and ending at the end of page 12.
Class 27  ‑ Mon 28‑11‑2022 Electives.
Disc considerations for B-trees and B+-trees,
Quadtrees,
Compression, for graphics files and other purposes.
Maybe a word about AVL trees too if there's time.
Class 28  ‑ Wed 30‑11‑2022 What we learned from the second test.
Don't write all the way up to the corner.
A reminder of where we got in class 23 plus a quick introduction to parsing functions.
Class 29  ‑ Mon 5‑12‑2022 The last part of parsing and processing complex input, our starting point.
All completed: it is capable of running the example program calculating the factorial of 7.
It also includes an example of using C++'s built-in hash table, with the variable "memory".
Class 30  ‑ Wed 7‑12‑2022 (Deadlines, proper indentation, sensible names, functions with clear objectives, etc)
Topics for the final:
1. Hashing
2. Priority queues, heaps, etc
3. Graph exploration and shortest path
5. Searches, BFS, DFS, etc
6. Binary files
7. 2-3-trees
And that's it.