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

1: January 17 (Wednesday)
Cormen reading: Chapter 1.
2: January 19 (Friday)
Using the insertion sort method (Cormen Sections 2.1-2.2) as example, we Give a practice quiz using the iClicker system.
3: January 22 (Monday)
Embark on how to prove the correctness of algorithms:
4: January 24 (Wednesday)
Continue the correctness of iterative algorithms: we Assignment 1 due tomorrow night.
5: January 26 (Friday)
6: January 29 (Monday)
7: January 31 (Wednesday)
Finish asymptotic notation: Assignment 2 due tomorrow night.
8: February 2 (Friday)
Motivated by last quiz's exit poll, we We next address (as in Howell 3.4-6) the complexity of iterative algorithms where we need to estimate sums;
the "rectangle" is (as summarized in Howell's Theorem 3.28) Along the way, briefly motivate the upcoming Assignment 3.
9: February 5 (Monday)
Mention various pitfalls in algorithm analysis: Discuss various homework assignments: Conclude with a quiz.
Last day for 100 % refund.
10: February 7 (Wednesday)
We address how to solve recurrences Further discuss Assignment 3, due tomorrow night.
11: February 9 (Friday)
Continue the substitution method:
  1. recall the example from last time
  2. for another kind of example, the presence of logarithms requires a careful phrasing of the induction hypothesis (two approaches are possible)
  3. for a third kind of example, one needs some creativity to phrase the induction hypothesis
  4. conclude with a quiz.
Finish with a brief introduction to the "Master Theorem".
12: February 12 (Monday)
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 14 (Wednesday)
Elaborate on the Master Theorem: Assignment 4 due tomorrow night.
14: February 16 (Friday)
Cover the "Dutch National Flag" problem, cf. Section 2.4 in Howell:
15: February 19 (Monday)
Review session for the upcoming midterm exam:
16: February 21 (Wednesday)
Exam I.
17: February 23 (Friday)
Introduce graphs, cf Cormen Appendix B.4, which An important special case is a (rooted) tree, cf Cormen Appendix B.5.
18: February 26 (Monday)
Wrap up graphs: Motivate heaps, by discussing how to implement a priority queue
19: February 28 (Wednesday)
Introduce the heap data structure, cf Cormen Chapter 6: Further discuss Assignment 5, due tomorrow night.
20: March 2 (Friday)
21: March 5 (Monday)
22: March 7 (Wednesday)
Elaborate on sorting: Present another example of the divide-and-conquer paradigm: Assignment 6 due tomorrow night.
23: March 9 (Friday)
we study the multiplication of n x n matrices (Cormen Section 4.2): Briefly motivate the upcoming Assignment 7.
24: March 12 (Monday)
One more application of the Divide & Conquer paradigm: Further discuss the upcoming Assignment 7.
25: March 14 (Wednesday)
Introduce dynamic programming, the topic of Cormen 15, which often allows an efficient implementation of exhaustive search:
26: March 16 (Friday)
Continue dynamic programming:
March 19-23
Spring break.
27: March 26 (Monday)
28: March 28 (Wednesday)
29: March 30 (Good Friday)
Wrap up dynamic programming:
30: April 2 (Monday)
Review session for the upcoming midterm exam:
31: April 4 (Wednesday)
Exam II.
April 6 (Friday)
Class canceled (All-University Open House)
32: April 9 (Monday)
We embark on greedy algorithms, the topic of Cormen 16: Motivate the upcoming Assignment 9.
33: April 11 (Wednesday)
34: April 13 (Friday)
Introduce depth-first traversal of graphs, directed as well as undirected (Cormen 22.3): Motivate the problem of topological sort.
35: April 16 (Monday)
One may augment the depth-first algorithm in several ways:
36: April 18 (Wednesday)
Embark on Network Flow, cf. Cormen 26.1-3: Further discuss Assignment 10, due tomorrow night.
37: April 20 (Friday)
Continue Network Flow:
38: April 23 (Monday)
Finish Network Flow: Embark on the UnionFind slides: Discuss the upcoming Assignment 11
39: April 25 (Wednesday)
Introduce union/find structures (cf Cormen Chapter 21, Sections 1-3): Assignment 11 (last of the semester) due tomorrow night.
40: April 27 (Friday)
We address how to construct a minimum-cost spanning tree, cf. Cormen 23:
41: April 30 (Monday)
Present Dijkstra's algorithm (cf. Cormen 24.3) for single-source shortest paths: Quiz on Kruskal's algorithm, and Union-Find structures.
Discuss Q1 from Assignment 11.
42: May 2 (Wednesday)
Wrap up Greedy Algorithms:
43: May 4 (Friday)
Prepare for final exam:
May 9 (Wednesday)
Final exam, 4:10-6:00pm


Torben Amtoft