15-211: Fundamental Data Structures and Algorithms

COURSE CALENDAR

wk	Date	Topics	Text	HW/Quizzes
M	May 22	Course Overview		Submission Setup
		Hashing
Tu	May 23	Separate Chaining	ch. 5	HW1: Caterpillar Due: May 30
W	May 24	Open Addressing	ch. 5
Th	May 25	Complexity of Algorithms	ch. 2
		Dynamic Programming
F	May 26	Making Change, 0-1 Knapsack	ch. 10.3	HW2: Edit Distance Due: June 06 Quiz 1 [solutions]
M	May 29	Memorial Day
Tu	May 30	Matrix Chain Multiplication String Reconstruction	ch. 10.3
W	May 31	Longest Common Subsequence
		Search Trees and Heaps
Th	June 01	Search Trees	ch. 4
F	June 02	AVL and Splay Trees	ch. 4	Quiz 2 [solutions]
M	June 05	Binary and Binomial Heaps	ch. 6.1
Tu	June 06	Treepourri: B-trees, Tries, ...		HW3: Cell Phone Due: June 13
		Sorting
W	June 07	RadixSort and HeapSort
Th	June 08	Mergesort	ch. 7
F	June 09	Quicksort	ch. 7	Quiz 3
M	June 12	Midterm Exam
		Text Processing
Tu	June 13	Huffman coding	ch. 10.1.2	HW4: Compression Due: June 20
W	June 14	String compression: LZW compression
Th	June 15	Finite Automaton
F	June 16	String matching: The Knuth-Morris-Prat algorithm		Quiz 4 [solutions]
M	June 19	String matching: The Aho-Corasick algorithm The Rabin-Karp algorithm
		Graph Algorithms
Tu	June 20	Representations Traversals	ch. 9.1
W	June 21	Minimum Spanning Trees Prim's algorithm Kruskal's algorithm	ch. 9.5
Th	June 22	Minimum Spanning Trees Disjoint Sets	ch. 8	HW5: Maze Due: June 28
F	June 23	Disjoint Sets Union-Find	ch. 9.3	Quiz 5
M	June 26	Dijsktra's algorithm	ch. 9.3
Tu	June 27	The Bellman-Ford algorithm The Floyd-Warshall algorithm
W	June 28	Computability
Th	June 29	Final Exam

Last updated Sunday, Apr 12, 2006

Victor S. Adamchik,  Computer Science Department,  Carnegie Mellon University, Pittsburgh, PA.