Introduction to Algorithms and Data Structures, Course Schedule Fall 2004

Exam Curriculum is comprised of all the subjects mentioned under the Subject column in the schedule below.

Episode	Date	Text	Subject	Teacher(s)	Mandatory assignments due before 13.00 on
0	August 26, 2004	CLRS Appendix B.1, B.2, B.3, B.4, B.5 and C.1	Discrete math and combinatorics primer	VS AW
1	August 30, 2004	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.	VS AW	September 10, 2004
2	September 6, 2004	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	VS	September 17, 2004
3	September 13, 2004	CLRS chap. 7.1-3; chap. 8.1-3; Introduction to Part III (pages 196-199).	Quicksort, sorting by comparisons, lower bound on comparison sorting (with proof), Counting-Sort, stable&unstable sorting	AW	October 1, 2004
4	September 20, 2004	CLRS chap. 11.1-11.3.1 (omit proofs)	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. Major Week Assignment 1	AW & ERH	September 24, 2004
5	September 27, 2004	Handout + CLRS Appendix B.4-B.5 pp. 1080-1090, Chap 4.1-3 pp. 62-72, Chap. 10.4 pp. 214-216, and Chap. 12.1-2. pp. 253-262 + another handout	Simple proofs with mathematical induction, recurrences, substitution method, recurrence tree method, master method, binary search trees, tree traversals, various search operations on trees (most notably Search-Tree and Min-Tree).	AW	October 8, 2004
6	October 4, 2004	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.	VS	October 15, 2004
7	October 11, 2004	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	October 22, 2004
8	October 18, 2004	CLRS 17.1-2 and 21.1-3	Amortised Analysis: aggregate & accounting methods. Equivalence relations, disjoint sets and Union-Find, connected components, linked-list representation, forest representation.	AW	October 29, 2004
9	October 25, 2004	CLRS 22.1–22.4.	Graph representations. Breadth-first search. Depth-first search. Topological sort.	VS	November 5, 2004
10	November 1, 2004	CLRS 23.1–23.2 (Prim's algorithm is optional); CLRS 24.1–3; optionally 24.5.	Minimum spanning trees. Kruskal's algorithm. Single-source shortest paths in weighted graphs. The Bellman–Ford algorithm. Shortest paths in DAGs. Dijkstra's algorithm.	VS	November 19, 2004
11	November 8, 2004		Major Week Assignment 2	ERH	November 12, 2004
12	November 15, 2004		F2003 exam set	VS

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

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, or alternatively be submitted electronically by email to Esben Rune Hansen. All exercises and assignments are handed back on Monday of the following week.

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