1 | Due: 2nd February | |||
Stack-based reverse polish calculator. | ||||
2 | Due: 24th February | |||
Two dimensional array objects. | ||||
3 | Due: 9th March | |||
Race between sorting algorithms. | ||||
4 | Due: 6th April | |||
Calculator for giant integers. | ||||
5 | Due: 30th April | |||
Binary tree database. |
Class 1 | Tue 16‑1‑2018 |
Macintosh log in - use terminal and type ssh -oHostKeyAlgorithms=+ssh-dss username@rabbit.eng.miami.edu Introducing a variable-sized array. | ||||
Class 2 | Thur 18‑1‑2018 | Pointers and arrays and new and delete: Looking at where things are located in RAM. Making an array that can be resized on demand. | ||||
Class 3 | Tue 23‑1‑2018 | Review of *, new, and delete. C++'s vector class: Our previous example reprogrammed to use it. The data structure Stack. The reverse-polish calculator example. | ||||
Class 4 | Thur 25‑1‑2018 |
Methods and constructors: A self-reporting counter object, Public and protected: A fool-proof version of the above, Static variables and destructors: A trick for tracing complicated functions, The beginning of a complete vector_of_strings class implementation. | ||||
Class 5 | Tue 30‑1‑2018 | A hopeless program, it needs the debugger (and a better design). A complete vector of strings, reference results. templates: a vector of anything. | ||||
Class 6 | Thur 1‑2‑2018 |
A typical old-fashioned random number generator, Array parameters are annoying, you have to supply (and remember) the size separately, ourvec.h: Making our vector implementation into a library, vec.cpp: and using it in a simple test, Vector parameters are much more convenient, but watch out for the destructor | ||||
Class 7 | Tue 6‑2‑2018 | Two dimensional arrays: Multidimensional arrays are hopeless in C++ (this doesn't work). Improved method 1: a pointer to an array of pointers to arrays of data item (an array of arrays). Improved method 2: convert 2-d array into 1-d array, so item[r][c] becomes item[r*columns+c]. | ||||
Class 8 | Thur 8‑2‑2018 |
A badly designed database; The corrected version making proper use of pointers. Thinking about implementing giant numbers as vectors of digits. | ||||
Class 9 | Tue 13‑2‑2018 | Implementing big numbers as arrays of digits, introducing inheritance, See if you can work out how to make subtraction work "properly". | ||||
Class 10 | Thur 15‑2‑2018 | More about giant integers, signs and multiplication methods. The big O notation introduced, and discovering that our vector implementation is slow. | ||||
Class 11 | Tue 20‑2‑2018 | Sorting part 1. | ||||
Class 12 | Thur 22‑2‑2018 | Sorting part 2. code from this week: selsort.cpp, sel2.cpp, ourvec.h. | ||||
Class 13 | Tue 27‑2‑2018 | A bit more sorting, A skeleton program for timing functions, At the supermarket: discovering the linked list. | ||||
Class 14 | Thur 1‑3‑2018 | First experiments with a linked list. Creating, adding an item, printing, finding an item, removing an item. | ||||
Class 15 | Tue 6‑3‑2018 | Proper object orientation: and object for each link and an object for the list itself. isempty, remove_first, insert_in_place add up to insertion sort for linked lists. Splitting a linked list in half. | ||||
Class 16 | Thur 8‑3‑2018 | Adding to the end of a list, Merging two sorted linked lists, and all the pre-requisite methods. | ||||
Spring Break | ||||||
Class 17 | Tue 20‑3‑2018 | Test preparation. | ||||
Class 18 | Thur 22‑3‑2018 | First Test. A sample test, and its solution, and another mini-test, with its solution. Another sample, and its solution. Expect three equally weighted questions. Do not expect questions about timing to feature as heavily as they did in some of these samples. Topics are covered in a different order from one semester to the next, these samples at least show you the style of test to expect. Prepare for: Pointers, new, delete; vectors; multi-dimensional arrays; sorting; linked lists. | ||||
Class 19 | Tue 27‑3‑2018 | Discovering merge-sort and comparing its speed to other sorting methods we know. | ||||
Class 20 | Thur 29‑3‑2018 | Coding merge-sort recursively. Doubly-linked lists. | ||||
Class 21 | Tue 3‑4‑2018 | Reminding ourselves about Binary Chop Search. Introducing Binary Trees: searching. | ||||
Class 22 | Thur 5‑4‑2018 | Constructing a binary tree by hand, and printing it in order Two methods for inserting data into a tree | ||||
Class 23 | Tue 10‑4‑2018 | More binary tree methods. | ||||
Class 24 | Thur 12‑4‑2018 | Experimentally measuring how good a randomly constructed binary tree is. Inventing Tree-Sort. | ||||
Class 25 | Tue 17‑4‑2018 | Review. | ||||
Class 26 | Thur 19‑4‑2018 | Second Test. Another sample, (remember that some of the test 1 samples cover test 2 material). Prepare for: Merge-sort, binary chop search, doubly linked lists, binary trees. | ||||
Class 27 | Tue 24‑4‑2018 | More tree experiments. Including non-recursive in-order tree printing. | ||||
Class 28 | Thur 26‑4‑2018 | Quick-sort: A popular partitioning method. The whole algorithm. The first appearance of Quicksort: paper, algorithm part 1, part 2. The test system. |