Introduction to Algorithms and Data Structures, Course Schedule Fall 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	September 5, Monday!	CLRS Appendix B.1, B.2, B.3, B.4, B.5 and C.1	Discrete math and combinatorics primer	AW	no formal exercises
1	August 31, 2005	CLRS Chap. 1, 2.1, 2.2, 10.1, and 10.2	Introduction. Computational Problems and Algorithms. Basic Data Structures. Resources. Sorting. Insertion-Sort. Correctness proofs with loop invariants. Running time estimates.	AP	September 12, 2005
2	September 7, 2005	CLRS Chap. 3, 2.3 (skip 2.3.2), 6	Growth rates of functions. Sorting. Divide & Conquer technique and Merge-Sort; Heaps, Max-Heaps, and Heap-Sort; Priority Queues.	AP	September 19, 2005
3	September 14, 2005	CLRS chap. 7.1-3; chap. 8.1-2;	Quicksort, sorting by comparisons, lower bound on comparison sorting (with proof), Counting-Sort, stable&unstable sorting.	AW	September 26, 2005
4	September 21, 2005	CLRS 8.3, this paper (you may skip section 3)	Implementing radix sorting: LSD&MSD Radix-Sort, MSD Radix-Sort with explicit stack, Forward-Radix-Sort IADS programming contest!	AW	October 3, 2005
5	September 28, 2005	Weiss pp.173-189 + CLRS Appendix B.4-B.5 pp. 1080-1090, Chap 4.1-3 pp. 62-72 + optionally GKP chapter 1.	Simple proofs with mathematical induction, recurrences, substitution method, recurrence tree method, master method.	AW	October 10, 2005
6	October 5, 2005	CLRS 10.4, 12.1–3 supplemented by Weiss pp. 508–516	Search trees: binary search trees, tree traversals, various search operations on trees (most notably Search-Tree and Min-Tree) 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	October 24, 2005
7	October 12, 2005	CLRS Chap. 15.1—15.3	Dynamic programming.	AW	October 31, 2005
	October 19, 2005		No lecture. Fall break.
8	October 26, 2005	CLRS 11.0-11.3 (omit proofs), PaghR pages 1-5 (not sec. 2.1), and 17.0-17.2	Hashing: Guest lecture by Rasmus Pagh. Amortised Analysis: aggregate & accounting methods.	RP/AP	November 7, 2005
9	November 2, 2005	CLRS 21.1-21.3 and 22.1-22.2	Union-Find: Disjoint sets, connected components, linked-list representation, forest representation. Introduction to graph algorithms: Graph representations. Breadth-first search.	AP	November 14, 2005
10	November 9, 2005	CLRS 22.3-22.4 and 23.1-23.2 (Prim's algorithm is optional)	Depht-first search, Topological sort, Minimum spanning trees.	AP	November 21, 2005
11	November 16, 2005	24.1-24.3 (optionally 24.5)	Single-Source Shortest Paths: Bellman-Ford and Dijkstra	AP	November 25, 2005
12	November 23, 2005		Exam preparation. Summary (slides). Evaluation.	AP
Exam	January 11, 2006, 9.00-13.00.		Exam.

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

PaghR="Pagh and Rodler: Cuckoo hashing"

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).

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