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

1: January 21 (Wednesday)
Cormen reading: Chapter 1.
2: January 23 (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 26 (Monday)
We address, and illustrate on examples, how to prove (as is the topic of Assignment 1) the correctness of
4: January 28 (Wednesday)
5: January 30 (Friday)
We introduce the theory of asymptotic notation, cf. Cormen Chapter 3 or Howell Sections 3.1-3.3, and
6: February 2 (Monday)
February 4 (Wednesday)
Class canceled (instructor out of town).
Assignment 2 due tomorrow night.
7: February 6 (Friday)
We address (as in Howell 3.4-6) the complexity of iterative algorithms where we need to estimate sums; the "rectangle" is Also introduce the notion of a "barometer instruction" Discuss model solutions for Assignment 2 (uploaded on K-State Online).
8: February 9 (Monday)
Last day for 100% refund.
9: February 11 (Wednesday)
Mention various pitfalls in algorithm analysis: Wrap up the complexity of iterative algorithms:
10: February 13 (Friday)
Address general recurrences:
11: February 16 (Monday)
12: February 18 (Wednesday)
Elaborate on the Master Theorem: Introduce the "Dutch National Flag" problem, cf. Section 2.4 in Howell: Further discuss Assignment 4, due tomorrow night.
13: February 20 (Friday)
14: February 23 (Monday)
Review session for the upcoming midterm exam:
15: February 25 (Wednesday)
Exam I.
16: February 27 (Friday)
Introduce graphs, cf Cormen Appendix B.4, which An important special case is a (rooted) tree, cf Cormen Appendix B.5.
17: March 2 (Monday)
Introduce the heap data structure, cf Cormen Chapter 6: Motivate and discuss the upcoming Assignment 5.
18: March 4 (Wednesday)
Conclude the treatment of heaps: Further discuss (Question 3 in) Assignment 5, due tomorrow night.
19: March 6 (Friday)
20: March 9 (Monday)
21: March 11 (Wednesday)
Explore the Divide and Conquer paradigm, already motivated by merge sort (Cormen Section 2.3) and with further examples: Assignment 6 due tomorrow night.
22: March 13 (Friday)
Continue exploring the Divide & Conquer paradigm: we see clever applications that allow Mention the quests to
March 16-20
Spring break.
23: March 23 (Monday)
24: March 25 (Wednesday)
One more application of the Divide and Conquer paradigm: Further discuss Assignment 7, due tomorrow night.
25: March 27 (Friday)
Introduce dynamic programming, the topic of Cormen 15, which often allows an efficient implementation of exhaustive search:
26: March 30 (Monday)
Continue dynamic programming:
27: April 1 (Wednesday)
Continue Dynamic Programming:
28: April 3 (Good Friday)
Review session for the upcoming midterm exam:
April 6 (Monday)
Class canceled (instructor out of town)
but TA has office hours in Nichols 16A as usual: 3:30pm to 5pm, and by appointment.
29: April 8 (Wednesday)
Exam II.
April 10 (Friday)
Class canceled (All-University Open House)
30: April 13 (Monday)
We embark on greedy algorithms, the topic of Cormen 16:
31: April 15 (Wednesday)
Present algorithms for constructing a minimum-cost spanning tree, cf. Cormen 23:
32: April 17 (Friday)
33: April 20 (Monday)
34: April 22 (Wednesday)
Wrap up Greedy Algorithms: Introduce depth-first traversal of graphs (Cormen 22.3) Assignment 9 due tomorrow night.
35: April 24 (Friday)
Continue depth-first traversal of graphs, directed as well as undirected (Cormen 22.3); Motivate Question 2 in the upcoming Assignment 10.
36: April 27 (Monday)
Continue algorithms based on depth-first traversal:
37: April 29 (Wednesday)
Embark on Network Flow, cf. Cormen 26.1-3: Further discuss Assignment 10, due tomorrow night.
38: May 1 (Friday)
Elaborate on the Ford-Fulkerson method, motivated last time and described in Cormen 26.2: Discuss model solutions for (graded) Assignment 9.
39: May 4 (Monday)
Finish Network Flow: Wrap up Dynamic Programming: Motivate the upcoming Assignment 11.
40: May 6 (Wednesday)
Wrap up Dynamic Programming: Prepare for final exam: Assignment 11 due tomorrow night.
41: May 8 (Friday)
Prepare for final exam:
May 15 (Friday)
Final exam, 4:10-6:00pm


Torben Amtoft