| 1 | Due: Sat. 8th February . | |||
| Reverse Polish Calculator. | ||||
| 2 | Due: Thur. 27th February. | |||
| Creating and programming your own virtual machine. | ||||
| 3 | Due: Sat. 29th March. | |||
| Super-integer calculator. | ||||
| 4 | Due: Thur. 24th April. | |||
| Another super-integer calculator. | ||||
| 4 | Due: Tue. 29th April. | |||
| A collection in a binary tree. | ||||
| Quick introductions. What pointers are all about. | ||||||
| Remembering (or maybe finding out) what structs are for, twelve steps: one, two, three, four, five, six, seven, eight, nine, ... | ||||||
| Still to look at:
ten,
eleven,
twelve. and a lucky thirteenth one for what we are about to do. | ||||||
| a closer look at take_int from example 13. Vectors. Reverse Polish Notation. Here are the jottings from today's class including the demonstration of arrays being dangerous. How to convert a string that looks like a number into that number. | ||||||
| Details for the first assignment. fast to-the-power-of operations, the bitwise binary operators & | ^ << >> new and delete give the effect of changing an array's size and lifetime. protected: and public: in struct definitions. | ||||||
| Useful technique: find the closest fraction to a double. A surprisingly complex task: how to convert a string that looks like a number into that number. Protected: (and private:) only protect programmers who behave nicely: Trivialised version of fractions program showing normal behaviour, Protected: protecting us from bad behaviour, An experiment, just to make what comes next easier, Typecasting pointers to evade protection. | ||||||
| Various things concerned with making our own vector, Must work effectively in two different ways: as a safe growable array, and as a stack, operator[] Reference results, like reference parameters, are useful. | ||||||
| operator+=, operator=, copy constructor, destructor for vectors. | ||||||
| A new adventure: creating and programming our own virtual machine. | ||||||
| Little add-on from Tuesday: how functions, local variables, and even recursion can be handled. Amortised time analysis: why vectors should grow by doubling their size. | ||||||
| Two (and more) dimensional arrays. Many troubling C++ "features", including multi-dimensional arrays, and how to fix them. How to use <cstdarg>. | ||||||
| Efficient implementation of multidimensional arrays with variably based indexes. Simple use of templates for class definitions. Constructors and destructors for tracing. An attempted database. | ||||||
| Pointers to the rescue: the attempted database works. Big (and complicated) example of all sorts of things with classes. using istringstreams. Selection sort and its efficiency (or lack of it). | ||||||
| What the "big O" notation is really all about. Insertion sort and bubble sort. Loop invariants and variants help to understand, explain, and validate. | ||||||
| A miscellany of test review items. | ||||||
| First mid-term test. Vectors and multi-dimensional arrays: the C++ way making your own. Classes, methods, con/de-structors, operators, static things... Quadratic sorting algorithms. And of course general C++ and programming will be required. A sample test (not question 1), and its solution, Another sample (only question 3), and its solution. Another sample (only question 6), Yet another sample (only question 5), and its solution. | ||||||
| Break | 10th to 14th | |||||
| About the next assignment, a super-int calculator. Creating single objects with new; exactly why making a pointer to an existing object is dangerous. At the supermarket. Representation of giant ints and how to add, subtract, and multiply. Why it is dangerous to create an object with & instead of new. Fragmentation of memory. Our first linked list, just 3 operations so far: create, print, reverse. (See class 18's notes link for today's notes, they are combined) | ||||||
| Much more with linked lists: searching, adding up all the values, linked list as dictionary. Reduce and map (called apply_to_all here), functions prototypes, functions being parameters. A templated linked list of anything with a very general templated search method. Today's notes. | ||||||
| More with linked lists: adding to the end (2 ways), length (2 ways), etc... Today's partial notes. | ||||||
| Recording the end of the list doesn't help with removing from the end. Doubly linked lists would do that. Selection sort on a linked list is almost identical to the array version. Today's partial notes. | ||||||
| Insertion sort and bubble sort on linked lists. | ||||||
| Insertion sort on a linked list, it has a useful dual purpose. Splitting a linked list in half, and combining two sorted linked lists. | ||||||
| How merge-sort on linked lists really works - no sorting (sort of). Vital thing to get: demonstrating that merge-sort's time is O(N*log(N)) and why that matters. | ||||||
| A quick look at a doubly-linked list. Binary trees. | ||||||
| (for the division by two thing set out nicely see the assignment) Lots more with binary trees. | ||||||
| Even more about binary trees. | ||||||
| Second test: Linked lists, fast sorting, and binary trees. Sample 1: Questions 5 and 7 only. Sample 2: Questions 6 and 7 only. Sample 3: Questions 5 and 7 only. Don't treat the samples as all-inclusive. Anything we have covered on those topics could appear. | ||||||
| Review Q1 from MT1. Quicksort. | ||||||