EEN218 R (Programming 2: Data Structures) Spring 2015
Mon Wed 5:00-6:15 in MM313

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 7th Feb.
       Flexible Resizable Array
2Due Sat 21st Feb.
Giant Numbers, part 1
3Due Thur 2nd Apr.
Very-fast merge sort
4Due Wed 15th Apr.
Linked list database
5Due Tues 5th May.
Giant Numbers, part 2
6Due Sun 26th Apr.
Binary tree database
Sat 2nd May:
Hard absolute deadline for all assignments except number five.
Lab guys for questions and help:
    Austin = a.clifton at umiami.edu
    Davis = davislabhelp118 at gmail.com
    Jonathan = Jonathan.Edwards94 at gmail.com

Some older notes on relevant topics:

Class History

Class 1  Mon 12‑1‑2015   Quick introductions, etc.
The bad program that illustrates the dangers of arrays in C++.
RAM is just a giant array, everything to do with your program is stored in it somewhere. To access a variable you just need to know its index.
(don't worry about the messy picture at the end, you'll see it done more neatly).
Class 2  Wed 14‑1‑2015   The bad program is extended so that we can see exactly which locations in RAM contain all the variables and other things. From this we build up an accurate memory map showing where the static area (code and globals) and the stack (local variables) are and how they behave.
Solving the unsafe array problem, using object-oriented techniques we can protect an array against incorrect accesses. This is of course an extremely basic example.
Class 3  Wed 21‑1‑2015   All sorts of new things: Sensibly protecting the right things ... Templates can be interesting ... At last, using the heap.
Class 4  Mon 26‑1‑2015   Constructors and destructors, NULL, uninitialised pointers. All about correct use of the heap and new and delete.
Class 5  Wed 28‑1‑2015   The triads example of a templated struct (and I've sorted out the mystery error).
The example that illustrated use of the debugger.
Class 6  Mon 2‑2‑2015   The better debugger example.
More of "triads", illustrating operator definition and how templates can be quite helpful but can also grow quickly into something too complicated.
Introducing C strings, which are not C++ strings.
Class 7  Wed 4‑2‑2015   More time pushing pointers into your brains.
char, unsigned char, signed char, short int, int, long int, and the ill-defined even longer int. We are about to create ints with vast numbers of digits.
Todays review session, 6.30: room search will start at EB 304. Friday's, 2.30 in EB 237 (the 118 lab room).
Class 8  Mon 9‑2‑2015   Considering methods for giant integer arithmetic. What terrible things happen when an object containing a pointer to heap memory is copied (when it is passed as a parameter). Defining your own copy constructor (not always a good solution). Why passing objects by reference is nearly always the only way to go.
Class 9  Wed 11‑2‑2015   Serious analysis of the three simple sorting algorithms, bubble sort, selection sort, and insertion sort.
Big Ohs.
The old triangular program.
Todays review session, 6.30: room search will start at EB 304. Friday's, 2.30 in EB 237 (the 118 lab room).
Class 10  Mon 16‑2‑2015   Bubble sort's occasional advantage, which leads to shaker sort.
All sorts so far have been quadratic, is that a pattern? A reminder that we definitely know of linear algorithms, and a taste of something nasty, a "sixtic" algorithm.
How terrible time can get (gorillas, etc).
Class 11  Wed 18‑2‑2015   A reminder of the binary chop method, and a proper analysis to show that it is logarithmic in time, and just what a difference that makes.
Beginning to see a much faster but quite mystical sorting method.
Class 12  Mon 23‑2‑2015   All about const, and accidental copying causing multiple deletes of the same thing.
Class 13  Wed 25‑2‑2015   Don't do this.
Merge-sort in all its detail.
Class 14  Mon 2‑3‑2015   Review of all sorts of things.
Class 15  Wed 4‑3‑2015   Test Day. Particularly be ready for these things.
Sample one, sample two.
8th to 14th Break
Class 16  Mon 16‑3‑2015   Why vectors should grow by multiples in size rather than increments (size*=N rather than size+=N): it changes the overall time from quadratic to linear.
If you're using objects, you should almost always be using pointers to those objects instead, and exactgly why.
Class 17  Wed 18‑3‑2015   Not everyone has a boss.
At the supermarket: Linked Lists.
Class 18  Mon 23‑3‑2015   Lots of lnked lists. Adding to the beginning, searching, counting the length. Realising it is better to have a simple struct to represent a link, and a separate class to represent the list as a whole. Adding to the end and recording the length become easy.
Class 19  Wed 25‑3‑2015   Templates make linked lists so much more useful. A generic find method that is given (as a parameter) a function that detects the desired data item. A linked list is a good implementation of a stack. Reverse Polish Notation for calculations.
Class 20  Mon 30‑3‑2015   Doubly-linked lists, gdb (again), applications of lists, and an example audio application.
Class 21  Wed 1‑4‑2015   More linked list operations. Removing from anywhere, and a special implementation of merge-sort for linked lists.
Class 22  Mon 6‑4‑2015   Introducing binary trees. The logic behind them: linked lists adapted to make fast (binary chop) search possible. General method for search and insertion.
Class 23  Wed 8‑4‑2015   More trees, different insertion methods, in-order printing.
Review 2  Sun 12th   Voluntary pre-test review session, in the lab room, 2.30 pm.
Class 24  Mon 13‑4‑2015   All sorts of practice, Map Reduce (and Filter). etc.
Class 25  Wed 15‑4‑2015   Test Day. Some old sample questions.
Class 26  Mon 20‑4‑2015   Getting useful information while printing a tree.
Plain unadorned print, just for reference
Indentation shows the structure
Gives turn-by-turn instructions for finding each node
Drawing the tree, showing the pointers, is much more informative
Parentheses gives the same information. Harder for a human to read, but much easier for a computer to read.
Also reading trees.
Reading and reconstructing a previously printed tree
The same again, but made nicer, and with a better tree printer
Class 27  Wed 22‑4‑2015  
Review Sat 25 Apr   Voluntary pre-test review session, 1.00 pm.
Deadline Sat 2 May   Nothing received after this date, except for assignment 5 (big numbers), will receive a grade.