EEN218 R Data Structures Spring 2018
Tue, Thur, 2:00-3:15 in MM 202

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: 2nd February
       Stack-based reverse polish calculator.
2Due: 24th February
Two dimensional array objects.
3Due: 9th March
Race between sorting algorithms.
4Due: 6th April
Calculator for giant integers.
5Due: 30th April
Binary tree database.

Class History

Class 1  Tue 16‑1‑2018    Macintosh log in - use terminal and type ssh -oHostKeyAlgorithms=+ssh-dss username@rabbit.eng.miami.edu
Introducing a variable-sized array.
Class 2  Thur 18‑1‑2018 Pointers and arrays and new and delete:
Looking at where things are located in RAM.
Making an array that can be resized on demand.
Class 3  Tue 23‑1‑2018 Review of *, new, and delete.
C++'s vector class: Our previous example reprogrammed to use it.
The data structure Stack.
The reverse-polish calculator example.
Class 4  Thur 25‑1‑2018 Methods and constructors: A self-reporting counter object,
Public and protected: A fool-proof version of the above,
Static variables and destructors: A trick for tracing complicated functions,
The beginning of a complete vector_of_strings class implementation.
Class 5  Tue 30‑1‑2018 A hopeless program, it needs the debugger (and a better design).
A complete vector of strings, reference results.
templates: a vector of anything.
Class 6  Thur 1‑2‑2018 A typical old-fashioned random number generator,
Array parameters are annoying, you have to supply (and remember) the size separately,
ourvec.h: Making our vector implementation into a library,
vec.cpp: and using it in a simple test,
Vector parameters are much more convenient, but watch out for the destructor
Class 7  Tue 6‑2‑2018 Two dimensional arrays:
Multidimensional arrays are hopeless in C++ (this doesn't work).
Improved method 1: a pointer to an array of pointers to arrays of data item (an array of arrays).
Improved method 2: convert 2-d array into 1-d array, so item[r][c] becomes item[r*columns+c].
Class 8  Thur 8‑2‑2018 A badly designed database;
The corrected version making proper use of pointers.
Thinking about implementing giant numbers as vectors of digits.
Class 9  Tue 13‑2‑2018 Implementing big numbers as arrays of digits,
introducing inheritance,
See if you can work out how to make subtraction work "properly".
Class 10  Thur 15‑2‑2018 More about giant integers, signs and multiplication methods.
The big O notation introduced, and discovering that our vector implementation is slow.
Class 11  Tue 20‑2‑2018 Sorting part 1.
Class 12  Thur 22‑2‑2018 Sorting part 2.
code from this week: selsort.cpp, sel2.cpp, ourvec.h.
Class 13  Tue 27‑2‑2018 A bit more sorting,
A skeleton program for timing functions,
At the supermarket: discovering the linked list.
Class 14  Thur 1‑3‑2018 First experiments with a linked list.
Creating, adding an item, printing, finding an item, removing an item.
Class 15  Tue 6‑3‑2018 Proper object orientation: and object for each link and an object for the list itself.
isempty, remove_first, insert_in_place add up to insertion sort for linked lists.
Splitting a linked list in half.
Class 16  Thur 8‑3‑2018 Adding to the end of a list,
Merging two sorted linked lists, and all the pre-requisite methods.
Spring Break
Class 17  Tue 20‑3‑2018 Test preparation.
Class 18  Thur 22‑3‑2018 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, these samples at least show you the style of test to expect.
Prepare for: Pointers, new, delete; vectors; multi-dimensional arrays; sorting; linked lists.
Class 19  Tue 27‑3‑2018 Discovering merge-sort and comparing its speed to other sorting methods we know.
Class 20  Thur 29‑3‑2018 Coding merge-sort recursively.
Doubly-linked lists.
Class 21  Tue 3‑4‑2018 Reminding ourselves about Binary Chop Search.
Introducing Binary Trees: searching.
Class 22  Thur 5‑4‑2018 Constructing a binary tree by hand, and printing it in order
Two methods for inserting data into a tree
Class 23  Tue 10‑4‑2018 More binary tree methods.
Class 24  Thur 12‑4‑2018 Experimentally measuring how good a randomly constructed binary tree is.
Inventing Tree-Sort.
Class 25  Tue 17‑4‑2018 Review.
Class 26  Thur 19‑4‑2018 Second Test.
Another sample, (remember that some of the test 1 samples cover test 2 material).
Prepare for: Merge-sort, binary chop search, doubly linked lists, binary trees.
Class 27  Tue 24‑4‑2018 More tree experiments. Including non-recursive in-order tree printing.
Class 28  Thur 26‑4‑2018 Quick-sort:
A popular partitioning method. The whole algorithm.
The first appearance of Quicksort: paper, algorithm part 1, part 2.
The test system.