CIS-3050 Algorithms and Data Structures

Fall 2010

Vermont Technical College

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


8/25
C++ topics:
templates
abstract data types
Chapter 1

8/30
C++ topics:
inheritance
polymorphism
Chapter 2

9/1
Interesting functions
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
Stacks, Queues, Linked Lists
Chapter 4
Queue Slides.  The slides I showed in class start on page 16

9/13
More Linked Lists
Stacks on Lists
Stacks on Arrays

Assignment 2 out, due 9/20
9/15
Extending List
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
Other Queue types - deque and priority

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
Begin Unordered Data  - Sets, Bags

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
Exam 1


10/11
No Class
Fall break


10/13
No Class
Fall break


10/18
Trees
Chapter 6

10/20
More Trees
Binary Tree Traversal Visualization (click on Start Exercise)

10/25
Exceptions, bit sets
Section 2.4 pg 92 - 96
Also: web resource on exceptions
STL exceptions
Assignment 4 out, due 11/3
10/27
Binary Trees and Arrays
Heaps


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

11/3
Open Addressing hashing
Chaining


11/8
More chaining
Linear hashing
more hash functions


11/10
Bubble, Selection and Insertion sorts
Pseudocode for the quadratic sorts
Sort visualization applet
Assignment 5 out, due 11/15
11/15
Heap and Merge sorts
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
Exam 2


11/22
No Class
Thanksgiving break


11/24
No Class
Thanksgiving break


11/29
Quick and Bucket Sort
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
Finish sorts
Photocopy of Radix sort information
Info about counting sort
Assignment 6 out, due in class Dec 13
12/6
Graphs
Slides with basic graph terminology (we didn't go through all of these -- you should recognize the ones we did)

12/8
More Graphs
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)