EEN218 J (Programming 2: Data Structures) Spring 2017
Mon, Wed, 5:00-6:15 in MM 312

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: Sat. 4th Feb.
       Very basic linked list constructuion.
2Due: Thur. 23rd Feb.
Cat club - a linked list of linked lists.
3Due: Sat 1st April.
Special vector.
4Due: Sat 22nd April.
Basic supercalculator.
5Due: Sat 29th April.
Quicksort.
6Due: Mon 8th May
Binary Trees.

Some older notes on relevant topics:

Class History

Class 1  Wed 18‑1‑2017    Introductions. Data Structures = what to do when you've got complicated data and/or a lot of data - keep it nicely organised.
Reminders about structs: Alone, and in Arrays; use reference parameters.
PC log in - use Putty or your own preferred SSH app.
Macintosh log in - use terminal and type ssh -oHostKeyAlgorithms=+ssh-dss username@rabbit.eng.miami.edu.
Class 2  Mon 23‑1‑2017 What do we do if we don't know how big to make the array?
We'll discover something more flexible. Here's a start.
Pointers, methods, and constructors are introduced all at once.
Class 3  Wed 25‑1‑2017 More linked lists. There should be a difference between a person and an address book, but for now ...
A linked list of people, using NULL for a proper sentinel value.
Notified of first assignment.
Class 4  Mon 30‑1‑2017 Searching a linked list.
Building a linked list "the right way round" - adding new items to the end.
Class 5  Wed 1‑2‑2017 Three separate objects is the way to go: 1 for the list, 1 for the links, and 1 for the people.
Class 6  Mon 6‑2‑2017 Adding in the right place in an ordered list. Before following any pointer make sure you know it can't be NULL.
A simple algorithm for sorting a linked list. The time it takes depends on the square of the size of the list.
Class 7  Wed 8‑2‑2017 More linked list sorting algorithms: insertion sort, selection sort, bubble sort. All of them require time that depaends on the square of the length of the list.
Class 8  Mon 13‑2‑2017 Back to arrays: heap allocation (int * A = new int[10]) compared to stack allocation (int A[10]). Bubble sort on an array: really calculating the time, big O notation for computation time compared to data size.
Class 9  Wed 15‑2‑2017 Insertion sort and selection sort on arrays; gradually transforming a simplistic selection sort into an "in-place" version. Considering the times again, still quadratic.
Class 10  Mon 20‑2‑2017 C++ doesn't give us a very useful version of two dimensional arrays:
it doesn't check indexes against sizes, but needs to be told sizes.
So we implement our own as a class. Public, protected, and assert are introduced too.
Class 11  Wed 22‑2‑2017 We are introduced to printf,
and look at addresses used by heap and stack allocation, noticing that stack memory gets reused frequently.
A badly designed database.
Class 12  Mon 27‑2‑2017 The problem of accidentally copied objects (not getting a raise). Pointers save the day and our database program.
Looking at an old test, and being introduced to delete.
Class 13  Wed 1‑3‑2017 First Test
Class 14  Mon 6‑3‑2017 Introducing vectors - objects with the functionality of arrays, but you can change their sizes.
Class 15  Wed 8‑3‑2017 Efficiency of resizing a vector. Add an increment to capacity each time and the overall behaviour is quadratic. Double the capacity each time and it's linear.
Introduced Reverse Polish Notation.
Class 16  Mon 20‑3‑2017 Making a reverse polish calculator that also translates to normal notation.
First thoughts on an unlimited-precision calculator.
Class 17  Wed 22‑3‑2017 Separate compilation example with our 2d array code: 2da.h, 2da.cpp, test.cpp.
Compile with CC -c 2da.cpp followed by CC test.cpp t2d.o
The partitioning method that lets us split an array into two independently sortable portions: the animated demo. Introducing Quick-Sort.
Class 18  Mon 27‑3‑2017 Further study of quicksort, and mergesort for linked lists.
Class 19  Wed 29‑3‑2017 Where does all the sorting happen?
More about loop variants and invariants; A different partitioning algorithm.
The first appearance of Quicksort: paper, algorithm part 1, part 2, the test system.
Class 20  Mon 3‑4‑2017 Belatedly going over the test.
Special Tue 4‑4‑2017 Lab guys' help session, at 7 p.m.
Class 21  Wed 5‑4‑2017 Remembering Binary Chop Search.
New Things!
Special Fri 7‑4‑2017 Lab guys' help session, at 11 a.m.
Class 22  Mon 10‑4‑2017 More tree operations: Inserting and searching the linked-listy way, printing in order.
Special Tue 11‑4‑2017 Pre-test review session at 7 p.m.
Class 23  Wed 12‑4‑2017
Special Fri 14‑4‑2017 Pre-test review session at 9.30 a.m.
Class 24  Mon 17‑4‑2017 Second test. A sample. Another sample.
Class 25  Wed 19‑4‑2017 More tree operations - rotations can be useful.
A quick look at Lisp.
Class 26  Mon 24‑4‑2017 Impelementing Lisp - the basics.
Class 27  Wed 26‑4‑2017