CSCI 146 Fall 1997: Syllabus

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.

p. 490)
Week BeginsTopicLecture #1Lecture #2LabProgramming Assignment
August 18IntroductionN/A1.2No LabNone; Assign Whole Chapter 1 as Reading
August 25ADTs and C++ Classes2.1 & 2.2 2.3 to 2.5 Visual C++ Intro, Debugging Aids, Documentation Conventions 1. The Statistician Class.
September 1Container Classes3.13.2 & 3.3 A Circle ClassNone
September 8Pointers and Dynamic Arrays4.1 to 4.34.4 & 4.5 The List Class from Section 3.2 (with Fixed Arrays) 2. The List Class with a Dynamic Array
September 15Linked Lists5.1 & 5.25.3 & 5.4 The String ADTNone
September 22More Linked Lists3.5 & 3.6 Exam #1Lab Exam #1 3. Extending the Linked List Toolkit
September 29 Software Reuse with Templates 6.1 & 6.36.2 & 6.5 The List Class from Section 5.4 (with Linked Lists) None
October 6 Stacks 7.1 & 7.27.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.19.2 Word Palindromes None
November 3 More Recursion Exam #29.2 Implementation of the Priority Queue ADT Using an Array of Queues None
November 10 Trees 10.1 & 10.210.3 Three Simple Recursive Algorithms 6. From Binary Search Tree to Linked List (P.P. 8 on p.490)
November 17 More Trees 10.410.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