1 | Due: Sat. 4th Feb. | |||
Very basic linked list constructuion. | ||||
2 | Due: Thur. 23rd Feb. | |||
Cat club - a linked list of linked lists. | ||||
3 | Due: Sat 1st April. | |||
Special vector. | ||||
4 | Due: Sat 22nd April. | |||
Basic supercalculator. | ||||
5 | Due: Sat 29th April. | |||
Quicksort. | ||||
6 | Due: Mon 8th May | |||
Binary Trees. |
Class 1 | Wed 18‑1‑2017 | Introductions. Data Structures = what to do when you've got complicated data and/or a lot of data -
keep it nicely organised. Reminders about structs: Alone, and in Arrays; use reference parameters. PC log in - use Putty or your own preferred SSH app. Macintosh log in - use terminal and type ssh -oHostKeyAlgorithms=+ssh-dss username@rabbit.eng.miami.edu. | ||||
Class 2 | Mon 23‑1‑2017 | What do we do if we don't know how big to make the array? We'll discover something more flexible. Here's a start. Pointers, methods, and constructors are introduced all at once. | ||||
Class 3 | Wed 25‑1‑2017 | More linked lists. There should be a difference between a person and an address book, but for now ... A linked list of people, using NULL for a proper sentinel value. Notified of first assignment. | ||||
Class 4 | Mon 30‑1‑2017 | Searching a linked list. Building a linked list "the right way round" - adding new items to the end. | ||||
Class 5 | Wed 1‑2‑2017 | Three separate objects is the way to go: 1 for the list, 1 for the links, and 1 for the people. | ||||
Class 6 | Mon 6‑2‑2017 | Adding in the right place in an ordered list. Before following any pointer make sure you know
it can't be NULL. A simple algorithm for sorting a linked list. The time it takes depends on the square of the size of the list. | ||||
Class 7 | Wed 8‑2‑2017 | More linked list sorting algorithms: insertion sort, selection sort, bubble sort. All of them require time that depaends on the square of the length of the list. | ||||
Class 8 | Mon 13‑2‑2017 | Back to arrays: heap allocation (int * A = new int[10]) compared to stack allocation (int A[10]). Bubble sort on an array: really calculating the time, big O notation for computation time compared to data size. | ||||
Class 9 | Wed 15‑2‑2017 | Insertion sort and selection sort on arrays; gradually transforming a simplistic selection sort into an "in-place" version. Considering the times again, still quadratic. | ||||
Class 10 | Mon 20‑2‑2017 | C++ doesn't give us a very useful version of two dimensional arrays: it doesn't check indexes against sizes, but needs to be told sizes. So we implement our own as a class. Public, protected, and assert are introduced too. | ||||
Class 11 | Wed 22‑2‑2017 |
We are introduced to printf, and look at addresses used by heap and stack allocation, noticing that stack memory gets reused frequently. A badly designed database. | ||||
Class 12 | Mon 27‑2‑2017 | The problem of accidentally copied objects (not getting a raise). Pointers save the day and our database program. Looking at an old test, and being introduced to delete. | ||||
Class 13 | Wed 1‑3‑2017 | First Test | ||||
Class 14 | Mon 6‑3‑2017 | Introducing vectors - objects with the functionality of arrays, but you can change their sizes. | ||||
Class 15 | Wed 8‑3‑2017 | Efficiency of resizing a vector. Add an increment to capacity each time and the overall behaviour
is quadratic. Double the capacity each time and it's linear. Introduced Reverse Polish Notation. | ||||
Class 16 | Mon 20‑3‑2017 | Making a reverse polish calculator that also translates to normal notation. First thoughts on an unlimited-precision calculator. | ||||
Class 17 | Wed 22‑3‑2017 | Separate compilation example with our 2d array code:
2da.h,
2da.cpp,
test.cpp. Compile with CC -c 2da.cpp followed by CC test.cpp t2d.o The partitioning method that lets us split an array into two independently sortable portions: the animated demo. Introducing Quick-Sort. | ||||
Class 18 | Mon 27‑3‑2017 | Further study of quicksort, and mergesort for linked lists. | ||||
Class 19 | Wed 29‑3‑2017 | Where does all the sorting happen? More about loop variants and invariants; A different partitioning algorithm. The first appearance of Quicksort: paper, algorithm part 1, part 2, the test system. | ||||
Class 20 | Mon 3‑4‑2017 | Belatedly going over the test. | ||||
Special | Tue 4‑4‑2017 | Lab guys' help session, at 7 p.m. | ||||
Class 21 | Wed 5‑4‑2017 | Remembering Binary Chop Search. New Things! | ||||
Special | Fri 7‑4‑2017 | Lab guys' help session, at 11 a.m. | ||||
Class 22 | Mon 10‑4‑2017 | More tree operations: Inserting and searching the linked-listy way, printing in order. | ||||
Special | Tue 11‑4‑2017 | Pre-test review session at 7 p.m. | ||||
Class 23 | Wed 12‑4‑2017 | |||||
Special | Fri 14‑4‑2017 | Pre-test review session at 9.30 a.m. | ||||
Class 24 | Mon 17‑4‑2017 | Second test. A sample. Another sample. | ||||
Class 25 | Wed 19‑4‑2017 | More tree operations - rotations can be useful. A quick look at Lisp. | ||||
Class 26 | Mon 24‑4‑2017 | Impelementing Lisp - the basics. | ||||
Class 27 | Wed 26‑4‑2017 |