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

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.