ECE218 R Data Structures Spring 2022
Tue, Thur, 2:40 to 3:55, in MEA 202 A

Examinations:

Assignments:

All to be emailed to ecegrader @ gmail.com
Include in the subject: ECE 218, Assignment N, Your name.
Always include transcript/screenshot of a successful run.
Capture your code with "cat", copy, and paste.

    1   Due: Wednesday 9th February.
       The RPN calculator.
2Due: Wednesday 23rd February.
Make your RPN calculator understand variables.
3Due: Friday 11th March.
Implement Shaker sort.
4Due: Saturday 2nd April.
Linked list database.
here is the database.
5Due: Monday 18th April.
Supercalculator.
Extra credit for implementing division of two BigInts correctly.
6Due: Friday 6th May.
Binary tree database.

Class History

Class 1  ‑ Tue 18‑1‑2022   Quick introductions.
The syllabus.
Why arrays in C++ are not safe.
Class 2  ‑ Thur 20‑1‑2022 Introducing pointers:
Step one, two, three, four, five.
Class 3  ‑ Tue 25‑1‑2022 Making our array object oriented, Making a vector, Reverse Polish Notation.
today's notes.
The beginning of a vector.
Investigating the difference between stack and heap addresses.
Making a vector resizable.
The beginning of an RPN calculator.
Class 4  ‑ Thur 27‑1‑2022 Finishing the RPN calculator.
How C++ isn't very good with multi-dimensional arrays,
Creating our own object to represent a two-D array,
Today's partial notes.
Class 5  ‑ Tue 1‑2‑2022 The day the class computer wouldn't work. - No Zoom recording
The use of delete [], defining a destructor.
Why object parameters are usually passed as references.
Templates.
Class 6  ‑ Thur 3‑2‑2022 The date object,
Public and protected.
An attempt at a small database, A problem, Pointers saved the day.
Another database, step 1, step 2.
Class 7  ‑ Tue 8‑2‑2022 Review of public and protected and ::, etc.
Making a library with .h and .o files.
More with our database and Polymorphism,
Our starting position,
Virtual methods,
The dynamic_cast.
Class 8  ‑ Thur 10‑2‑2022 External help for those troubled by pointers.
Another way to store a 2-dimensional array; stars in types.
Ar array of strings that is in alphabetical order,
Remembering the Binary Chop Search, it is a logarithmic algorithm,
Randomising the list of animals,
Selection sort on the randomised list,
Now we need a bigger data set: generating random strings, to be completed.
Class 9  ‑ Tue 15‑2‑2022 Randomly generating strings for selection sort,
Discovering that time is proportional to data size squared,
Insertion sort,
int argc, and char * argv[ ],
an In-place insertion sort.
Class 10  ‑ Thur 17‑2‑2022 The big-O notation, and calculating times based on it.
Bubble sort and Shaker sort.
Cutting an array in half and then recombining those two halves.
Class 11  ‑ Tue 22‑2‑2022 Cutting, sorting, and merging halves the time it takes to sort.
Leading to: Merge-sort.
Merge-sort is O(N×log2N) in time, O(N) in memory.
Class 12  ‑ Thur 24‑2‑2022 (Today's class will be remote only)
Some more polymorphism: Building expressions and evaluating them, and version two.
Designing a partition algorithm, essential for Quicksort.
An animation of partitioning.
Our own partition algorithm,
Quicksort itself.
Quicksort's first appearance, the algorithm part 1, part 2. The test system.
Class 13  ‑ Tue 1‑3‑2022 (Back to in-person again)
An animation of a whole quicksort.
Comparing quicksort to mergesort, timing them.
It's an unfair comparison, mergesort can be made much more efficient.
Two more partitioning methods.
Radix sort.
Class 14  ‑ Thur 3‑3‑2022 Review day
Class 15  ‑ Tue 8‑3‑2022 First Mid-term. Possible topics:
  ⇒ pointers, new, delete, constructors, destructors,
  ⇒ vectors, 2-D arrays,
  ⇒ sorting: selection, insertion, bubble, shaker, merge, quick.
  ⇒ public, protected, inheritance, polymorphism,
  ⇒ timing, big Os.
A sample test, and its solution,
Another sample, and its solution.
Another sample, (remember that some of these samples cover test 2 material).
Class 16  ‑ Thur 10‑3‑2022 At the supermarket: discovering the linked list.
Making a linked list of supermarket items.
Doing it again in a properly object-oriented way.
Break
Class 17  ‑ Tue 22‑3‑2022 A linked list with a remove method.
Reversing a list in two slightly different ways.
Class 18  ‑ Thur 24‑3‑2022 Sorting a linked list: insertion-, selection-, bubble-sort.
Class 19  ‑ Tue 29‑3‑2022 A word about the supercalculator assignment.
Splitting a linked list in two (three different ways), and
Merging two already sorted linked lists.
Class 20  ‑ Thur 31‑3‑2022 What we learned from the test.
Hippopotamusses.
Class 21  ‑ Tue 5‑4‑2022 Linked lists that always remember where their ends are.
Doubly linked lists.
Starting quicksort on linked lists.
Class 22  ‑ Thur 7‑4‑2022 Quicksort on linked lists.
Sparse one-dimensional arrays, sparse two dimensional arrays, version 1, and version 2.
Class 23  ‑ Tue 12‑4‑2022 Review day.
Class 24  ‑ Thur 14‑4‑2022 Second test day, possible topics:
  ⇒ 2-D arrays,
  ⇒ mergesort and quicksort.
  ⇒ public, protected, inheritance, polymorphism,
  ⇒ linked lists.
A sample,
Another sample, and its solution.
Class 25  ‑ Tue 19‑4‑2022 Binary trees: structure, searching, inserting, printing, flattening into a vector.
Class 26  ‑ Thur 21‑4‑2022 Binary trees: traversals - in-order, pre-order, post-order, breadth first by iterative deepening,
Printing to show the tree's structure,
Flattening to a vector, building from a vector, inefficient rebalancing.
Class 27  ‑ Tue 26‑4‑2022 find not based on keys, average, saving and restoring the structure, reverse, find path, follow path.
Class 28  ‑ Thur 28‑4‑2022 What we learned from the test.