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. |
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:
| ||||
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. |