EEN218 R (Programming 2: Data Structures) Autumn 2015
Mon, Wed, 5:00-6:15 in MM317

Examinations:

Assignments:

All to be emailed to grader218 at rabbit.eng.miami.edu, Subject: Assignment N Your Name
Always include transcript/screenshot of a successful run.
    1   Due Sat 26 Sept.
       The special sorting array.
2Due Mon 12th October.
Basic Linked Lists
3Due Mon 26th October.
The special sorting array revisited
4Due Sat 14th November.
Big Numbers, part one.
5Due Wed 9th December.
Big Numbers, complete.
6Due Wed 16th December.
Binary Tree Database
Lab guys for questions and help

Some older notes on relevant topics:

Class History

Class 1  Mon 24‑8‑2015   Quick introductions, etc.
The unsafe array access example: one, two,
Class 2  Wed 26‑8‑2015   The separateness of the CPU and the RAM. Everything in memory has an address: the numeric location of the first byte or ram it occupies. The address of an array is the same as the address of its first element. Using the & operator to find the address of something - but never use & with an array or function, it is applied automatically.
Demonstrating that C++ does not know the length of an array parameter.
Seeing the addresses of everything in a program.
The stack and the stack pointer creating local variables.
Class 3  Mon 31‑8‑2015   The * operator (follow this pointer) is just about the opposite of the & operator. We are using it now in a rather obscure way, to scan the memory of a running program. It is about to become so much more practical.
Here is our scanning program, run it and examine its output. Make sure you can identify all of the stack frames and understand their contents.
Class 4  Wed 2‑9‑2015   If you use [ ] after a pointer, C++ will assume it is a pointer to an array, and access that array in the normal way.
We made a struct that acts a lot like an array, except that it can be resized at will.
Class 5  Wed 9‑9‑2015   The resizable, error-proof array and it's C++ features in great detail, public and protected, struct and class, set and get methods, flag members to fine-tune behaviour, automatic resizing, operator [ ], reference results.
Class 6  Mon 14‑9‑2015   Lots of details about reference parameters, reference results, and reference variables.
A deliberate mistake, to let us see the debugger in action.
Class 7  Wed 16‑9‑2015   Why pointers are so useful, part 2.
The starting point, a little employee database.
It didn't even compile. Some unsatisfactory fixes are needed.
Now we put in the find operation. Unsuccessful searches ruin everything.
Another unsatisfactory fix.
At least we can make a case-insensitive search.
Adding the ability to give someone a raise. It doesn't work!
Pointers save the day. Pointers are our friends.
disc. Thu 17‑9‑2015   6:50 pm in EB 237 - first discussion session.
Class 8  Mon 21‑9‑2015   More uses of pointers, NULL, and this: Self-referential structures, not everyone has a boss.
Introducing linked lists at the supermarket.
Class 9  Wed 23‑9‑2015   Implementation of linked list operations, primarily adding, searching, accumulating, counting. Remember to use pointers when the list contains objects. Remember the NULL at the end and for initialisation.
disc. Thu 24‑9‑2015   6:50 pm in EB 237 - discussion session.
Class 10  Mon 28‑9‑2015   Even more work on linked lists.
Class 11  Wed 30‑9‑2015   Classes of algorithms (based on time). Linear: search unsorted array, build linked list sensibly. Quadratic: build linked list foolishly, bubble sort, selection sort, maximum sum subsequence done intelligently. Cubic: brute-force maximum sum subsequence.
disc. Thu 1‑10‑2015   6:50 pm in EB 237 - discussion session.
Class 12  Mon 5‑10‑2015   More algorithm classes: Logarithmic - binary chop search, to-the-power-of; exponential - the knapsack problem; factorial - the travelling salesman. Consequences: the great significance of the big-O.
Class 13  Wed 7‑10‑2015   Splitting a linked list into equally sized halves (three methods). Merging two ordered (sorted) linked list into a single ordered linked list. Why that is interesting: we've now got a new sorting algorithm.
Class 14  Mon 12‑10‑2015   Analysis of the mergesort algorithm. It is O(NlogN). Just how much better that is than the quadratic algorithms we already knew.
Short review of vectors.
Class 15  Wed 14‑10‑2015   Test day.
A sample test, and its solution,
and another mini-test, with its solution.
Another sample, and its solution.
Class 16  Mon 19‑10‑2015   Separate compilation: salib.h, salib.h, prog.cpp.
Templates, demonstrated here on a weird little triad thing.
Thinking about very big numbers.
Class 17  Wed 21‑10‑2015   Templates have an unfortunate effect on separate compilation. (here's the new .h file)
More thoughts on the implementation of giant numbers. (here's the first part)
disc. Thu 22‑10‑2015   6:30 pm, discussion session.
Class 18  Mon 26‑10‑2015   More big numbers, and we found out what 500 factorial is.
Also main's parameters argc and argv, and a little bit about C strings.
Class 19  Wed 28‑10‑2015   Using const properly can be quite demanding.
Introducing binary trees.
disc. Thur 29‑10‑2015   6:30 in EB 304, Discussion section.
Class 20  Mon 2‑11‑2015   What (I hope) we learned from the test.
Class 21  Wed 4‑11‑2015   How methods are made - converted into an ordinary function with a special name, and a hidden parameter called this. ptr->method() can work even if ptr is NULL.
A non-recursive tree insertion method, just like adding to the end of a linked list.
Printing the contents of a tree, and some testing: what we had in class, and a classier version. I know, that's a terrible pun.
disc. Wed 4‑11‑2015   6:30 in EB 304, Discussion section.
Class 22  Mon 9‑11‑2015   More adventures with trees. Structs within structs, tracing the recursive insertion to strengthen our ideas about how the printall method works. An assortment of print methods, including a print-by-layers which gives an easy to implement "breadth first search".
Class 23  Wed 11‑11‑2015   Even more fun with trees. Printing with cleanly visible structure (printnicely), think about using a graphical system to rotate it to the normal view. Discovering another NlogN sorting algorithm (treesort), but it uses (temporarily) a lot of memory.
Class 24  Mon 16‑11‑2015   Mergesort is easy, but needs a lot of extra space when applied to an array.
Quicksort. Just partition the array around a pivot, and recursion takes care of the rest. Try it yourself, just implement to partition method and test it very carefully.
Class 25  Wed 18‑11‑2015  
disc. Wed 18‑11‑2015   6:30, probably in EB 304, Discussion section.
Class 26  Mon 30‑11‑2015   More practice, and experimentally finding how good a binary tree made from random data is, it turns out to be on average only about one third slower than the perfect case.
Class 27  Wed 2‑12‑2015   Test Day. Here's a sample.
Class 28  Mon 7‑12‑2015   Looking over some key things again: deletion from a binary tree, high precision division, timing calculations when it's O(NlogN).
Review Sun   Sunday 13th at 12 noon.
In EB 216 or 237 or 304. It will be made easy to find.