EEN218 R (Programming 2: Data Structures) Spring 2016
Tue, Thur, 2:00-3:15 in MM 315

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 Tues 26 Jan
       Reverse Polish Calculator using a vector.
2Due Tues 2 Feb
Implement the 2-D Matrix object.
3Due Tues 23 Feb
Make your own vector.
4Due Sat 2 Apr
Timed comparison sorting linked lists by insertion-, bubble-, and selection-sort.
5Due Tue 19 Apr
Enormous integer calculator.
5Due Sat 30 Apr
Something with trees. The data file.
Lab guys for questions and help

Some older notes on relevant topics:

Class History

Class 1  Tue 12‑1‑2016   Quick introductions, etc.
Vectors, just like arrays, but flexible.
Reverse Polish Notation Calculator.
Class 2  Thur 14‑1‑2016   The abstract data structure Stack, easily implemented with vector.
Really understanding how to deal with Reverse Polish Notation. (combined notes).
Trying to get cin to handle the input but not quite succeeding.
Converting strings to ints, and ints to strings (a clue anyway).
Class 3  Tue 19‑1‑2016   Int to string conversion - adapting the recursive function,
realising that a loop will do it,
trying to get rid of the list of digits, but running into trouble with C++'s type rules. Pesky arrays of chars,
it works at last, but it's ugly..
An istringstream in action.
Class 4  Thur 21‑1‑2016   Tying off a loose end, an ostringstream doing its thing too.
C++'s idea of two dimensional arrays isn't very good. We'll take matters into our own hands and create an "array2d" struct to do the job properly.
Methods, constructors, protected:, public:
Class 5  Tue 26‑1‑2016   How arrays are really arranged. Can we explain this behaviour?
That's why the array2d object is so important.
Arrays with more than one dimension as parameters to functions.
Making pointers (&) and following them (*). How references are implemented.
Why you should never even try to return an (ordinary) array from a function.
Class 6  Thur 28‑1‑2016   Making your own web page.
The stack and the heap.
new and delete.
We can now make our array2d object resizable.
Class 7  Tue 2‑2‑2016   Making our own vectors, part 1.
disc. Tue 2nd Discussion section, 5:00.
Class 8  Thur 4‑2‑2016   A program that goes wrong, it needs the debugger.
Introducing templates and typedefs with a special little storage object.
Class 9  Tue 9‑2‑2016   Making our own vectors, part 2.
Lots about templates and defining our own operators.
disc. Tue 9th Discussion section, 7:00.
Class 10  Thur 11‑2‑2016   A little database, unfortunately not designed very well.
1. Need to add a default constructor in order to create arrays. That destroys our guarantee of a deliberately set-up object through a specific constructor.
2. Completed find function but forgot to return specific value when search fails. Unpredictable results, sometimes program crashes.
3. Return easily recognised bad value when search fails. Not very satisfactory.
4. Tried to give someone a raise, nothing happened. Turns out we were only working on a copy of the data.
Pointers save the day! An array of pointers to objects instead of an array of objects solves all our problems.
We were also introduced to printf().
Class 11  Tue 16‑2‑2016   Not everyone has a boss, objects can refer directly to other objects.
Shopping time, we invent the Linked List.
disc. Wed 17th Discussion section, 6:50.
Class 12  Thur 18‑2‑2016   Lots about linked lists. Adding and removing from the front, search, printing all items, finding the length, realising that there should be a class to represent a whole list and a class/struct to represent the links, they are different things after all.
Class 13  Tue 23‑2‑2016   Try this out for practice. 100, 136, 192. Practice, practice, practice.
Some "bitwise" operations that can be used to speed programs up.
The idea of memoised functions.
Class 14  Thur 25‑2‑2016   More linked list operations: adding to the end, remembering where the end is. Adding in the right place in an ordered list. Important thoughts about how long things take. Sorting a linked list.
disc. Sun 28th 1 p.m., Pre-test review. Meet near EB 237, Lab guys will find a room.
Class 15  Tue 1‑3‑2016   Many things reviewed.
disc. Wed 2nd Discussion section, 6:50.
Class 16  Thur 3‑3‑2016   First Test.
A sample test, and its solution,
and another mini-test, with its solution.
Another sample, and its solution.
Expect three equally weighted questions. Do not expect questions about timing to feature as heavily as they did in some of these samples. Topics are covered in a different order from one semester to the next. Prepare for what we have covered in class.
Break
Class 17  Tue 15‑3‑2016   Finding out what a puppy is in at most 11 steps. Binary Chop Search, max number of steps = log2(number of items), serach through a billion items in 30 steps. Unfortunately it doen't apply to linked lists, and requires the data to be sorted.
Sorting linked lists. Insertion sort - remove items in most convenient order from original list, put effort into inserting them in the right place in the sorted results, expect quarter N squared steps.
Bubble sort - compare neighbours and swap if out of order, repeat until none are out of order, expect half N squared steps, but can finish very early. Both Quadratic = too slow for large data.
Class 18  Thur 17‑3‑2016   Selection sort for linked lists, also quadratic. In-place sorting, really working out the time and big-O for an algorithm.
Class 19  Tue 22‑3‑2016   Joshua's day.
Class 20  Thur 24‑3‑2016   The many many things to learn from the test.
Class 21  Tue 29‑3‑2016   Merge sort: as a cooperative effort, and how it can be done on files rather than in RAM for huge data sets. However it's done, the time works out to O(N×log2N).
Splitting a linked list in two; merging two already sorted linked lists into one.
disc. Wed 30th Discussion section, 6:50.
Class 22  Thur 31‑3‑2016   Completing merge-sort on linked lists.
Proof by induction.
Integers of unlimited size and perfect precision implemented as linked lists of digits.
Class 23  Tue 5‑4‑2016   More about big-integer methods.
Copy constructors and assignment operators - when sharing pointers goes wrong.
Introducing Binary Search Trees.
disc. Wed 6th Discussion section, 6:50.
Class 24  Thur 7‑4‑2016   More trees: node and tree are separate objects; searching for an item both with a loop and recursively, adding a new item both with a loop and recursively.
disc. Sat 9th 1 p.m., Pre-test review. Meet near EB 237, Lab guys will find a room.
Class 25  Tue 12‑4‑2016   The tree assignment, Accessing the command line and environment variables.
Review of timing and big-O related matters.
Printing the contents of a binary tree in order.
disc. Wed 13th Discussion section, 6:50.
Class 26  Thur 14‑4‑2016   ANNOUNCEMENT!
Second test.
Class 27  Tue 19‑4‑2016   Even more about binary trees.
Class 28  Thur 21‑4‑2016   Reviews of various things.
review Sun 1 May Pre-final review, 5 p.m.
and Mon 2 May Pre-final review, 12 Noon.