EEN218 R (Programming 2) Spring 2013
Tue Thur 2:00-3:15 in MM-203

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 Thursday 31st January.
       Write a C++ program that creates a large array of random strings (size to be chosen by the user) and sorts them into alphabetical order using insertion sort, selection sort, or bubble sort (as chosen interactively by the user). The program must accurately time how long each sort takes, and you must work out the relationship between array size and time taken.
Turn in your program, a screenshot or transcript of it working, the timings it produces, the graphs for the three algorithms, and the time formulas that you worked out.
(How to Time a Running Program), (Special graph paper here).
GIF and JPEG versions of the graph paper, which cheap programs like "paint" will be able to handle.
2Due: Part A - Tues 19th Feb., Part B - Tues 26th Feb.
Implement flexible resizable two dimensional matrices as objects.
3Due: Fri 5th April
Supercalculator! Part 1 - don't bother with division.
4Tues 26th March
Based on the solution you turned in, program question 3 from the midterm. Test it thoroughly, make it perfect. Do not use the wikipedia method. When it is perfect, make it into a complete quicksort.
5Due: Wed 3rd April
Simple linked list operations.
6Due: Mon 29th April
Supercalculator! Part 2 - just add division and negatives.
7Due: Thurs 2nd May
General linked list operations, and here's the data file.
8Due: Thurs 2nd May
Basic tree operations.
To contact the graders:
Elliot = e.beeman at umiami.edu
Paul = paul.gerald.levy at gmail.com

Some older notes on relevant topics:

Class History

Class 1  Tue 15‑1‑2013   Quick introductions, etc., Remembering how to use unix.
Thinking about random strings in preparation for sorting, the static variable.
Class 2  Thur 17‑1‑2013   What static variables really are (example). Stars for pointers, with functions array parameters and array results are really just pointers (example of exactly what not to do).
Visual comparison of Selection sort, Insertion sort, and Bubble sort.
Class 3  Tue 22‑1‑2013   Random number generators - good: random, srandomdev, bad: rand, srand.
Using the gdb debugger for run time errors, especially segmentation fault.
Timing: I had used the wrong graph paper file! correct one, wrong one. The times.
Verifying that a sort is correct, and useful argc, argv (example).
Class 4  Thur 24‑1‑2013   Dynamically creating permanent arrays with new.
The old database lab done the new way, introducing methods and constructors.
Class 5  Tue 29‑1‑2013   A step backwards, adding a constructor, rats! a default constructor too.
It's usually best to use pointers all the way.
We can even make the array grow when needed.
Class 6  Thur 31‑1‑2013   Heap memory compared to stack memory, and pointers to objects compared to just plain objects, in all the details. Lots of big pictures.
I hope you kept good notes.
A plan for an automatic safe database object.
Class 7  Tue 5‑2‑2013   The complete database object with automatic resizing and error protection.
Class 8  Thur 7‑2‑2013   Public, Protected, and destructors: now our database is fool-proof.
Using a template, we've got a safe resizable array of anything we want.
Class 9  Tue 12‑2‑2013   Default parameters, reference results, and even reference variables.
Stacks, and the reverse polish notation calculator.
Class 10  Thur 14‑2‑2013   The three simple sorting algorithms are all quadratic. What that means in practical terms for large databases: we'd better hope there is another way.
A cubic algorithm is hopelessly slow, but with some clever thinking, we can come up with a linear algorithm that solves the same problem, so maybe there is hope.
Class 11  Tue 19‑2‑2013   An object stored in a local variable or parameter gets its destructor called when the function ends, ruining the object. The solution is to use pointers or references.
The binary chop search: step 1 - manual, step 2 - automatic, step 3 - minimal, and why it is so fast.
Class 12  Thur 21‑2‑2013   For creating 2-D arrays, do you use an array of pointers to arrays or a single 1-D array, mapping A[i][j] to A[i*cols+j]?
The different sizes of ints: char, short, long, and occasionally long long; signed and unsigned.
Newton's method - for square roots it's even faster than the logarithmic binary chop
First thoughts about really really big numbers.
Academic alerts due
Class 13  Tue 26‑2‑2013   Some old tests: one, two, three, Don't worry about the "linked lists".
More about suitable implementation methods for very big numbers.
Quicksort - Making the sorting of large data sets practical.
Class 14  Thur 28‑2‑2013   Quicksort as it first appeared, and implementation part 1, part 2, the test system. Student results from 2011.
Class 15  Tue 5‑3‑2013   Test day.
Here is one of the old tests solved.
Class 16  Thur 7‑3‑2013   The effect of picking a bad pivot; an infallible partition algorithm; Producing pseudo-random numbers doesn't take much time.
A hard problem. Comparing algorithm speeds.
Spring Break
Class 17  Tue 19‑3‑2013   At the supermarket, introducing linked lists.
Building a list backwards then reversing it is still linear time.
Class 18  Thur 21‑3‑2013   Nice calm linked list operations. searching, adding to the front, adding in order, adding to the end, finding the length. Make an object to represent the whole list as well as an object for the individual links, then you can record the length or a pointer to the last link to speed operations up if necessary.
Class 19  Tue 26‑3‑2013   Reminder about templates: before and after; you can make linked lists of anything, even things that contain other linked lists.
Carefully considering add to front and and and remove from front and end. So long as you don't need to be able to remove from both ends, everything can be simple and efficient.
Class 20  Thur 28‑3‑2013   Exploratory development, complicated at first, but yielding a nice simple and very flexible way of finding or removing anything in a linked list.
Class 21  Tue 2‑4‑2013   Trying to make nice database functions that can work equally well on animals, humans, and numbers. First attempt only works for animals; Second attempt better but no good for numbers; Third attempt, numbers too. We've got map, now to think about reduce.
Class 22  Thur 4‑4‑2013   Map and Reduce with templates.
I think we've seen quite enough of templates now.
Class 23  Tue 9‑4‑2013   Introducing Binary Trees: just linked lists with two nexts. Recursion makes everything so much easier.
Class 24  Thur 11‑4‑2013   More practice with trees.
Review session with the lab guys: Sunday at 1 pm.
Class 25  Tue 16‑4‑2013   Even more practice with trees, the abstract case by case approach.
Recursion and induction are very similar - being sure it will work.
Class 26  Thur 18‑4‑2013   Test Day
Class 27  Tue 23‑4‑2013   Merge-sort on linked lists. Easy and fast O(NlogN).
Class 28  Thur 25‑4‑2013   Building a tree by hand, and different ways of printing a tree.