CS352: Data Structures and Algorithms

Proposed ScheduleFall 2009****Dates Are Subject to Change****

ApproxDates / Topics / Readings / In-class Work / Comments
Aug 25 / Course Information, Introduction
Aug 27 / Writing/Reading Algorithms / Ch. 1 / Exercise 1
Sept 1 / Algorithm analysis / Ch. 2 / Exercise 2
Sept 3 / Asymptotics(Big-O, Theta & Omega) / Ch. 2 / Quiz 1 / Assign Project 1
Sept 7 / Labor Day holiday / Holiday / Holiday / Holiday
Sept 8 / More asymptotics / Ch. 2 / Exercise 3
Sept 10 / Abstract Data Types (ADT) List,implementation and complexities
Skip Lists / Ch. 3.1-3.5, 10.4.2 / Quiz 2 / Exercise
Sept 15 / ADT Stack,ADT Queue and their implementation complexities
Applications for StacksQueues / Ch.3.6-3.7 / Exercise 4
Sept 17 / General tree structures, binary trees, traversals / Ch. 4.1-4.2, 12.2 / Quiz 3 / Exercise
Sept 22 / Expression trees, binary search trees / Ch. 4.3 / Exercise 5
Sept 24 / Self-adjusting search trees -- AVL / Ch. 4.4 / Quiz 4
Sept 29 / Self-adjusting search trees -- finish AVL,Splay / Ch. 4.5 / Exercise 6 / Proj 1 due
Oct 1 / External tree structures: 2-3trees,2-3-4 trees, B+-trees, red-black trees / Ch. 4.7 / Quiz 5 / Proj 1 Report due
Assign project 2
Oct 6 / Hashing as search technique, Hash functions
Open hashing, Collision resolution with chaining / Ch. 5.1-5.3 / Exercise 7
Oct 8 / Closed hashing,Collision resolution methods, Double Hashing, Rehashing, Extendible hashing / Ch. 5.4-5.7 / Quiz 6
Oct 13 / Sets and Maps / Ch. 4.8 / Exercise 8
Oct 15 / Binary tree applications : Priority Queues, Heaps / Ch. 6.1-6.3 / Quiz 7
Oct 20 / Binomial Queues / Ch. 6.8 / Exercise 9
Oct 22 / Insertion sort algorithms and their performance : Insertion Sort,Shellsort / Ch. 7.1-7.2,7.4 / Quiz 8
Oct 27 / Lower bound for sorting,
Priority Queue sorts and their performance : Heapsort and Selection / Ch. 7.3,7.5, 7.9 / Exercise 10 / Project 2 due
Judy at OOPSLA
Oct 29 / Divide&Conquer sorting algorithms and their performance : Mergesort / Ch. 7.6 / Quiz 9 / Judy at OOPSLA
Project 2 Report due
Assign Project 3
Nov 3 / Divide&Conquer sorting algorithms and their performance : Quicksort / Ch. 7.7 / Exercise 11
Nov 5 / Disjoint sets-Union/Find algorithm / Ch. 8 / Quiz 10
Nov 10 / Graphs(basic facts, representations), Graph ADT, topological sort / Ch. 9.1-9.2 / Exercise 12
Nov 12 / Shortest path algorithms / Ch.9.3 / Quiz 11
Nov 17 / Graph Traversals : BFS,DFS / Ch.9.3 / Exercise 13
Nov 19 / Minimum Spanning Trees / Ch. 9.5 / .Quiz 12
Nov 23-
27 / Thanksgiving Break / Break / Break / Break
Dec 1 / Applications for DFS:Biconnectivity and Articulation Points / Ch.9.6.1-9.6.2 / Exercise 14 / Project 3 due
Dec. 3 / Critical path analysis, Network flow problems / Ch. 9.3.4,9.4 / Quiz 13 / Project 3 Report due
Dec. 8 / Introduction to NP and NP-Complete Problems / Ch. 9.7 / Exercise 15
Dec. 10 / Catch-up and Review / Quiz 14
Dec. 15 / Final Exam - comprehensive
VOC 5:45pm-7:45pm
Dec.16 / Final Exam - comprehensive
VOA 10:30am-12:30pm