ECE218 R Data Structures Spring 2019
Tue, Thur, 2:00-3:15 in MM 313

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: 27th January
       Make the RPN calculator work.
2Due: 17th February
See which sorting method is the fastest.
3Due: 3rd March
Make your own vector.
4Due: 26th April
Calculator for giant integers.
5Due: 6th April
Linked List database.
6Due: 2nd May
Binary Tree database.

Class History

Class 1  Tue 15‑1‑2019    General introductions, what the class is about, policies, etc.
Introducing C++'s vector:
        counting the words in a file using an array,
        and using a vector.
Class 2  Thur 17‑1‑2019 Operations of vectors.
Reverse Polish notation.
Class 3  Tue 22‑1‑2019 Some reminders and some new things about structs.
A very primitive implementation of a 2-D array.
Class 4  Thur 24‑1‑2019 Pointers and new and delete.
An improved implementation of the 2-D array object.
Class 5  Tue 29‑1‑2019 Creating our own vector of ints.
Class 6  Thur 31‑1‑2019 More depth about the vector implementation
Reference results
Making the vector able to sort itself.
Class 7  Tue 5‑2‑2019 Sorting: selection sort and insertion sort.
Class 8  Thur 7‑2‑2019 Sorting: bubble sort and shaker sort,
and some experimental timing.
Class 9  Tue 12‑2‑2019 Analysing the speed of selection sort,
The "Big O" notation,
Binary chop search analysed too.
Class 10  Thur 14‑2‑2019 More about big-O.
Partitioning: getting all the small elements of an array to the left and all the larger ones to the right.
Class 11  Tue 19‑2‑2019 Quicksort all the way through with recursion.
Seeing that the expected time is O(N×log2N),
but with consistently bad pivot choices it is O(N2), the same as selection sort.
Class 12  Thur 21‑2‑2019 A badly designed database.
Slightly improved using a reference,
All better using pointers.
Class 13  Tue 26‑2‑2019 Some time calculations based on big-Os.
The time chart.
Class 14  Thur 28‑2‑2019 Review day.
Class 15  Tue 5‑3‑2019 Test Day.
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  Thur 7‑3‑2019 At the supermarket: discovering the linked list.
Class 17  Tue 19‑3‑2019 Three spearate objects: the list itself, the links, and the data (grocery items).
If adding to the end of the list is important, make the list remember where the end is.
Multiple matches to a search? The linked list search method can return a linked list.
Class 18  Thur 21‑3‑2019 What we learned from the test.
Class 19  Tue 26‑3‑2019 Some thoughts about your supercalculator assignment.
Insertion sort on a linked list.
Class 20  Thur 28‑3‑2019 Splitting a linked list in two.
Combining two already-sorted linked lists.
Class 21  Tue 2‑4‑2019 Merge-sort on linked lists.
Class 22  Thur 4‑4‑2019
Class 23  Tue 9‑4‑2019 First experiments with binary trees.
Class 24  Thur 11‑4‑2019
Class 25  Tue 16‑4‑2019 Second Test.
Class 26  Thur 18‑4‑2019 Experimentally examining the structure of randomly built binary trees.
Class 27  Tue 23‑4‑2019 What we learned from the second test.
Class 28  Thur 25‑4‑2019