ECE218 R Data Structures Fall 2021
Mon, Wed 6:00 - 7:15 in MM 115

Examinations:

Assignments:

All to be emailed to ecegrader @ gmail.com
Always include transcript/screenshot of a successful run.
    1   Due: Thursday 9th September.
       The RPN calculator.
2Due: Saturday 25th September, extended to Tues 28th.
Add variables to your RPN calculator.
3Due: Monday 11th October.
Implement shaker sort.
4Due: Saturday 23rd October.
Implement quick-sort.
5Due: Sunday 7th November.
Linked list database,
Here is the database in downloadable form.
6Due: Tuesday 30th November.
Binary tree database.
7Due: Saturday 11th December absolute latest.
CANCELLED: You don't have to do it.
Conway's game of Life.

Class History

Class 1  ‑ Mon 23‑8‑2021   Quick introductions.
What's unsafe about arrays, and how vectors fix that: one, two, three.
Making our own vector definition, part 1.
Reference results as well as reference parameters.
Class 2  ‑ Wed 25‑8‑2021 Pointers, the use of * and &, pointers to arrays.
Using pointers to see where things are in memory.
Constructors and destructors, new and delete.
Our own vec_of_str struct.
Reverse Polish Notation.
Class 3  ‑ Mon 30‑8‑2021 Review of vector enlargement.
Public and protected: The tomorrow calculator.
Defining your own operators.
Class 4  ‑ Wed 1‑9‑2021 Templates: Swap function, SafeArray object.
Dealing with two-dimensional arrays: the Matrix object.
Class 5  ‑ Wed 8‑9‑2021 Why objects are usually passed to functions as reference parameters.
The special timing function for unix.
Selection Sort on random strings.
Class 6  ‑ Mon 13‑9‑2021 Selection sort testing itself,
Experimentally deriving the time formula,
Determining the time by examining the code, O(N2).
Insertion sort, version 1, not in-place.
Class 7  ‑ Wed 15‑9‑2021 An in-place version of insertion sort.
Bubble sort.
Shaker sort.
What happens if I split the array in two and sort the two halves individually?
Class 8  ‑ Mon 20‑9‑2021 Mergesort completed, a basic implementation.
The time for mergesort is O(NlogN).
It could have been done with just two arrays and some carefully constructed loops.
Class 9  ‑ Wed 22‑9‑2021 An attempt at a small database.
Pointers make it work properly. Pointers are our friends.
Another kind of database,
Introducing inheritance and polymorphism,
Where we finished today.
Class 10  ‑ Mon 27‑9‑2021 Adding bankers to the database,
Adding dependents, and the dynamic_cast,
Processing normal arithmetic expressions.
Class 11  ‑ Wed 29‑9‑2021 External help for those troubled by pointers.
Quicksort:
Our first partitioning algorithm.
Our first partition method animated,
The entire quicksort algorithm animated.
Class 12  ‑ Mon 4‑10‑2021 Review day.
Class 13  ‑ Wed 6‑10‑2021 First Mid-term. Topics:
  • pointers, new, delete, constructors, destructors,
  • vectors, 2-D arrays,
  • sorting: selection, insertion, bubble, shaker, merge,
  • 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 14  ‑ Mon 11‑10‑2021 At the supermarket: discovering the linked list.
Building a linked list, printing a linked list, searching a linked list.
The shopping example, and it improved.
Class 15  ‑ Wed 13‑10‑2021 Properly object-oriented linked list implementation.
add, add_to_end, print, find, length, reverse, remove, remove_smallest.
Class 16  ‑ Mon 18‑10‑2021 Insertion sort, selection sort, and bubble sort on linked lists.
Class 17  ‑ Wed 20‑10‑2021 Splitting a list in two, merging two lists,
Mergesort on a linked list (how far did we get?)
Class 18  ‑ Mon 25‑10‑2021 What we learned from the test.
Class 19  ‑ Wed 27‑10‑2021 Merging two sorted lists, re-using the old links.
Linked lists that remember where their ends are.
Introducing doubly-linked lists.
Class 20  ‑ Mon 1‑11‑2021 Remove and insert operations on doubly linked lists.
Stacks, Queues (the maze), and Deques.
Class 21  ‑ Wed 3‑11‑2021 Queues and Stacks continued:
Searching a maze with a queue = breadth-first search,
Searching a maze with a stack = depth-first search.
Introducing the binary tree.
Class 22  ‑ Mon 8‑11‑2021 Test preparation.
Class 23  ‑ Wed 10‑11‑2021 Second mid-term. Possible topics:
  • Vectors
  • Quicksort, Mergesort
  • Timing, Big Os
  • Anything about linked lists.
Class 24  ‑ Mon 15‑11‑2021 Binary trees: searching, find-longest-string, find-shortest-string, print-all-in-order, add, linearise.
Class 25  ‑ Wed 17‑11‑2021 Sorting via a tree, saving and restoring the tree's structure, print nicely showing the structure,
breadth-first printing, average value with returns.
Break
Class 26  ‑ Mon 29‑11‑2021 Moving the cursor about the screen.
Conway's game of Life.
More on trees: the Visitor pattern, reduce, find path, follow path,
a non-destructive destructor.
Class 27  ‑ Wed 1‑12‑2021 For help with interviews, a brief introduction to dynamic programming:
The best way to give change for a particular amount,
Finding a 'subset' with a particular sum.
Finding the subsequence with the greatest sum.
Class 28  ‑ Mon 6‑12‑2021 What we learned from test two.
Class 29  ‑ Wed 8‑12‑2021 Final exam preparation.
The new topic (question 9) is Binary Trees.