EEN218 R (Programming 2) Spring 2012
Tue Thur 2:00-3:15 in MM312

Examinations:

Assignments:

All to be emailed to grader218 at rabbit.eng.miami.edu, Subject: Assignment N Your Name
    1   Due Noon Saturday 4th Feb.
       Implement both Insertion Sort and Bubble Sort. You may use the program in the notes for class 2 and just substitute in your own sort function.
Repeat the timing experiment and plot the graphs on logarithmic graph paper.
Determine the speeds of the algorithms in terms of both the "big O" notation, and as a formula that predicts the actual time in seconds for a given array size.
Put everything - your code, results, graphs, and conclusions - in a single word document.
2Due Midnight Tues. 28th Feb.
Supercalculator! Part one, details here.
3Due Midnight Thur. 29th March.
Linked List exercises, details here.
4Due Midnight Tues. 17th April.
Complete Supercalculator, with long multiplication and division, details here.

Some older notes on relevant topics:

Class History, etc.:

Last semester's web site
Class 1  Tue 17‑1‑2012   Quick introductions, etc. Seeing some algorithm analysis, introduction to binary trees, O(N) and O(log N) searches, software engineering by continuous refinement.
Class 2  Thur 19‑1‑2012   Experiments - sorting arrays of random strings and seeing how long it takes.
Using pointers and "new" for better control of arrays.
Class 3  Tue 24‑1‑2012   Review of basic unix commands and methods.
The magic of logarithmic graph paper: lin-log, log-log.
Results of timing our sorting program, plotted, reveal that it is quadratic.
Class 4  Thur 26‑1‑2012   Algorithm Analysis done the analytical way.
Comparing Selection, Insertion, and Bubble sort.
Class 5  Tue 31‑1‑2012   Exploring memory: seeing where things are kept in a running program. The stack and the heap, new and delete, segmentation faults and using the debugger.
Class 6  Thur 2‑2‑2012   The loop invariant as a way of understanding designs.
Mistakes with array accesses cause undetectable errors, so we made a Safe Array of Strings.
The Second Version was properly object oriented: protected, public, constructors, members, and methods.
Class 7  Tue 7‑2‑2012   Strings can cause very strange things when you use a pointer or array incorrectly: demo 1, demo 2.
With simple types, errors are much more likely to be undetectable, or to have their effect much later (demo 3).
Further adventures with the safe array of strings.
Class 8  Thur 9‑2‑2012   The minor usefulness of reference variables.
Making an array that can be resized, or even resize itself automatically.
~Destructors.
Class 9  Tue 14‑2‑2012   Things on the stack vs things on the heap, use reference params for objects with pointers to heap memory.
Defining operators, the complex number calculator, M a n d e l b r o t and J u l i a sets.
operator[] for our safe arrays (the sas3.cpp that I mistyped, it was the const).
Class 10  Thur 16‑2‑2012   Sometimes it is OK for member variables to be public, e.g. controlling growth.
Stacks are simple useful things, Reverse Polish Notation (RPN) for calculators.
Increasing array size incrementally (adding a few elements) always results in Quadratic time for filling it. Increasing the size by doubling each time makes the operation Linear, only twice as slow as knowing the correct size at the start.
Class 11  Tue 21‑2‑2012   Introducing Linked Lists at the supermarket.
Basic linked list implementation, adding items, scanning the entire list.
Class 12  Thur 23‑2‑2012   Why it is usually not sensible to put objects directly in linked-list links. Use pointers instead.
Searching and updating, the unnecessary complexity of adding items to the end.
Class 13  Tue 28‑2‑2012   Reminders about the various kinds of int.
Slightly more complex linked list operations. Adding to the end of a list (in a not very good way). Reversing a list the ignorant way which turns out to take quadratic time. Reversing a list the sensible way which is linear, much faster. Finding the length of a list, easy. Noticing that most of these operations are OK if you only do them rarely, but will be very time consuming if they are needed a lot.
The note about prototypes for methods.
Class 14  Thur 1‑3‑2012   Cubic, and Exponential, Time Comparisons.
A properly object-oriented linked list definition.
Class 15  Tue 6‑3‑2012   Test Day.
Class 16  Thur 8‑3‑2012   Slightly more complicated linked list operations: add_to_front, add_to_end, remove_from_front in the nicely object oriented version, but remove_from_end is still nasty.
Split and Merge, what could they be useful for?
Spring Break
Class 17  Tue 20‑3‑2012   Linked list review, and test stuff.
Class 18  Thur 22‑3‑2012   Inventing merge-sort. How fast is it?
Class 19  Tue 27‑3‑2012   Determining that the time for mergesort to sort a list of N items is O(N×log(N)), seeing what that really means.
Class 20  Thur 29‑3‑2012   Despite all the thousands of merge and split operations, the mergesort function is extremely easy to design: The C++ implementation. Experimental verification that the number of operations is at most 2×N×log2N.
Thinking about adapting it for sorting arrays.
Class 21  Tue 3‑4‑2012   Detailed thoughts about and lessons drawn from supercalculators.
Class 22  Thur 5‑4‑2012   Keeping programs modular and compartmentalised. CC -c to produce .o files, proper use of .h files, programs split into several files improves organisation and efficiency, and allows you to keep trade secrets but still sell software.
Class 23  Tue 10‑4‑2012   Introducing Binary Trees - Linked lists with two "next"s, built around the idea of the binary chop search: Today's designs.
Class 24  Thur 12‑4‑2012   Recursion makes tree programming so much easier.
Class 25  Tue 17‑4‑2012   Making sure we really understand why the recursive tree functions work. Why #define is bad - never use it.
Adding some more functionality to our tree program in preparation for measuring how "good" our trees are.
Class 26  Thur 19‑4‑2012   It is important to use your own code properly.
Properly object-orienting the whole tree program, then adapting it to calculate the average search time for any string. This is the random string generator, and this is the generator of strings in the perfect order for a balanced tree.
Class 27  Tue 24‑4‑2012   Second Test Day.
Class 28  Thur 26‑4‑2012   a better tree-statisticiser, big tree.
Experiments and analysis on trees. Put data in a tree then take it out again = sort, best case time is O(NlogN), worst case is O(N2). How fast is a real tree search? Best possible tree structure, average search time is exactly log2N - 1 operations; completely random structure even with 1,000,000 strings is only about 35% slower.
Exercises for Pre-Exam Confidence Building:
          with linked lists
          with binary trees
          with vectors