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

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 Tue 4th Feb.
       Big Numbers (part 1)
2Due Thur 20th Feb.
Big Numbers (part 2)
3Due Mon 24th Mar.
Linked list database sorting
4Due Mon 7th Apr.
Analysis of efficient sorting
5Due Sat 26th Apr.
Basic binary tree operations
6Due Fri 2nd May.
Complete, useful bignum calculator, with trees.
2Mon 5th May
Nothing turned in after this date will be graded.
Elliot = e.beeman at umiami.edu
Austin = a.clifton at umiami.edu

Some older notes on relevant topics:

Class History

Class 1  ‑ Mon 13‑1‑2014   Quick introductions, policies and things.
Remembering about files. <fstream> ifstream x; x.open("xxx"); if (x.fail()) after an attempt to read. Processing big files doesn't necessarily require their content all to be held in memory at once. The corrupt TA example.
Class 2  ‑ Wed 15‑1‑2014 Adventures with arrays, the function that put a new item in the right place in a sorted array.
An example of how dangerous C++ arrays can be.
Class 3  ‑ Wed 22‑1‑2014 Exploring binary and the bit-wise operators: example 1, example 2.
Finding out where variables live: first version, nicer version.
Looking at the contents of memory without knowing the variables' names.
Class 4  ‑ Mon 27‑1‑2014 Inventing big numbers.
Class 5  ‑ Wed 29‑1‑2014 Lots of things: using the debugger to trace run-time errors,
Telling cout how to print our own objects,
Constructors and methods for object oriented programming.
Class 6  ‑ Mon 3‑2‑2014 Constructors and methods, much more gently this time.
Class 7  ‑ Wed 5‑2‑2014 (what did "two boards" mean?) (using your own unixes)
We found out what the factorial of 500 is, and thought about properly testing programs.
Then we learned about making operators.
Class 8  ‑ Mon 10‑2‑2014 More object orientation: public and protected.
The fool-proof Safe Array that prevents insidious errors.
abort() is kinder than exit(1) to the debugger. Default parameters. Bad macros, __LINE__
Class 9  ‑ Wed 12‑2‑2014 Clearing up some little things. :: and ., operator<<. The point of the safe-array, operator[] and reference results, Never having to worry about undetectable errors again. Arrays can't change size, but we're about to see something that lets us get around that.
Class 10  ‑ Mon 17‑2‑2014 Pointers, New, Delete, and the Heap.
Class 11  ‑ Wed 19‑2‑2014 Putting everything together, the object that behaves like an array that grows to whatever size is needed.
Class 12  ‑ Mon 24‑2‑2014 Pointers are our friends:
This database program doesn't use pointers. It doesn't work, in many mnay ways.
This version uses pointers properly, and works properly.
Class 13  ‑ Wed 26‑2‑2014 Linking things together: Everyone has a boss, except Olivia.
At the supermarket.
A real Linked List.
Sat 1st March Voluntary review session, 2.00 to 4.00 pm, in EB237 (the 118 lab room).
Class 14  ‑ Mon 3‑3‑2014 So many linked list examples that we are all thoroughly sick of them.
Practice until you can do it almost without thinking.
Class 15  ‑ Wed 5‑3‑2014 Mid Term Day.
Some old tests: one, two, three.
Spring Break
Class 16  ‑ Mon 17‑3‑2014 Don't confuse the links with the contents of a linked list.
The dreaded database file: people1.txt.
Sorting a linked list.
Class 17  ‑ Wed 19‑3‑2014 linked list sorting diagrams, and
we looked at Selection sort, Bubble sort, and Insertion sort, and found that all three whether applied to linked lists or arrays are always quadratic algorithms O(N squared): 3 million years for the government to process its SSA databases.
Class 18  ‑ Mon 24‑3‑2014 Other algorithm types: logarithmic (e.g. binary chop search), linear (e.g. search unsorted list), cubic (e.g. solve system of N simultaneous equations), exponential (e.g. boolean satisfiability), and even worse (e.g. travelling salesman).
The serious consequences.
An odd idea: to sort a list, split it in half, sort the two halves individually, then merge them back into one. Seems like more work but it's faster.
Class 19  ‑ Wed 26‑3‑2014 Analysis of the speed of merge-sort, exactly why it is O(N times log N), and just how significant that is.
Class 20  ‑ Mon 31‑3‑2014 Careful examination of the split and merge procedures and the recursive sort function.
How to debug with linked lists (and other pointer-based structures).
Class 21  ‑ Wed 2‑4‑2014 There is a difference between a Link in a list and a whole linked List, so have separate objects for each of them. That gives us a convenient place to keep information that pertains to a whole list, such as where the end is or how long it is.
Class 22  ‑ Mon 7‑4‑2014 Doubly linked lists: extra overhead, but make insertion and deletion easy at any position.
Introduction to Binary Trees.
Class 23  ‑ Wed 9‑4‑2014 The magic of logarithmic graph paper: lin-log, log-log.
Results of timing a sorting program, plotted, reveal that it is quadratic.
Discovering the algorithm for building a binary tree from scratch, and for searching one.
Sun 13th Voluntary review session, 3.00 to 5.00 pm, in EB237 (the 118 lab room).
Class 24  ‑ Mon 14‑4‑2014 Some more review, then some more work on trees.
Class 25  ‑ Wed 16‑4‑2014 Second test, Some old sample questions.
Class 26  ‑ Mon 21‑4‑2014 Nice simple recursive functions for printing whole trees. Pre-order and in-order traversals. Adding enough information to be able to reconstruct the tree exactly. Today's experiments.
Class 27  ‑ Wed 23‑4‑2014 Developing functions that can read back the result of a pre-order or in-order print, and completely reconstruct the original tree. Trees that represent arithmetical expressions, and the important and useful thing: a program that reads an arithmetical expression as a tree and evaluates it.
Sun 27‑4‑2014 1 to 3 pm, Pre-final review session.
Mon 5‑5‑2014 Last Chance - Nothing turned in after this date will be graded.