The textbook is: Main, Michael and Walter Savitch. Data Structures and Other Objects Using C++. Reading, MA: Addison-Wesley, 1997. All references in the outline are to this text. The lab exercises and programming assignments are either taken from the text (as indicated in the outline) or are described in the authors' supplement. Please note that the Lab and Programming Assignments are tentative: entries in italics indicate modifications to the original syllabus.
A course outline follows. The Sections of the text listed under the ``lecture'' headings should be read before the corresponding class.
| Week Begins | Topic | Lecture #1 | Lecture #2 | Lab | Programming Assignment | |
|---|---|---|---|---|---|---|
| August 18 | Introduction | N/A | 1.2 | No Lab | None; Assign Whole Chapter 1 as Reading | |
| August 25 | ADTs and C++ Classes | 2.1 & 2.2 | 2.3 to 2.5 | Visual C++ Intro, Debugging Aids, Documentation Conventions | 1. The Statistician Class. | |
| September 1 | Container Classes | 3.1 | 3.2 & 3.3 | A Circle Class | None | |
| September 8 | Pointers and Dynamic Arrays | 4.1 to 4.3 | 4.4 & 4.5 | The List Class from Section 3.2 (with Fixed Arrays) | 2. The List Class with a Dynamic Array | |
| September 15 | Linked Lists | 5.1 & 5.2 | 5.3 & 5.4 | The String ADT | None | |
| September 22 | More Linked Lists | 3.5 & 3.6 | Exam #1 | Lab Exam #1 | 3. Extending the Linked List Toolkit | |
| September 29 | Software Reuse with Templates | 6.1 & 6.3 | 6.2 & 6.5 | The List Class from Section 5.4 (with Linked Lists) | None | |
| October 6 | Stacks | 7.1 & 7.2 | 7.3 & 7.4 | Implementation of the Set Class with Linked Lists | 4. The n-Queen Problem (Programming Project 9 on p.344) | |
| October 13 | Queues | Fall Break | 8.1 & 8.2 | No Lab: Fall Break | None | |
| October 20 | More Queues and Recursion | 8.3 & 8.4 | 9.1 | Evaluator of Postfix Expressions | 5. Four Small Recursive Functions | |
| October 27 | More Recursion | 9.1 | 9.2 | Word Palindromes | None | |
| November 3 | More Recursion | Exam #2 | 9.2 | Implementation of the Priority Queue ADT Using an Array of Queues | None | |
| November 10 | Trees | 10.1 & 10.2 | 10.3 | Three Simple Recursive Algorithms | 6. From Binary Search Tree to Linked List (P.P. 8 on p.490) | p. 490)|
| November 17 | More Trees | 10.4 | 10.5 | Expression Trees (Programming Project 1 on p.487) | None | |
| November 24 | Thanksgiving Break | 12.1 | Thanksgiving Break | Bag Class Implementation Using Binary Search Trees | None | |
| December 1 | Binary Search | Correction of Second Midterm | 12.1 | Empirical Comparison of the Time Complexity of Serial and Binary Search | None |