ECE318 J (Algorithms) Autumn 2023
Mon, Wed, 5:05-6:20 in MCA 202 A

The Book

Useful information and things

Examinations:

Assignments

1    Due: Saturday 2nd September
Tree database with deletion.
2 Due: Saturday 16th September
Put all the named places in a hash table.
3 Due: Friday 20th October
An on-disc hash table for compressed named places.
4 Due: Saturday 11th November
Exploring the map of the United States manually.
5 Due: Saturday 18th November
Automatically finding the shortest path through the map.
6 Due: Saturday 2nd December
Subset sum by two different methods.

PC log in - use Putty or your own preferred SSH app.
OR mac users: start the terminal app, windows users: start powershell, then type the command
ssh username@rabbit.eng.miami.edu and type your password when prompted.
Windows users beware: you can't use ctrl-V in pico, but page up and page down will do the job.

Class History

Class 1 - Mon 21-8-2023    Introductory Bits.
Removing data from a binary tree without ruining the balance.
The essential take-aways from today's class.
Class 2 - Wed 23-8-2023 New accounts all added. Username = UM email before @, new passwords = C number with capital C.
Announce assignment.
Stringstreams: iss0.cpp, iss.cpp.
The basic unadorned original hash function,
Digital fingerprints,
An almost correct hash table.
The essential take-aways from today's class.
Class 3 - Mon 28-8-2023 Hundreds of hippopotamusses in Peter Pan - we had clashes.
Resolving clashes - buckets are linked lists.
Useful little utilites, wc, sort, uniq: getting an accurate word count.
Graphs of the Poisson distribution.
How hash functions can go bad. Checking our distribution against the ideal.
Keeping the fullness in a good range, efficiently resizing a hash table.
The dangers that unsigned ints can cause.
Why we always double (or at least multiply) the size when enlarging vectors and hash tables.
The essential take-aways from today's class.
Class 4 - Wed 30-8-2023 All named U.S. places, and the states.
strtod and strtol from cstdlib, use old C strings.
String methods.
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.
Finding out whether a path exists or not, recursion works if we remember where we've been.
Finding length of a path recursively too, return float, -1.0 for failure.
The essential take-aways from today's class.
Class 5 - Wed 6-9-2023 The recursive algorithm.
circular struct definitions,
Reading and creating the internal representation of the map, all places in a hash table.
Use a vector to record roads followed and places visited.
Keep track of distance so far, save the vectors for the best solution yet.
A queue would be very much more efficient than the recursive search,
but it requires that all roads have the same length.
The essential take-aways from today's class.
Class 6 - Mon 11-9-2023 Important things for assignments.
Examples of some less used C++ features.
Exceptions: one, two, three.
The essential take-aways from today's class.
Class 7 - Wed 13-9-2023 (No video on today's zoom recording, rear camera not working, I reported it).
Save order for a tree - prefix and rebuild.
Simulated ants, don't really care where they are most of the time.
The Priority Queue ADT, considering various implementations.
The min-heap, full binary tree, only top-to-bottom ordering.
Min-heap in an array (or vector), no need for pointers.
Heaps: major operations review.
The essential take-aways from today's class.
Class 8 - Mon 18-9-2023 (No video on today's zoom recording, rear camera not working, I reported it again).
Special heapable objects, not so great for this: index, prio, and node.
Animated heap operations.
Animated shortest path with a heap,
Discovering heap-sort.
The essential take-aways from today's class.
Class 9 - Wed 20-9-2023 The Floyd-Warshal algorithm.
A Mysterious File.
Lots of details about iostream/fstream.
The essential take-aways from today's class.
Class 10 - Mon 25-9-2023 A bit about how binary files reduce data size and speed up retrieval.
Making a binary file from the named places text file.
Binary chop search on a binary disc file.
The essential take-aways from today's class.
Class 11 - Wed 27-9-2023 First test date.
Updated HKN tutoring times.
Compressing a string: .cpp and .h
How would we make a disc-based hash table? ISAM too
Decoding the mystery file.
The essential take-aways from today's class.
Class 12 - Mon 2-10-2023 The essential Unix commands and pico/nano editor controls, and the vim cheat sheet.
Separate compilation reminder.
Probabilistic methods do a better job of compressing strings.
A slightly different way to construct a tree, and why it is useful.
A reminder about stack frames or activation records.
Recursion elimination.
The essential take-aways from today's class.
Class 13 - Wed 4-10-2023 Back to recursion elimination.
And a self-tracing version for educational purposes.
What happens if the stack is replaced with a queue?
Something this is useful for: the build-up, and the real thing.
In simple cases, we don't need to go to all the trouble of creating activation records: stack, and queue.
Depth-first with iterative deepening is usually better than a queue.
Quick introduction to an up-coming topic via "how many ways can I give change for N cents?"
The essential take-aways from today's class.
Class 14 - Mon 9-10-2023 Review for the test for as long as is needed.
Class 15 - Wed 11-10-2023 First test day, A sample.
Topics:
  • Hash functions and hash tables.
  • Exploring a graph, depth-first and breadth-first.
  • Finding the shortest path, both Dijkstra's and Floyd-Warshall.
  • Priority queues, heaps, and heapsort.
  • Binary files.
  • Recursion elimination.
Class 16 - Wed 18-10-2023 Completing the which coins question: plain, traced, complete, memo, dynamic.
Only a limited number of possible questions but it takes a long time anyway.
Memoisation - make sure you never ask the same question twice.
Leads to the more elegant style of Dynamic Programming - solve all possible problems first.
The knapsack or subset sum problem.
The essential take-aways from today's class.
Class 17 - Mon 23-10-2023 More words on assigment 3.
The "brute force" solution to the knapsack problem.
The combinatoric function C(n, r) by dynamic programming.
How many shortest paths in a regular grid? by d.p. again.
The essential take-aways from today's class.
Class 18 - Wed 25-10-2023 Exploring the natural balance of a binary tree.
For most N there is no perfectly balanced binary tree.
Introducing the 2-3-tree, how to search it and how to add new data to it.
How to implement those 2-3-tree algorithms.
The essential take-aways from today's class.
Class 19 - Mon 30-10-2023 Issues that arose from the first mid-term.
Things about the 4th assignment: the file formats and intersections.txt and connections.txt.
Class 20 - Wed 1-11-2023 Deletion from a 2-3-tree, the easy parts.
Persistent data structures. Saving linked data structures to a file.
The essential take-aways from today's class.
Class 21 - Mon 6-11-2023 A different 6th assignment than I had originally planned.
Deleting from a 2-3-tree, the whole thing.
A more object-oriented style, a binary tree in Python.
Reinforcing some O.O. things: ok to start, but not ok here.
Five minutes introducing the next topic.
The essential take-aways from today's class.
Class 22 - Wed 8-11-2023 Dealing with complex input: proper expressions or even programs.
Separate stages and separate little functions for parsing are essential.
And a quick look at some unfortunate aspects of C and C++'s syntax.
Where we got to today.
The essential take-aways from today's class.
Class 23 - Mon 13-11-2023 Parsing all the different kinds of statements is easy for a cleanly designed language.
Then dealing with operator priorities requires a clever idea.
This is where we got, after adding a step that we didn't have time for.
The essential take-aways from today's class.
Class 24 - Wed 15-11-2023 Pre-test review. Be prepared with questions and topics.
Class 25 - Mon 20-11-2023 A special reading assignment.
Make sure you understand the "Estimate of time taken" section, starting on page 11 and ending at the end of page 12.
And what is a Nest? What is it doing? What would we call it today? What would we use instead?
Answer those three questions and submit your answers as assignment number 99 on blackboard.
Class 26 - Mon 27-11-2023 Second mid-term, the possible topics are:
Heap sort,
Exploring or shortest path in a graph other than by breadth first search,
Woring with files, both text and binary,
Simple dynamic programming problems, and
Recursion Elimination.
Samples: an assortment of questions, and an old test, ignore quicksort and mergesort.
Class 27 - Wed 29-11-2023 Dealing with priorities actually involved restructuring the rules.
Finishing parsing, and now actually executing our programs:
       our little programming language completed.
Fast to-the-power-of-int and the seive or Eratosthenes.
Class 28 - Mon 4-12-2023 What we should learn from the test.
B-trees and B+-trees, especially designed for storage on disc.
A little bit about 2-3-4-trees and red-black trees.
I looked it up, 2-3-trees were invented in 1970, red-black in 1978, so it is the 2-3's that deserve the credit.