| 1 | Due: Sunday 29th January. | |||
| The RPN calculator. | ||||
| 2 | Due: Sunday 12th February. | |||
| Make your RPN calculator understand variables. | ||||
| 3 | Due: Wednesday 1st March. | |||
|
Linked list database. here is the database. | ||||
| 4 | Due: Saturday 8th April. | |||
| Enhancements to the linked list database. | ||||
| 5 | Due: Thursday 4th May. | |||
| Binary tree database. | ||||
| Thursday 11th May is the absolute drop-dead deadline for everything. | ||||
| 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. | ||||||
| Introducing vectors from the standard library. So why does anybody use arrays at all any more? Reverse Polish Notation: a use for a Stack. | ||||||
| An aside: three new things. (null.cpp). How vectors work: making our own version. It'll take a few steps. Here's where we got (I made a careless mistake with the delete statements, it is corrected here). | ||||||
| References, templates, and separation:
vector1.cpp,
vector2.cpp,
vector3.cpp,
vector4.cpp. Matrices and mathematical vectors: the starting point, and the generalised version that doesn't work. | ||||||
| Operator overloading. Why C++ demands some dimensions but ignores others, the layout of a 2-D array. Two sensible ways to create a two-dimensional array. | ||||||
| Another class example, introducing "static", and += again, and <<, An attempt at a small database. That database corrected and enhanced, pointers are out friends. | ||||||
| A quick word about istringstreams. << >> fail str clear. Ram, Rom, Disc, Volatile, Sram, Dimm, Core, Heap, Stack: the demo program. At the supermarket: inventing the linked list. Making a linked list (the set-up anyway). Where we got in implementing the supermarket. | ||||||
| An aside: Tuesday's address demo program. Structure, names, globals (maybe one struct, namespace X { }). Returning pointers to local objects: Bad. Using the debugger: wrong.cpp. | ||||||
| Steer clear of using maps for a while. Completing the supermarket program. General linked list methods, and adding to the end the slow way, Adding to the end of a linked list the sensible way. | ||||||
| An example of unacceptable garbage. External help for those troubled by pointers. More linked lists: is_present, links should be protected, a destructor, remove, reverse. All those things in one program. | ||||||
| When will the first mid-term be? Splitting a list into two parts, Merging two pre-sorted lists, The idea of the "big O" notation, time = O(N) etc. Merge-sort on a linked list. Bubble-sort on an array. | ||||||
| Analysing bubble-sort, here's the triangular loopless version. Bubble sort is quadratic. It can be sped up for special circumstances, but remains quadratic. Selection sort, it is quadratic too. | ||||||
| Reading complicated declarations, pointers, arrays, function variables, and mixtures. Typedefs. Insertion sort. Shaker sort, a bidirectional bubble sort. | ||||||
| Sorting linked lists: Bubble sort, Selection sort, Thoughts about insertion sort. | ||||||
| Read grading comments even when you get 10/10. Test .fail() after trying to read, not before. Test preparation, the vector question we did in class. | ||||||
| First mid-term. Topics to be ready for: 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, and its solution, Another sample, and its solution. Another sample, Yet another sample, and its solution. (remember that some of these samples cover test 2 material). | ||||||
| Break | ||||||
| Relocated to room 216 in main engineering building, just for today. No zoom video recording for today, sound only. The classrom didn't have a camera. Three dimensional matrices and selection sort on a vector. | ||||||
| Where we left off: the end of question 2, all finished now. Exploring a graph: the graph itself, the adjacency matrix, and the program so far. | ||||||
| (argc and argv, << has higher priority than ?), continuing where we left off. The completed program almost worked, but immediately got stuck in a loop, Introducing the Closed Set, implemented as a bitmap, The program worked, but actually found almost the longest possible path, Introducing the Queue to solve that problem. | ||||||
| Second mid-term. | ||||||
| The operations on a queue and why it is useful, The possibility of a double-ended queue, but it isn't neeed here, Implementing a Queue to find shortest paths. Here is the corrected code with the debugging still in it. | ||||||
| Could use the queue as its own closed set, A slight detour to get us ready: simple beginning, basic inheritance, virtual methods, the dynamic cast. A searchable vector using inheritance, The final result. The idea behind binary trees. | ||||||
| Mergesort and Quicksort. | ||||||
| More on mergesort and quicksort, including analysis. | ||||||
| Getting somewhere with binary trees, Searching, inserting, and printing. Our two stages: one, two. | ||||||
| A bit of pre-test review. Complete run-through of a recursive tree print. Printing a tree so that its structure/shape is visible. | ||||||
| Third mid-term, topics: 1. Fast sorting, O(NlogN) times, etc. 2. Sorting linked lists, 3. Graphs, representation and searching, 4. Binary trees. | ||||||
| More about printing. Another recursive insertion method. | ||||||
