Captain's Log: Introduction to Algorithm Analysis, Spring 2016

1: January 20 (Wednesday)
Cormen reading: Chapter 1.
2: January 22 (Friday)
Using the insertion sort method (Cormen Sections 2.1-2.2) as example, we Embark on how to prove the correctness of algorithms:
3: January 25 (Monday)
We address, and illustrate on examples, how to prove the correctness of Discuss the upcoming Assignment 1.
4: January 27 (Wednesday)
5: January 29 (Friday)
We introduce the theory of asymptotic notation, cf. Cormen Chapter 3 or Howell Sections 3.1-3.3, and Motivate the upcoming Assignment 2 (this web site may come handy).
February 1 (Monday)
Class canceled (instructor out of town).
6: February 3 (Wednesday)
Assignment 2 due tomorrow night.
7: February 5 (Friday)
Motivate, state and illustrate a general result (Theorem 3.28 in Howell) that is often useful for estimating sums found in the analysis of iterative programs: Discuss graded Assignment 1.
8: February 8 (Monday)
Mention various pitfalls in algorithm analysis: Wrap up the discussion of iterative algorithms: Address general recurrences: Last day for 100% refund
9: February 10 (Wednesday)
We address how to solve recurrences: Assignment 3 due tomorrow night.
10: February 12 (Friday)
11: February 15 (Monday)
Present a general recipe, the "Master Theorem", for solving recurrences: Discuss graded Assignment 3.
12: February 17 (Wednesday)
Elaborate on the Master Theorem: Assignment 4 due tomorrow night.
13: February 19 (Friday)
Introduce the "Dutch National Flag" problem, cf. Section 2.4 in Howell:
14: February 22 (Monday)
Review session for the upcoming midterm exam:
15: February 24 (Wednesday)
Exam I.
16: February 26 (Friday)
Introduce graphs, cf Cormen Appendix B.4, which An important special case is a (rooted) tree, cf Cormen Appendix B.5.
17: February 29 (Monday)
Introduce the heap data structure, cf Cormen Chapter 6: Motivate and discuss the upcoming Assignment 5.
18: March 2 (Wednesday)
Conclude the treatment of heaps: Further discuss Assignment 5, due tomorrow night.
19: March 4 (Friday)
Introduce union/find structures (cf Cormen Chapter 21, Sections 1-3):
March 7 (Monday)
Class canceled (instructor not well)
20: March 9 (Wednesday)
21: March 11 (Friday)
March 14-18
Spring break.
22: March 21 (Monday)
Explore the Divide and Conquer paradigm, already motivated by merge sort (Cormen Section 2.3) and with further examples: Motivate, and discuss in detail, the upcoming Assignment 7.
23: March 23 (Wednesday)
We see some clever applications of the Divide & Conquer paradigm: Further discuss Assignment 7, due tomorrow night.
24: March 25 (Good Friday)
Introduce dynamic programming, the topic of Cormen 15, which often allows an efficient implementation of exhaustive search: Motivate Assignment 8.
25: March 28 (Monday)
Continue dynamic programming:
26: March 30 (Wednesday)
Continue Dynamic Programming:
27: April 1 (Friday)
One more application of the Divide and Conquer paradigm: Motivate the chained matrix multiplication problem (Cormen 15.2).
April 4-8 (Monday-Friday)
Classes canceled (instructor out of town).
28: April 11 (Monday)
Review session for the upcoming midterm exam:
29: April 13 (Wednesday)
Exam II.
April 15 (Friday)
Class canceled (All-University Open House)
30: April 18 (Monday)
We embark on greedy algorithms, the topic of Cormen 16:
31: April 20 (Wednesday)
We address how to construct a minimum-cost spanning tree, cf. Cormen 23: Discuss and hand back graded Exam 2.
Assignment 9 due tomorrow night.
32: April 22 (Friday)
Introduce depth-first traversal of graphs, directed as well as undirected (Cormen 22.3): Motivate Question 2 in the upcoming Assignment 10.
33: April 25 (Monday)
Continue algorithms based on depth-first traversal:
34: April 27 (Wednesday)
Continue the construction of minimum-cost spanning trees: Continue the detection of shortest paths: Assignment 10 due tomorrow night.
35: April 29 (Friday)
Embark on Network Flow, cf. Cormen 26.1-3:
36: May 2 (Monday)
Continue and finish Network Flow:
37: May 4 (Wednesday)
Wrap up Greedy Algorithms: Discuss graded Assignments 9 & 10.
Assignment 11 due tomorrow night.
38: May 6 (Friday)
Prepare for final exam:
May 9 (Monday)
Final exam, 4:10-6:00pm


Torben Amtoft