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. 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: Sat 4th September.
More tree operations.
2 Due: Sun 19th September.
Hash table of named places.
3 Due: Wed 6th October.
Sort race, part 1: preliminary quicksort.
Here are the files: testlib.cpp, testlib.h, bsort.cpp.
4 Due: Mon 18th October.
Sort race, part 2: quicksort working properly.
5 Due: Sat 30th October.
Sort race, part 3: mergesort working properly.
6 Due: Tue 30th November.
Manually exploring the highway system.
7 Due: Sun 12th December, ABSOLUTE LATEST.
Finding the shortest path.
8 Due: Sun 12th December, ABSOLUTE LATEST
Final version of quicksort and mergesort for the race.

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  ‑ Tue 24‑8‑2021   Quick introductions.
An animated tree app, to try things out.
Deleting a node from a binary tree.
Class 2  ‑ Thur 26‑8‑2021 An inefficient way to balance a binary tree.
Hash functions and hash tables.
The int that can't be negated.
Class 3  ‑ Tue 31‑8‑2021 Why unsigned ints are dangerous.
Experiments with hash tables.
The Poisson distribution.
Named places Format, Data file.
Class 4  ‑ Thur 2‑9‑2021 String Methods.
Bad hash functions.
Digital fingerprints.
Resizing on demand to keep lambda in a good range.
Linear Probing = closed hashing = open addressing.
Why we double the size when growing a vector or hash table.
Class 5  ‑ Tue 7‑9‑2021 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.
using a queue for a breadth-first search.
Class 6  ‑ Thur 9‑9‑2021 Inventing the priority queue, an abstract data type,
Using it to drive the shortest path algorithm.
Introducing the Min-Heap as an implementation.
Min-Heap operations.
Class 7  ‑ Tue 14‑9‑2021 Heaps: major operations.
Animated heap operations.
Discovering heap-sort.
The heap-sort algorithm,
Comparing heapsort with quicksort and merge-sort.
Shortest path with a min-heap,
Animated shortest path with a heap.
Class 8  ‑ Thur 16‑9‑2021 The adjacency matrix, and when it is appropriate.
The Floyd-Warshall algorithm.
The Floyd-Warshall algorithm in C++.
Using floating-point "infinity".
Class 9  ‑ Tue 21‑9‑2021 Some words on the use of two (and higher) dimensional arrays in C++.
Quicksort: three partitioning methods.
Quicksort animations: a partition method, and complete quicksort.
Quicksort on a linked list.
A warning about macros in C++.
Class 10  ‑ Thur 23‑9‑2021 Mergesort without recursion.
A Mysterious File.
fstream operations for binary files.
Our little file-reading program.
Class 11  ‑ Tue 28‑9‑2021 Lots of details about iostream/fstream.
A straightforward recursive program,
A non-recursive version of it,
Using a queue instead of a stack.
Class 12  ‑ Thur 30‑9‑2021 No class today.
Voluntary reading assignment: try to understand the "Estimate of time taken" section, starting on page 11 and ending at the end of page 12.
Class 13  ‑ Tue 5‑10‑2021 Strategies for game-playing programs,
The farmer, wolf, chicken, and grain crossing a river,
Nim: the MiniMax strategy.
Class 14  ‑ Thur 7‑10‑2021 Review day.
Class 15  ‑ Tue 12‑10‑2021 First Test Day, A sample.
This is an in-person, on-paper test.
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,
  • Recursion elimination.
Class 16  ‑ Thur 14‑10‑2021 a short break.
Class 17  ‑ Tue 19‑10‑2021 More MiniMax: Naughts and crosses.
Exploration with a maximum depth, letting an heuristic take over.
Using stacks and queues for DFS and BFS without needing to implement ARs.
DFS with iterative deepening: equivalent to BFS, but recursive and uses less memory.
Beginning to explore the natural shape of a binary tree.
Class 18  ‑ Thur 21‑10‑2021 The average height of a node.
Here's a tree in Python.
Gathering various statistics about the balancedness of trees: one, two, three.
(Did I get our ending time wrong? You really should have said something!)
Class 19  ‑ Tue 26‑10‑2021 2-3-trees: insertion methods and implementation.
Class 20  ‑ Thur 28‑10‑2021 What we learned from the test.
A 2-3-4-tree and the equivalent red-black tree.
How to colour a pointer.
Class 21  ‑ Tue 2‑11‑2021 Persistence: saving and restoring linked data structures.
Class 22  ‑ Thur 4‑11‑2021 Implementing a bit-set.
Introduction to dynamic programming:
Making change.
Finding a 'subset' with a particular sum.
Some more numbers.
Class 23  ‑ Tue 9‑11‑2021 Test preparation.
Class 24  ‑ Thur 11‑11‑2021 Second mid-term.
Some assorted sample questions.
Topics:
  • Depth- and Breadth- first searches; iterative deepening.
  • Binary files.
  • Recursion elimination.
  • 2-3 trees.
  • Minimax searches.
  • Saving and restoring data structures.
Class 25  ‑ Tue 16‑11‑2021 The subset sum problem.
Minimum number of coins to give change.
A basic input system.
Class 26  ‑ Thur 18‑11‑2021 Where we had got to, slightly tidied up:
inputsystem.h, inputsystem.cpp,
lexical.h, lexical.cpp,
prog.cpp, testfile.txt,
and the beginning of parsing.
Parsing statements and expressions,
Where we'd got to at the end.
Break
Class 27  ‑ Tue 30‑11‑2021 Finishing parsing and interpreting
Class 28  ‑ Thur 2‑12‑2021 What we learned from the second test.
Class 29  ‑ Tue 7‑12‑2021 Final exam preparation.