ECE218 T Data Structures Autumn 2019
Tue, Thur, 5:05-6:20 in MM 312

Examinations:

Assignments:

All to be emailed to ecegrader at gmail.com, Subject: 218 Assignment N Your Name
Always include transcript/screenshot of a successful run.
    1   Due: Sun 1st September
       Make the RPN calculator work.
2Due: Tue 17th September
Make your own vector class.
3Due: Tue 5th November
Race two sorting algorithms against each other.
4Due: Sat 16th November
Super-calculator.
5Due: Sat 23rd November
Linked list database.
Here is the database in downloadable form.
6Due: Sun 8th December
Tree based database.

Class History

Class 1  ‑ Tue 20‑8‑2019   Quick introductions.
Storing all the words from a file into an array.
Introducing vectors, and using one for the same purpose.
Class 2  ‑ Thur 22‑8‑2019 Operations that can be performed on a vector.
Reverse Polish notation for expressions.
Class 3  ‑ Tue 27‑8‑2019 A struct/object that implements a two dimensional array sensibly.
Class 4  ‑ Thur 29‑8‑2019 Public and protected, inheritance, destructors, type-casts,
passing objects by reference to avoid destruction, reference results.
Class 5  ‑ Tue 3‑9‑2019 (Closed)
Class 6  ‑ Thur 5‑9‑2019 The strange implementation of an array: operator definitions and templates.
Class 7  ‑ Tue 10‑9‑2019 Selection sort, Insertion sort, Bubble sort.
Class 8  ‑ Thur 12‑9‑2019 Shaker sort,
Some empirical evidence.
Introducing Quicksort.
Class 9  ‑ Tue 17‑9‑2019
Class 10  ‑ Thur 19‑9‑2019
Class 11  ‑ Tue 24‑9‑2019
Class 12  ‑ Thur 26‑9‑2019
Class 13  ‑ Tue 1‑10‑2019 Review day.
Class 14  ‑ Thur 3‑10‑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 15  ‑ Tue 8‑10‑2019 At the supermarket: discovering the linked list.
Class 16  ‑ Thur 10‑10‑2019 Basic linked list operations
Class 17  ‑ Tue 15‑10‑2019 Linked lists that remember where their own last link is.
Class 18  ‑ Tue 22‑10‑2019 What we learned from the test.
Class 19  ‑ Thur 24‑10‑2019 Doubly-linked lists,
Sparse arrays.
Class 20  ‑ Tue 29‑10‑2019 Reminding ourselves of binary chop search.
Trying to apply it to linked lists, and discovering binary trees.
Class 21  ‑ Thur 31‑10‑2019 Binary trees: search, insert, print-all,
The sample code.
Class 22  ‑ Tue 5‑11‑2019 A tree with objects in it, using a dummy object as a pattern.
Can we compare two trees to see if they contain the same data?
Class 23  ‑ Thur 7‑11‑2019 Linearising a tree, finding and following paths in trees.
Class 24  ‑ Tue 12‑11‑2019 Review day
Class 25  ‑ Thur 14‑11‑2019 Second test, Another sample, (remember that some of the test 1 samples cover test 2 material).
Class 26  ‑ Tue 19‑11‑2019 Examining the natural balance of random trees.
Inefficiently rebalancing an unbalanced tree.
Here is today's code from class.
Class 27  ‑ Thur 21‑11‑2019 Using stacks to evaluate normal expressions, and
to run through a tree without using recursion.
Break
Class 28  ‑ Tue 3‑12‑2019 The test will have six questions on it.