ECE218 R Data Structures Spring 2021
Mon, Wed 6:00 - 7:15 in LC 140

Examinations:

Assignments:

All to be emailed to grader218 @ rabbit.eng.miami.edu
Always include transcript/screenshot of a successful run.
    1   Due: Sun. 7th Feb.
       The RPN calculator, part one.
    2   Due: Thur. 25th Feb.
       The RPN calculator, part two.
3Due: Thur. 11th March.
Implement Shaker-sort on an array of objects.
4Due: Sun. 4th April.
Linked list database,
Here is the database in downloadable form.
5Due: Sun. 2nd May.
Binary tree database.

Class History

Class 1  ‑ Mon 25‑1‑2021   Quick introductions, the syllabus, policies, etc.
Today's scrappy notes.
Class 2  ‑ Wed 27‑1‑2021 Vector operations,
How dangerous an ordinary array can be (here it is made safe),
Reverse Polish Notation (RPN).
Notes from today: Playing with a vector, converting strings to ints.
Class 3  ‑ Mon 1‑2‑2021 The use of new and delete.
Defining our own version of a vector: ArrayOfStrings.
Class 2's example "playing with a vector" converted to this style.
Class 4  ‑ Wed 3‑2‑2021 The tomorrow calculator: protected and public.
Here it is, made safe.
Two dimensional arrays in C++, making our own matrix object to fix the problems.
Class 5  ‑ Mon 8‑2‑2021 Reference variables and reference results.
A templated version of ArrayOf (equivalent to vector).
Class 6  ‑ Wed 10‑2‑2021 The special timing function for unix.
Timing a sorting operation: Selection Sort.
Class 7  ‑ Mon 15‑2‑2021 Determining that selection sort is O(N2) analytically,
and a graphical technique, using logarithmic graph paper.
Insertion sort, first version.
Class 8  ‑ Wed 17‑2‑2021 Insertion sort can easily be an in-place algorithm.
Bubble sort, slower than the others.
Shaker sort.
Generating random strings, character encodings.
Why sorting strings is slower than soting ints.
Class 9  ‑ Mon 22‑2‑2021 Why we usually pass objects as reference parameters.
Splitting an array, sorting the two halves, and re-merging them makes sorting faster.
Class 10  ‑ Wed 24‑2‑2021 The plan for Merge-Sort's splitting and merging.
Why Mergesort's time is O(NlogN).
The starting point for coding mergesort.
A complete basic mergesort implementation.
An attempt at a small database.
Class 11  ‑ Mon 1‑3‑2021 Back to the attempted database.
Introducing Polymorphism, step 1, 2a, 2b, 3a, 3b, Final version.
Class 12  ‑ Wed 3‑3‑2021 "Wellness Wednesday", we do not meet today.
Your make-up reading assignment:
Read the first one-and-a-half pages and try to work out what the algorithm is.
What is a "nest" in today's terms?
Class 13  ‑ Mon 8‑3‑2021 Back to polymorhpism and inheritance.
The final version of the example.
Class 14  ‑ Wed 10‑3‑2021 Test preparation.
Class 15  ‑ Mon 15‑3‑2021 First mid-term exam. All on-line, using Respondus lock-down browser.
A sample test, and its solution,
and another mini-test, with its solution.
Another sample, and its solution.
Another sample, (remember that some of these samples cover test 2 material).
Class 16  ‑ Wed 17‑3‑2021 Algorithm part 1, part 2. The test system.
Our first partitioning algorithm.
Our first partition method animated,
The entire quicksort algorithm animated.
Our second partitioning algorithm.
Class 17  ‑ Mon 22‑3‑2021 At the supermarket: discovering the linked list.
Building a linked list, printing a linked list, searching a linked list.
Notes from today: version 1, and version 2.
Class 18  ‑ Wed 24‑3‑2021 The linked list as a proper object,
including two methods for removing an object, and a way to reverse a list.
Class 19  ‑ Mon 29‑3‑2021 What we learned from the test.
Class 20  ‑ Wed 31‑3‑2021 Adding to the end of a linked list, two slightly different methods.
Linked lists that remember where their own ends are. adding and removing.
Class 21  ‑ Mon 5‑4‑2021 Doubly-linked lists: Adding and removing in all sorts of ways.
Class 22  ‑ Wed 7‑4‑2021 Inheritance, quicksort, etc: review.
Class 23  ‑ Mon 12‑4‑2021 Second test day. All on-line, using Respondus lock-down browser.
A sample; Binary trees will not appear on this test.
Class 24  ‑ Wed 14‑4‑2021 "Wellness Wednesday", we do not meet today.
Here is your special reading assignment. Try to work out what they are saying a tree is. No need to go too far.
Class 25  ‑ Mon 19‑4‑2021 Introducing Binary Trees.
Building a tree by hand.
Navigating, searching, finding path, printing.
Class 26  ‑ Wed 21‑4‑2021 Binary trees, part two.
Printing the whole tree, printing nicely, inserting (recursion and a loop),
Using a tree to sort a vector.
Class 27  ‑ Mon 26‑4‑2021 Binary trees, part three.
More about printing and flattening. A destructor, finding the average value,
Printing with depth, printing by depth, a breadth-first traversal.
Class 28  ‑ Wed 28‑4‑2021 Preparing for the final.