1 | Due: Sun. 7th Feb. | |||
The RPN calculator, part one. | ||||
2 | Due: Thur. 25th Feb. | |||
The RPN calculator, part two. | ||||
3 | Due: Thur. 11th March. | |||
Implement Shaker-sort on an array of objects. | ||||
4 | Due: Sun. 4th April. | |||
Linked list database, Here is the database in downloadable form. | ||||
5 | Due: Sun. 2nd May. | |||
Binary tree database. |
Class 1 ‑ | Mon 25‑1‑2021 | Quick introductions, the syllabus, policies, etc. Today's scrappy notes. | ||||
Class 2 ‑ | Wed 27‑1‑2021 | Vector operations, How dangerous an ordinary array can be (here it is made safe), Reverse Polish Notation (RPN). Notes from today: Playing with a vector, converting strings to ints. | ||||
Class 3 ‑ | Mon 1‑2‑2021 | The use of new and delete. Defining our own version of a vector: ArrayOfStrings. Class 2's example "playing with a vector" converted to this style. | ||||
Class 4 ‑ | Wed 3‑2‑2021 | The tomorrow calculator: protected and public. Here it is, made safe. Two dimensional arrays in C++, making our own matrix object to fix the problems. | ||||
Class 5 ‑ | Mon 8‑2‑2021 | Reference variables and reference results. A templated version of ArrayOf (equivalent to vector). | ||||
Class 6 ‑ | Wed 10‑2‑2021 | The special timing function for unix. Timing a sorting operation: Selection Sort. | ||||
Class 7 ‑ | Mon 15‑2‑2021 | Determining that selection sort is O(N2) analytically, and a graphical technique, using logarithmic graph paper. Insertion sort, first version. | ||||
Class 8 ‑ | Wed 17‑2‑2021 | Insertion sort can easily be an in-place algorithm. Bubble sort, slower than the others. Shaker sort. Generating random strings, character encodings. Why sorting strings is slower than soting ints. | ||||
Class 9 ‑ | Mon 22‑2‑2021 | Why we usually pass objects as reference parameters. Splitting an array, sorting the two halves, and re-merging them makes sorting faster. | ||||
Class 10 ‑ | Wed 24‑2‑2021 | The plan for Merge-Sort's splitting and merging. Why Mergesort's time is O(NlogN). The starting point for coding mergesort. A complete basic mergesort implementation. An attempt at a small database. | ||||
Class 11 ‑ | Mon 1‑3‑2021 | Back to the attempted database. Introducing Polymorphism, step 1, 2a, 2b, 3a, 3b, Final version. | ||||
Class 12 ‑ | Wed 3‑3‑2021 | "Wellness Wednesday", we do not meet today. Your make-up reading assignment: Read the first one-and-a-half pages and try to work out what the algorithm is. What is a "nest" in today's terms? | ||||
Class 13 ‑ | Mon 8‑3‑2021 | Back to polymorhpism and inheritance. The final version of the example. | ||||
Class 14 ‑ | Wed 10‑3‑2021 | Test preparation. | ||||
Class 15 ‑ | Mon 15‑3‑2021 | First mid-term exam. All on-line, using Respondus lock-down browser. A sample test, and its solution, and another mini-test, with its solution. Another sample, and its solution. Another sample, (remember that some of these samples cover test 2 material). | ||||
Class 16 ‑ | Wed 17‑3‑2021 | Algorithm part 1,
part 2.
The test system. Our first partitioning algorithm. Our first partition method animated, The entire quicksort algorithm animated. Our second partitioning algorithm. | ||||
Class 17 ‑ | Mon 22‑3‑2021 | At the supermarket: discovering the linked list. Building a linked list, printing a linked list, searching a linked list. Notes from today: version 1, and version 2. | ||||
Class 18 ‑ | Wed 24‑3‑2021 | The linked list as a proper object, including two methods for removing an object, and a way to reverse a list. | ||||
Class 19 ‑ | Mon 29‑3‑2021 | What we learned from the test. | ||||
Class 20 ‑ | Wed 31‑3‑2021 | Adding to the end of a linked list, two slightly different methods. Linked lists that remember where their own ends are. adding and removing. | ||||
Class 21 ‑ | Mon 5‑4‑2021 | Doubly-linked lists: Adding and removing in all sorts of ways. | ||||
Class 22 ‑ | Wed 7‑4‑2021 | Inheritance, quicksort, etc: review. | ||||
Class 23 ‑ | Mon 12‑4‑2021 | Second test day. All on-line, using Respondus lock-down browser. A sample; Binary trees will not appear on this test. | ||||
Class 24 ‑ | Wed 14‑4‑2021 | "Wellness Wednesday", we do not meet today. Here is your special reading assignment. Try to work out what they are saying a tree is. No need to go too far. | ||||
Class 25 ‑ | Mon 19‑4‑2021 | Introducing Binary Trees. Building a tree by hand. Navigating, searching, finding path, printing. | ||||
Class 26 ‑ | Wed 21‑4‑2021 | Binary trees, part two. Printing the whole tree, printing nicely, inserting (recursion and a loop), Using a tree to sort a vector. | ||||
Class 27 ‑ | Mon 26‑4‑2021 | Binary trees, part three. More about printing and flattening. A destructor, finding the average value, Printing with depth, printing by depth, a breadth-first traversal. | ||||
Class 28 ‑ | Wed 28‑4‑2021 | Preparing for the final. |