Introduction to Algorithms and Data Structures, Course Schedule Spring 2005

This schedule is preliminary, and will be updated during the course period.

Episode	Date	Text	Subject	Teacher	Mandatory exercises due before 13.00 on
0	January 24, 2005 (Monday!)	CLRS Appendix B.1, B.2, B.3, B.4, B.5 and C.1	Discrete math and combinatorics primer	AW
1	February 4, 2005	CLRS Chap. 1, 2.1, 2.2, and 3	Introduction. Computational Problems and Algorithms. Data Structures. Resources. Sorting. Insertion-Sort. Correctness proofs with loop invariants. Running time estimates. Worst- and average-case performance. Growth rates of functions.	AP	February 16, 2005
2	February 11, 2005	CLRS Chap. 10.1, 10.2, 2.3 (skip 2.3.2), 6	Divide & Conquer technique and Merge-Sort; Heaps, Max-Heaps, and Heap-Sort; Priority Queues; Stacks, Queues, and Lists	AP	February 23, 2005
3	February 18, 2005	CLRS chap. 7.1-3; chap. 8.1-3;	Quicksort, sorting by comparisons, lower bound on comparison sorting (with proof), Counting-Sort, stable&unstable sorting	AW	March 2, 2005
4	February 25, 2005	paper (you may skip section 3)	Implementing radix sorting: LSD&MSD Radix-Sort, MSD Radix-Sort with explicit stack, Forward-Radix-Sort Big Assignment 1	AW ERH	March 9, 2005
5	March 4, 2005	Weiss pp.173-189 + CLRS Appendix B.4-B.5 pp. 1080-1090, Chap 4.1-2 pp. 62-72, Chap. 10.4 pp. 214-216, and Chap. 12.1-2. pp. 253-262 + optionally GKP chapter 1.	Simple proofs with mathematical induction, recurrences, substitution method, recurrence tree method, binary search trees, tree traversals, various search operations on trees (most notably Search-Tree and Min-Tree).	AW	March 16, 2005
6	March 11, 2005	CLRS Chap. 12.1–3 supplemented by a handout on AVL trees.	Binary Search Trees: successors, insertion, and deletion. The height of a search tree. Balanced Search Trees. AVL trees. The height of an AVL tree. Insertion, deletion, and rebalancing. Time usage of operations on AVL trees.	AW	March 30, 2005
7	March 18, 2005	CLRS Chap. 15.1-15.3	Computing Fibonacci numbers, Car Assembly Line, Matrix Chain Multiplication (also known as corporate mergers). Each in three versions: simple top-down, top-down with memoization, bottom-up (dynamic programming). Optimized bottom-up of Fibonacci numbers and Car Assembly Line. Optimal substructure.	AW	April 6, 2005
	March 25, 2005		No lecture. Easter.
8	April 1, 2005	CLRS 21.1-3, and 17.1-2	Amortised Analysis: aggregate & accounting methods. Equivalence relations, disjoint sets and Union-Find, connected components, linked-list representation, forest representation.	AP	April 13, 2005
9	April 8, 2005	CLRS chap. 11.1-11.3.1 (omit proofs) and 22.1–22.4.	Guest lecture by Rasmus Pagh on hashing: Dynamic sets, direct access tables, hash tables, chaining, simple uniform hashing, time complexity of Insert & Delete, expected running time of Search (no proofs), rebuilding a hash table (growing), hash functions. Graph representations. Breadth-first search. Depth-first search. Topological sort.	AP	April 20, 2005
10	April 15, 2005	CLRS 23.1–23.2 (Prim's algorithm is optional); CLRS 24.1–2.	Minimum spanning trees. Kruskal's algorithm. Single-source shortest paths in weighted graphs. The Bellman–Ford algorithm. Big assignment 2 (due on April 27).	AP ERH	April 27, 2005
11	April 22, 2005		Work on Big Assignment 2 this week. No lecture.		April 27, 2005
12	April 29, 2005	CLRS 24.2-24.3; optionally 24.5.	Shortest paths in DAGs. Dijkstra's algorithm. Exam preparation (last semesters exam set).	AP AW

CLRS = "Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms, Second Edition"

Weiss= "M. Weiss. Data Structure & Problem Solving Using Java. Addison-Wesley 1998"

GKP= "Graham, Knuth and Patashnik. Concrete Mathematics. A Foundation for Computer Science. 2nd edition. Addison-Wesley 1994."

The weekplans describe the subject, text, and assignments of the week. An assignment can be marked with either an (H), an (M), or an (D) after the assignment which means:

(H): Indicates that the assignment can hopefully be solved by everyone at home, and we will not spend time on these assignments during the course.
(M): Indicates that the assignment is mandatory.
(D): Indicates that the assignment is expected to be more difficult than others.

For instance, 1.2-2 (M), 1.2-3, 10.1-1 (H), 10.1-2 means that 1.2-2 is a mandatory assignment, 10.1-1 is a home assignment and 1.2-3 and 10.1-2 will be run through at the tutorials.

Mandatory assignments can be written on paper and placed in the course pigeonhole on first floor (outside the student administration office), or alternatively be submitted electronically by email to Esben Rune Hansen. All exercises and assignments are handed back on the following Friday.

Introduction to Algorithms and Data Structures, Schedule Spring 2005 (tentative)