## Data Structures - Fall 1997 Lectures and Reading

 Date Planned Lecture Topic Read Before Lecture Aug 26 Aug 28 Preconditions/Postconditions & Classes More Classes & Operator Overloading Through Section 2.5 Sep 2 Sep 4 Container Classes Introduction to Pointers Chapter 3 Section 4.1 Sep 9 Sep 11 Dynamic Arrays Introduction to Linked Lists Section 4.2 - 4.5 Section 5.1 Sep 16 Sep 18 . Building a Linked List Toolkit Using the Linked List Toolkit plus exam review Section 5.2 Section 5.3 - 5.5 Sample exam Sep 23 Sep 25 First Exam (Chapters 1-5) Template Functions . Section 6.1 - 6.2 Sep 30 Oct 2 Template Classes The Stack Template Class Sections 6.3 - 6.4 Section 7.1 - 7.3 Oct 7 Oct 9 . Applications that use Stacks Queues and Priority Queues plus exam review Sections 7.4 Chapter 8 Sample exam Oct 14 Oct 16 Second Exam (Chapters 6-8) Introduction to Recursion . Section 9.1 Oct 21 Oct 23 Fractals and their Friends Third Exam (Recursion) Section 9.2 Sample exam Oct 28 Oct 30 Trees and Traversals Binary Search Trees Section 10.1-10.4 Section 10.5 Nov 4 Nov 6 . Heaps and B-Trees B-Tree Implementation Details plus exam review Pages 492 - 501 Rest of Section 11.2 Sample exam Nov 11 Nov 13 Fourth Exam (Chapters 10-11) Binary Search and Hashing . Chapter 12 Nov 18 Nov 20 Quadradic Sorting Mergesort Section 13.1 Pages 583 - 595 Nov 25 . Quicksort . Pages 595 - 603 Project 4 (p 617) Dec 2 Dec 4 The Standard Library Quicksort Derived Classes and an Ecosystem Quicksort Web Page Sections 14.1 - 14.2 Dec 9 . Demos, Stump the Prof, Videos plus exam review Project 3 (p 661) Sample exam Dec 16 . Dec 17 . Fifth exam (Chap 12-13) for 12:30 lecture is at 3:30-6:30 on Tuesday, Dec 16. Fifth exam (Chap 12-13) for 2:00 lecture is at 3:30-6:30 on Wednesday, Dec 17. .

The textbook is Data Structures and Other Objects Using C++ by Michael Main and Walter Savitch .

The five exams are listed in the table of lectures. A collection of sample exam questions is available through our class web pages.