Vermont Technical College
Date  Topic  Reading  Assignments 
8/23 
Course Mechanics
What is Algorithm Analysis? 

8/25 
templates abstract data types 
Chapter 1 

8/30 
inheritance polymorphism 
Chapter 2 

9/1 
Big O  what is it? 
Additional
info
on
Running
Time Chapter 3, skipping 3.3 
Assignment 1 out, due 9/8 
9/6 
No Class
Labor Day 

9/8 

Chapter 4 Queue Slides. The slides I showed in class start on page 16 

9/13 
Stacks on Lists Stacks on Arrays 
Assignment 2 out, due 9/20 

9/15 
Queues on Lists Queues on Arrays Doubly Linked Lists 
Web
page all about STL vector class Comparison of STL deque and vector classes. Good look at vector performance. You might want to wait until we've talked about double ended queues, however. 

9/20 

What
is
an
Iterator
in
C++,
part
I  all What is an Iterator in C++, part II  Read the part about Homemade Iterators 

9/22  More on Iteration Writing Iterators 
More on
STL iteration  a bit easier to read then the material above. STL Reference Material  nicely formatted 

9/27  Finish Writing Iterators Searching ordered data 
AList.h with minimal forward iterator AList.cpp to match Simple test of AList: ArrayIterator.cpp Binary search sample file 
Assignment 3 out, due 10/6 
9/29 

Basic
info
on
Trees (more later when we fully consider trees) 

10/4 
Recursion  Section 2.5, pages 97  102 and Section 4.1, pages 145  155 

10/6 


10/11 
No Class
Fall break 

10/13 
No Class
Fall break 

10/18 

Chapter 6 

10/20 

Binary
Tree
Traversal
Visualization (click on Start Exercise) 

10/25 

Section 2.4 pg 92  96 Also: web resource on exceptions STL exceptions 
Assignment 4 out, due 11/3 
10/27 
Heaps 

11/1 
Simple hash functions 
Hashing handout (hardcopy given out in class) 

11/3 
Chaining 

11/8 
Linear hashing more hash functions 

11/10 

Pseudocode for the quadratic
sorts Sort visualization applet 
Assignment 5 out, due 11/15 
11/15 

Section 7.1.2 Heap sort, pg 315 Slides
(basic
review of heaps, plus one slide on heap sort) Section 10.1 Merge sort, pg 485  497 Slides Presentation PDFs from the text 

11/17 


11/22 
No Class
Thanksgiving break 

11/24 
No Class
Thanksgiving break 

11/29 

Section 10.3 Quick sort, pg 504  516. Slides Section 10.5 Bucket sort, pg 517  518 Section 10.6 Sort Comparison pg 520  521 

12/1 

Photocopy of Radix sort information Info about counting sort 
Assignment 6 out, due in class Dec 13 
12/6 

Slides
with basic graph terminology (we didn't go through all of these 
you should recognize the ones we did) 

12/8 

Depth
first
traversal algorithm and example Breadth first traversal algorithm and example Djikstra's shortest path video 

12/13 
Review for Final

Another
explanation of quicksort Sort visualization 

12/15 
Final
Exam
10:30, Room 213 (normal room) 