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

1: January 23 (Wednesday)
Cormen reading: Chapter 1.
2: January 25 (Friday)
3: January 28 (Monday)
Embark on how to prove the correctness of algorithms:
4: January 30 (Wednesday)
Continue the correctness of iterative algorithms: we
5: February 1 (Friday)
6: February 4 (Monday)
Embark on the theory of asymptotic notation, cf. Cormen Chapter 3 Discuss the upcoming Assignment 2.
7: February 6 (Wednesday)
Continue (almost finish) asymptotic notation: Assignment 2 due tomorrow night.
8: February 8 (Friday)
Wrap up asymptotic notation: We next address (as in Howell 3.4-6) the complexity of iterative algorithms where we need to estimate sums; the "rectangle" is Briefly motivate the upcoming Assignment 3.
9: February 11 (Monday)
We finish the estimate of sums: as captured by Howell's Theorem 3.28, the "rectangle" is Discuss the upcoming Assignment 3.
10: February 13 (Wednesday)
Mention various pitfalls in algorithm analysis: We motivate the need to recurrences Further discuss Assignment 3, due tomorrow night.
11: February 15 (Friday)
We address how to solve recurrences;
to check a proposed solution, the substitution method (Cormen Section 4.3) can be used:
  1. we illustrate by one kind of example which is rather straightforward
  2. for another kind of example, the presence of logarithms requires a careful phrasing of the induction hypothesis (two approaches are possible)
12: February 18 (Monday)
Wrap up the substitution method: Present a general recipe, the "Master Theorem" (cf, e.g, Cormen Sections 4.4 & 4.5) for solving recurrences: Discuss the upcoming Assignment 4.
13: February 20 (Wednesday)
Elaborate on the Master Theorem: Briefly discuss Assignment 4, due tomorrow night.
14: February 22 (Friday)
Wrap up recurrences: Cover the "Dutch National Flag" problem, cf. Section 2.4 in Howell:
15: February 25 (Monday)
Review session for the upcoming midterm exam:
16: February 27 (Wednesday)
Exam I.
17: March 1 (Friday)
Introduce graphs, cf Cormen Appendix B.4, which An important special case is a (rooted) tree, cf Cormen Appendix B.5.
18: March 4 (Monday)
Wrap up graphs:
19: March 6 (Wednesday)
Introduce the heap data structure, cf Cormen Chapter 6: Assignment 5 due tomorrow night.
20: March 8 (Friday)

Wrap up heaps: Explore the Divide and Conquer paradigm: Discuss solutions to Assignment 5.
March 11-15
Spring break.
21: March 18 (Monday)
22: March 20 (Wednesday)
Elaborate on sorting: Further discuss Assignment 6, due tomorrow night.
23: March 22 (Friday)
We address how to multiply n-bit integers (or polynomials of degree n, cf Howell Section 10.1) We study the multiplication of n x n matrices (Cormen Section 4.2): Briefly motivate the upcoming Assignment 7.
24: March 25 (Monday)
25: March 27 (Wednesday)
One more application of the Divide & Conquer paradigm: Briefly further discuss Assignment 7, due tomorrow night.
26: March 29 (Friday)
Introduce dynamic programming, the topic of Cormen 15, which often allows an efficient implementation of exhaustive search: Very briefly motivate the upcoming Assignment 8.
27: April 1 (Monday)
Continue dynamic programming:
28: April 3 (Wednesday)
Continue dynamic programming: Assignment 8 due tomorrow night.
April 5 (Friday)
Class canceled (All-University Open House)
29: April 8 (Monday)
Review session for the upcoming midterm exam:
30: April 10 (Wednesday)
Exam II.
31: April 12 (Friday)
Introduce depth-first traversal of graphs, directed as well as undirected (Cormen 22.3):
32: April 15 (Monday)
The depth-first traversal algorithm may be augmented in several ways,
and for undirected graphs be used to
33: April 17 (Wednesday)
The depth-first traversal algorithm can also be augmented for directed graphs: Embark on Network Flow, cf. Cormen 26.1-3: Assignment 9 due tomorrow night.
34: April 19 (Good Friday)
35: April 22 (Monday)
We continue the study of flow networks: Discuss the upcoming Assignment 10.
36: April 24 (Wednesday)
Finish the study of flow networks: We embark on greedy algorithms, the topic of Cormen 16: Assignment 10 due tomorrow night.
37: April 26 (Friday)
We address how to construct a minimum-cost spanning tree, cf. Cormen 23: Briefly motivate the upcoming Assignment 11.
38: April 29 (Monday)
Present Dijkstra's algorithm (cf. Cormen 24.3) for single-source shortest paths: Discuss the upcoming Assignment 11, in particular the scheduling problem in Question 1.
39: May 1 (Wednesday)
Introduce union/find structures (cf Cormen Chapter 21, Sections 1-3): Briefly further discuss Assignment 11 (last of the semester), due tomorrow night.
40: May 3 (Friday)
Mention that one can implement union/find such that the "amortized" (average) cost per operation is We look at how to schedule events with fixed start/end time, cf. Cormen 16.1: Discuss solutions to Assignments 10, and 11(Q2).
41: May 6 (Monday)
Wrap up greedy algorithms: Some general observations:
May 8 (Wednesday)
Class canceled
42: May 10 (Friday)
Wrap up dynamic programming: Prepare for final exam: Discuss solutions to Assignment 9
May 16 (Thursday)
Final exam, 4:10-6:00pm


Torben Amtoft