| 1 | Due: Thursday 7th September. | |||
| A reverse-polish calculator with variables and functions. | ||||
| 2 | Due: Saturday 30th September. | |||
| Supercalculator - int calculations with unlimited precision. | ||||
| 3 | Due: Saturday 21st October. | |||
| More functionality to your supercalculator. | ||||
| 4 | Due: Thursday 9th November. | |||
| Sort a database of a million people. | ||||
| 5 | Due: 5:05 p.m., Thursday 16th November. | |||
| Work out how to implement doubly-linked lists. | ||||
| 6 | Due: Wednesday 13th December BEWARE: no extensions will be possible. | |||
| Binary tree database. | ||||
| Introductory Bits. Everyone already has an account on the server. username = UM email before @. Can't cover everything, C++ is a very big language. A word about pointers. How dangerous arrays are, 10, 100, 200, 1000. Take-aways from today's class. | ||||||
| Making arrays safe. Introducing vectors from the standard library. So why does anybody use arrays at all any more? Take-aways from today's class. | ||||||
| With a vector you should habitually use at rather than []. Abstract Data Types and Concrete ones. The stack as an example of an ADT. Old fashioned C strings, and the useful strtod function. Reverse Polish Notation: a use for a Stack. Beginning the implementation of a vector: create and enlarge. Take-aways from today's class. | ||||||
| Completing the vector of doubles, defining operators + * [] and so on. Reference results - just like reference parameters. Separate compilation, .cpp, .o, and executable files, compiling and linking. Templates for functions and classes. Templates go in .cpp files. Take-aways from today's class. | ||||||
| Mention HKN. Examples of many class/struct related things. Default constructor, copy constructor, proper assignment, lazy replacement. Class methods, class constants, const methods, output not method, int for post. Why have copy constructors? Take-aways from today's class. | ||||||
| got up to <<. class variable, methods are outside class def. Fast graphics operations, Bad C++ two-dimensional arrays. This would be better but for the fact that it doesn't work. How to make a safe multi-dimensional array/matrix. A bitmap or bitarray. Got to set knowing intnumber and bitnumber. 32 or 64? Take-aways from today's class. | ||||||
| All the bit-wise operators with examples. Finishing the bitmap. Exceptions: one, two, three. Assign result before destroy at end of function. Take-aways from today's class. | ||||||
| Supercalculator. 32 or 8? maxnegint is -2147483648. An attempted database. Take-aways from today's class. | ||||||
| Making the database work properly by using pointers. A reference implementation of a superint type. Today's clicker questions. Stack and heap allocation, demostration. At the supermarket. Take-aways from today's class. | ||||||
| Practical linked list operations, we were half way through reverse at the end. Take-aways from today's class. | ||||||
| Updated HKN tutoring times. Supercalculator implementation tips. Today's clicker questions. Make use of a linked list's natural tendency to be backwards to reverse on efficiently. Finding the length (just record it if that's a frequent operation). Adding to the end, the inefficient way. Take-aways from today's class. | ||||||
| Just reminders: The essential Unix commands and pico/nano editor controls. The efficient way to add an item to the end of a linked list. Removing items in all sorts of ways. Accumulating a compound value. Take-aways from today's class. | ||||||
| accumulating, with a template too, Today's clicky questions. Destructor or destroy all? Selection Sort on a linked list. We discover that it is quadratic. Complexity, what O(...) means, and a way of determining it. Take-aways from today's class. | ||||||
| Today's clicky questions. Selection sort on an array, Bubble sort both ways, Insertion sort both ways. Take-aways from today's class. | ||||||
| A short word about stod's "worthlessness". The third assignment. Today's clicky questions. You must verify. About insertion sort on an array, how to avoid the need for a second array. Take-aways from today's class. | ||||||
| Test review for as long as it takes. We discovered Merge-sort in an educational exercise at the end. | ||||||
| First test. Topics: 1. Vectors. How to use them, how they work, how to implement them, 2. Multi-dimensional arrays or matrices. how they work, how to implement them, 3. All about linked lists, 4. The array/vector/linked list sorting algorithms. 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 (not question 6), and its solution. | ||||||
| An ordinary linked list of strings add an enumerator. Merge-sort on a linked list. Counting the number of operations reveals that its time is better than quadratic, but what? Analysis shows numper of ops = 5×N×log2N compared to the familiar ½×N2. Take-aways from today's class. | ||||||
| How much faster is 5×N×log2N than ½×N2?
and the answer. Merge-sort on an array, the loops are a bit complicated. Introducing Quick-sort, only for arrays this time. Take-aways from today's class. | ||||||
| Next assignment and cmath things. Questions about the mid-term if necessary. Today's clicky question. You must verify. The loop's invariant and variant: confirmation that it is right. Take-aways from today's class. | ||||||
| Our second partition method animated, The entire quicksort algorithm animated. Quicksort's first appearance, the algorithm part 1, part 2. The test system. A little bit of number theory. Inheritance, Polymorphism, Virtual Methods in 8 steps: one, two, three, we only got to the third. Take-aways from today's class. | ||||||
| The remainder of Inheritance, Polymorphism, and Virtual Methods:
four,
five,
six,
seven,
eight. Today's clicky question. You must verify in class. What Binary Trees are all about. Take-aways from today's class. | ||||||
| More binary trees. Some non-recursive methods, print all, and a new fast sorting algorithm. | ||||||
| Preparation for Thursday's test as needed. | ||||||
| Second mid-term. The topics are: Merge-sort (on linked list and array), Quick-sort, Big O() when logarithms or exponentials are involved, Object orientedness, inheritance, polymorphism, virtual methods, Doubly-linked lists. For samples see the last three samples for the first test. | ||||||
| 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. How a queue makes BFS work; BFS finds the easiest to reach solution. A tree to represent normal exressions, evaluating it, building from forward polish. | ||||||
| Using the debugger. Virtual in the right order. A number of things about encryption. | ||||||
| Another binary tree question, the 7th real question on the final. Question 7 on the third sample for the first mid-term is also on this topic. Deleting a data item from a binary tree. Hints of future things to fill the last few minutes: 2-3-trees for guaranteed balance, hash functions for digital fingerprints and fast data access. I had remembered the topic that I had in mind, what we actually did is much more useful. Last week I said I'd post the superint-related cryptography code. Here it is. |
