| 1 | Due: Sunday 8th Feb. | |||
| Reverse Polish Calulator. | ||||
| 2 | Due: Sunday 8th March | |||
| Your own virtual machine | ||||
| Data structures we are going to be working on, pointers, vectors, linked lists, binary trees. A few notes about using pointers. | ||||||
| Reviewing C++ things that we should mostly already know. | ||||||
| And some things that we might not already know. Surprise behaviours of C++ things, kinds of numbers, etc. | ||||||
| Reverse Polish notation, stacks, and #include <vector>. | ||||||
| (many) words on the first assignment. A stringstream trick, the int operators ^ & | << >> Practice with objects: start, next step, where we got. | ||||||
| (look at this again first) non-member operators, protection, member operators, operator<< We made a stack of strings (called svector) with a destructor. | ||||||
| splitting a program into multiple .cpp and .h files for separate compilation. templates for classes and functions. Amortised analysis of big-O for vector push if growth is incremental. | ||||||
| Sum of series for growth by doubling. How to use the debugger - essential stuff. A design for a simple virtual machine. | ||||||
| operator[], operator=, copy constructor. doing multi-dimensional arrays properly. | ||||||
| Review of the first quiz, I hope we learn the lesson. More ways of handling multi-dimensional arrays. <cstdarg> for an unknown number of parameters. C's printf function from <cstdio> is worth knowing about. | ||||||
| Virtual machines and the insides of real computers. An attempted database, pointers saved us. | ||||||
| Why did pointers save us? (References almost could have too) Constructors and destructors to automatically trace functions. Accurately measuring the time it takes to sort an array. | ||||||
| Pop Quiz 2 correction. A closer examination of selection sort. Loop invariants and loop varients establish/demonstrate correctness. Bubble sort and selection sort. All sorting algorithms so far quadratic time. | ||||||
| Reference implementation to help experiment with the VM assignment. Shell sort has a few advantages. Cutting array in half, sorting the halves, and recombining in order almost halves the time required. The magic of merge sort makes the sorting disappear. Merge-sort's time is NlogN. Although logarithms in all bases are proportional, knowing it is base 2 is important. | ||||||
| First mid-term test. Vectors and multi-dimensional arrays: the C++ way and making your own. Classes, methods, con/de-structors, operators, static things... Quadratic sorting algorithms, Big Os and timing calculations. And of course general C++ and programming will be required. A sample test and its solution, Another sample and its solution. Another sample. Yet another sample and its solution. Some of these questions are not relevant yet, you will not be tested on anything we haven't covered yet. | ||||||
| Break | 9th to 13th | |||||