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

1: January 22 (Wednesday)
Cormen reading: Chapter 1.
2: January 24 (Friday)
Using the insertion sort method as example, we Cormen reading: Sections 2.1-2.2.
3: January 27 (Monday)
We address, and illustrate on various implementations of insertion sort, how to prove (as is the topic of Assignment 1) the correctness of
4: January 29 (Wednesday)
We further discuss Assignment 1, due Thursday night: We then finish the correctness proof of iterative insertion sort, treating also the inner loop for which it is not obvious how to find an invariant that is strong enough.
5: January 31 (Friday)
6: February 3 (Monday)
We introduce the theory of asymptotic notation, cf. Cormen Chapter 3, and
February 5 (Wednesday)
University closed due to snow.
7: February 7 (Friday)
Finish the theory of asymptotic notation: Discuss Assignment 2, due Monday night (where this web site may come handy).
8: February 10 (Monday)
We address the complexity of iterative algorithms where we need to estimate sums: Assignment 2 is due tonight.
Last day for 100% refund.
9: February 12 (Wednesday)
Discuss model solutions for Assignment 2, Q1.
Further discuss Assignment 3, due tomorrow night.
10: February 14 (Friday)
Address general recurrences: Cormen reading: Section 4.3.
11: February 17 (Monday)
We give a general recipe, the "Master Theorem", for solving recurrences: Discuss the upcoming Assignment 4.
Discuss model solutions for Assignment 2, Q2 and Q3, also proving (cf. Q1) that log(n!) in Theta(n log(n)).
12: February 19 (Wednesday)
Elaborate on the Master Theorem: Introduce graphs, cf. Cormen Appendix B.4, which
13: February 21 (Friday)
Extension: Assignment 4 due tonight.
14: February 24 (Monday)
Review session for the upcoming midterm exam:
15: February 26 (Wednesday)
Exam I.
16: February 28 (Friday)
Brief summary of general principles for Data Structures: Introduce the heap data structure Cormen: Sections 6.1, 6.2, 6.5.
17: March 3 (Monday)
Continue heaps: Cormen: Sections 6.3 & 6.4.
Yang Xue's office hours are Tuesday, 3:30pm-5pm.
18: March 5 (Wednesday)
We introduce union/find structures (cf Cormen Chapter 21, Sections 1-3): Further discuss Assignment 5, due tomorrow night.
19: March 7 (Friday)
Finish Union/Find structures: Explore the Divide and Conquer paradigm, with motivating examples: Discuss and hand back graded Exam 1.
20: March 10 (Monday)
21: March 12 (Wednesday)
Continue the Divide & Conquer paradigm: we see clever applications that allow Further discuss Assignment 6, due tomorrow night.
22: March 14 (Friday)
Mention the quests to One more application of the Divide and Conquer paradigm: We discuss model solutions for Assignment 6, Q1 & Q2.
March 17-21
Spring break.
23: March 24 (Monday)
24: March 26 (Wednesday)
Introduce dynamic programming, the topic of Cormen 15, which often allows an efficient implementation of exhaustive search. Briefly further discuss Assignment 7, due tomorrow night.
25: March 28 (Friday)
One more application of Dynamic Programming: Discuss model solutions for Assignment 7.
26: March 31 (Monday)
Continue Dynamic Programming:
27: April 2 (Wednesday)
Continue Dynamic Programming: Further discuss Assignment 8, due tomorrow night.
April 4 (Friday)
Class canceled (All-University Open House)
28: April 7 (Monday)
Review session for the upcoming midterm exam: Use dynamic programming to find optimal solution for chained matrix multiplication (Cormen 15.2)
29: April 9 (Wednesday)
Exam II.
30: April 11 (Friday)
We embark on greedy algorithms, the topic of Cormen 16:
31: April 14 (Monday)
Continue algorithms for finding minimum-cost spanning trees: Discuss the upcoming Assignment 9
32: April 16 (Wednesday)
33: April 18 (Good Friday)
More applications of the greedy paradigm: Discuss model solutions for Assignment 9, and movitate the upcoming Assignment 10.
34: April 21 (Monday)
Introduce depth-first traversal of graphs, directed as well as undirected (Cormen 22.3). Discuss the upcoming Assignment 10.
35: April 23 (Wednesday)
See several graph problems that can be solved by algorithms that build on depth-first traversal: Assignment 10 due tomorrow night.
36: April 25 (Friday)
37: April 28 (Monday)
Embark on Network Flow, cf. Cormen 26.1-3: Discuss how the "Nearest Neighbor" heuristics may be arbitrarily bad for the Traveling Salesman Problem even when the triangle inequality holds.
38: April 30 (Wednesday)
Continue Network Flow: Discuss Question 1 in the upcoming Assignment 11.
39: May 2 (Friday)
Finish Network Flow:
40: May 5 (Monday)
41: May 7 (Wednesday)
42: May 9 (Friday)
Discuss questions from the exams for
May 15 (Thursday)
Final exam, 4:10-6:00pm


Torben Amtoft