| 1 | Due: Sunday 28th January. | |||||||||||||
| The RPN calculator. | ||||||||||||||
| 2 | Due: Thursday 15th February | |||||||||||||
| Make your own superior kind of vector. | ||||||||||||||
| 3 | Due: Friday 8th March | |||||||||||||
| Supercalculator!. | ||||||||||||||
| 4 | Due: Monday 25th March | |||||||||||||
| Add division and modulo to your bigints and supercalculator. | ||||||||||||||
| 5 | Due: Saturday 13th April | |||||||||||||
Linked-list database of people
| 6 | Due: Sunday 5th May
|
Database of people in a binary tree
| | |||||||||||
| Quick introductions. A word about pointers. Can't cover everything, C++ is a very big language. If anyone registers for this class late, send me an email right away so I can create an account for you on our server. Today's things: Checking the memory addresses of various things, seeing the stack frames The abstract data type Stack C++'s vectors as far as they relate to stacks Reverse polish notation | ||||||
| More things you can do with a vector, they aren't only good for stacks. Beginning to work out how we can make a vector for ourselves. Remember no zoom, take notes. A lot of the details of what we did today. | ||||||
| The "input all from one line" method, C++ does that automatically. The real point of vector's .data() and string's .c_str(), they should almost never be used. More on pointers vs arrays, * p, *(p + 3), p[3], p[0], and p. Never use the second one in C++. Vectors, comparing v[3], v.at(3), V.data()[3], *(v.data() + 3), don't do the fourth one. The dangerous array demonstration, the sizes tried were 10, 100, 200, and 1000. Complete run-through of strtol. | ||||||
| Details of requirements and expectations for work done. An accurate but incomplete look at how the heap works, including new and delete. Our own implementation of vector_of_string, still some bits left to do. | ||||||
| The do not use list. An ASR-33 Teletype (1963, $1,000 + add-ons, avg. fam. ann. income $6,200). Random access methods for the vector_of_string are easy. Redirecting input and output. Always use cerr instead of cout for error messages. Exceptions by many examples: one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen. "class" is identical to "struct" except for default protection level. Only use struct for simple little things. | ||||||
| Just for completeness, the different kinds of exception. Look at thirteen again, I missed something. public, protected, and private. many constructors, including default and copy, avoiding accidental data sharing. destructor. templates. | ||||||
| Check for the five absentees. More on exception example 13; POD and non-POD data items. The different meanings of const, depending on exactly where it appears. Destructors, just as important as constructors, but need etra care. Objects should nearly always be passed as (const) references; early destruction otherwise. Reference variables and results. Function parameters again. Making operators work on your own objects, even [i] for array-like access. A first very quick look at gdb the debugger. | ||||||
| Second assignment was already pushed back. On more try for the five absentees. Different kinds of error, and More about gdb the debugger. Constructors and destructors for tracing functions, static members. | ||||||
| Forgot this both days last week: Dean's special event. Why there's no plain old pop(). The Assignment operator. Graphical operations and animations as matrices, why a 3-D world requires 4x4 matrices. | ||||||
| C++'s troublesome idea of a matrix: the starting point, typedef - a little easier to read, Analysing time complexity, the big-O notation and consequences. Unacceptable, will be rejected without further inspection. #include <cstdarg> for POD parameters only. This would be better but for the fact that it doesn't work. | ||||||
| Guidelines and requirements fot the soon to be set third assignment, Supercalculator. Vector-like storage of digits, digit type must be unsigned char, bool for negatives, constructors from string and ordinary int, unsigned add first, test, then signed add. Same for subtract, multiplication by ordinary and, then by another bigint. | ||||||
| .cpp and .h files and separate compilation, using an example containing almost everything class/struct related. | ||||||
| The reason for not being able to look at /home/www. .hpp files and *.o Inheritance used to create a French-speaking version of Thursday's date class. Multidimensional arrays done properly. | ||||||
| private does have one use. array of array of array ... as multi-dimensional array implementation, unwieldy but valid. Three quadratic sorting algorithms: selection sort, insertion sort, and bubble sort. | ||||||
| A few more things about bubble sort:
p1, p2, p3, p4, p5,
p6, p7, p8, p9. BS can stop early if only a few small values are in the wrong place. A BS in the other direction can stop early if only a few big values are in the wrong place. Shaker sort alternates the two, so the big loop only runs once for each out-of-place value. One of the reasons sorting matters: a reminder of binary chop search. Logarithmic timing and why it matters so much. | ||||||
| An attempted database. Pointers to the rescue again. At the supermarket. | ||||||
| Linked lists day. | ||||||
| First mid-term, there are four possible topics but that does not necessarily mean there will be four questions: Vectors: making your own. Multi-dimensional arrays. Classes, methods, con/de-structors, operators, static things... Quadratic sorting algorithms. And of course general C++ and programming will be tested. 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. | ||||||
| Important Unix commands and most pico/nano operations. More on linked lists. Three ways to add to the end, only one is fast. Structure sharing, reasons and problems, reference counts don't always work. Insert in right place in already sorted list, leads easily to insertion sort. | ||||||
| Being a grown-up programmer, Using the emacs editor. Linked lists for sparse arrays. Splitting a linked list into two as-close-as-possible equal length halves. | ||||||
| (backspace and delete now work with emacs) Discovering mergesort. | ||||||
| Tidy review of merge-sort on a linked list and the time analysis. Fractals and recursion have quite a lot in common. The natural implementation of mergesort on a linked list is a very simple recursive function. Mergesort on an array is almost obvious but an efficient implementation is a bit tricky. Full analysis of vector growth strategies: add makes it quadratic, multiply makes it linear. | ||||||
| (zoom needed) Mergesort the old way, pictures: one, many. Mergesort on an array requires an extra temporary array, the loops are rather complicated. Recursion makes it much easier to understand and has no significant drawbacks. | ||||||
| (zoom needed) Quicksort. A partition method animated, The entire quicksort algorithm animated. Quicksort's first appearance, the algorithm part 1, part 2. The test system. | ||||||
| Binary trees: linked lists adapted so that binary chop search works. The structure, always insert at a leaf. Search, insert (both with loop and recursion), print. How to make print show the tree's shape, how to turn it into a sorting algorithm. | ||||||
| Depth first search (DFS) or breadth first search (BFS)? Four traversals, in-order DFS, pre-order DFS, post-order DFS, and BFS. The correct way to save a tree in a file. Removing from a binary tree. | ||||||
| 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. | ||||||
| Examinations. The starting point for virtual methods. Where we reached by the end. |
