Week 1:

Week 1 Lectures
 Introduction to Data Structures
 Topic:  Course Introduction
  Topic:  What Is a Data Structure?
  Topic:  Precondition/Postcondition Contracts
  Topic:  Include Directives
  Topic:  Using Directives
  Topic:  Time Analysis

Introduction to Classes
 Topic:  What is a Class?
  Example:  Throttle Class
  Topic:  Parts of a Class
  Topic:  Using a Class in a Program
  Topic:  Constructors
  Topic:  Using a Namespace, Header File, and Separate Implementation File
  Discuss:  The Statistician
Class (HW 1)
  Example:  Lock Class



Week 1 Lab
 In the Lab

Week 2:

Week 2 Lectures
 More about Member Functions and Parameters
 Discuss:  Classes and Parameters
  Topic:  Operator Overloading
  Exercise:  Fraction Class

Container Classes
 Topic:  Introduction to Container Classes
  Sec 3.1:  The Bag Class
  Exercise:  Big Integer Class


 Read
Sections 3.1, 3.3, 4.1 and 4.2
by next Monday.
The Statistician Class
(HW 1) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 2 Lab
 In the Lab

Week 3:

Week 3 Lectures
 Introduction to Pointers and Dynamic Arrays
 Sec 4.1:  Pointers and Dynamic Memory
  Sec 4.2:  Pointers and Arrays as Parameters

Using Dynamic Arrays


Week 3 Lab
 In the Lab

Week 4:

Week 4 Exam

First InClass Exam during this week's first lecture
period: Introductory Material from Chapters 14

 Read
Sections 5.1 and 5.2
by Monday, Sep 20.
Your String Class
(HW 2) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 4 Lectures
 Introduction to Linked Lists
 Sec 5.1:  A
Fundamental Node Class for Linked Lists
  Sec 5.2:  A Linked List Toolkit


Week 4 Lab
 In the Lab
 Lab 3:  Skill with the Debugger
  Also:  The TA will
offer lastminute feedback on your nearly completed string class (including your makefile).


Week 5:

Week 5 Lectures
 More Linked Lists
Using Linked Lists in a Container Class
 Sec
5.3: 
The Bag Class with a Linked List
  Topic:  Mutable Members
  Example:  Modifying Your String Class to Use a Linked List
  Sec 5.5:  Dynamic Arrays vs Linked Lists vs Doubly Linked Lists



Week 5 Lab
 In the Lab

Week 6:

Week 6 Exam

Second InClass Exam during the first lecture period of this week: Linked Lists from Chapter 5

 Read
Sections 6.1, 6.2 and 6.3
by next Monday.
Expanded Linked List Toolkit
(HW 3) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 6 Lectures
 Introduction to Templates
 Sec 6.1:  Template Functions
  Sec 6.2:  Template Classes


Week 6 Lab
 In the Lab
 Exercise: 
Building Templates
  Also:  The TA will
offer lastminute feedback on your nearly completed linked
list toolkit.


Week 7:

Week 7 Lectures
 The STL and Iterators
Iterators
Generic Algorithms


Week 7 Lab
 In the Lab

Week 8:

Week 8 Lectures
 Stacks
Queues
Priority Queues
Evaluating Arithmetic Expressions

 Read
Sections 8.1, 8.3 and 8.5
by next Monday.
A Program Using the STL
(HW 4) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 8 Lab
 In the Lab
 Exercise:  Using Vectors
  Also:  The TA will
offer lastminute feedback on your nearly completed STL program.


Week 9:

Week 9 Lectures
 Recursion
Introduction to Trees

 Read
Sections 9.1, 9.2 and 9.3
by next Monday.
 Start work on HW 5:
The Priority Queue Class due at 11:55pm on Friday of next week.

Week 9 Lab
 In the Lab

Week 10:

Week 10 Lectures
 A Class for Binary Tree Nodes
Complete Binary Trees
Tree Traversals
Printing Trees
Binary Search Trees

 Read
Sections 10.1, 10.2, 10.3, 10.4 and 10.5
by next Monday.
The Priority Queue Class
(HW 5) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 10 Lab
 In the Lab
 Exercise:  Tree Traversals
  Also:  The TA will
offer lastminute feedback on your nearly completed Priority Queue program.


Week 11:

Week 11 Exam

Third InClass Exam during the first lecture period of this
week: Mostly Recursion and Trees

The first small part of the BTree
(HW 6A) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 11 Lectures
 Introduction to BTrees
The Default Constructor
A Second Constructor to Build a Small Test Tree
Printing a BTree
Searching a BTree

Week 11 Lab
 In the Lab

Week 12:

Week 12 Lectures
 The Copy Constructor and Assignment Operator
The Clear Member Function and Destructor
BTree Insertion

Part B of the BTree
(HW 6B) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 11 Lab
 In the Lab

Week 13:

Week 13 Lectures
 BTree Removal
Heaps
Time Analysis

Part C of the BTree
(HW 6C) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 14 Lab
 In the Lab

Week 14:

Week 14 Exam

Fourth InClass Exam during the first lecture period of this
week: Mostly Chapter 11

Part D of the BTree
(HW 6D) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 14 Lectures
 Quadratic Sorting
Quicksort

Week 14 Lab
 In the Lab

Week 15:

Week 15 Lectures
 Removing Recursion from Quicksort
Mergesort
Hash Tables


Read Chapter 12 before the final exam.
 Work on the
Sorting Program, which is due this week.
The Sorting Program
(HW 7) must be submitted to webct by 11:55pm on Friday of this
week. If you did
not complete the work, then submit the things you did complete
for partial credit. No late work is accepted.



Week 15 Lab
 In the Lab
 Work On : 
Sorting Program


Finals Week

Final

Final Exam: Cumulative over the whole semester

 Get plenty of sleep for the final exam
