Captain's Log: CIS 775, Analysis of Algorithms, Fall 2008

1: August 25 (Monday)
Introduction to course, going through syllabus.
Embark on Chapter 1 of textbook, covering until p.10, in particular giving two simple (but inefficient) implementations of the "maximum subsequence sum" problem.
Slides for Sections 1.1-1.4
2: August 27 (Wednesday)
Homework 1 out.
Continue Chapter 1, covering pp.11--20: we apply the "Divide and Conquer" paradigm to get a quite efficient solution to the maximum subsequence sum problem but the best solution is found by applying the bottom-up technique; we also introduce the "Dutch National Flag" problem.
3: August 29 (Friday)
Finish Chapter 1, by developing algorithms for solving the Dutch National Flag problem.
Do Exercises 1.1 & 1.4.
September 1 (Monday)
University Holiday (Labor Day)
4: September 3 (Wednesday)
Embark on Chapter 2, showing how to prove the correctness of recursive algorithms (such as InsertSort from Fig.1.3) using the induction principle, and how to prove the correctness of iterative algorithms (such as MaxSuffixBU from Fig.1.11) using a 4-point checklist.
Homework 1 due Thu Sep 4 at 5pm
5: September 5 (Friday)
We prove correct the InsertionSort algorithm of Fig.2.2, while discussing a couple of pitfalls.
6: September 8 (Monday)
Go through HW 1 model solutions. Embark on Chapter 3, introducing big-O/big-Omega/big-Theta notation and proving closure properties (Corollary 3.16).
7: September 10 (Wednesday)
Continue Chapter 3: define worst-case complexity; then motivate and apply Theorem 3.28 which uses the notion of "smooth" functions.
8: September 12 (Friday)
Continue Chapter 3: first give more examples of how to apply Theorem 3.28 to analyze while-loops; next show how to analyze "(n-1)" recursion, by means of Theorem 3.31.
9: September 15 (Monday)
Continue Chapter 3, with focus on the crucial Theorem 3.32. Also discuss space complexity, observing that space (unlike time) can be reused. Introduce little-o and little-omega.
Homework 2 due Tue Sep 16 at 5pm
10: September 17 (Wednesday)
Finish Chapter 3, by discussing what Big-O means for binary functions. Cover Sections 4.1 and 4.2, on abstract data types and their implementations.
11: September 19 (Friday)
Cover Section 4.3 and 4.5, motivating and introducing amortized analysis.
12: September 22 (Monday)
Finish Chapter 4, by covering Section 4.4 on immutable lists.
Go through HW2 model solutions.
Discuss the upcoming HW3.
Homework 3 due Tue Sep 23 at 5pm
13: September 24 (Wednesday)
Introduce priority queues, with focus on implementation using leftist heaps, covering Sections 5.1-5.3.
Graded Homework 2 back.
14: September 26 (Friday)
Cover Sections 5.4 and 5.5 on skewed and randomized heaps.
Cover Sections 8.1-8.3 on the union-find implementation of disjoint sets.
15: September 29 (Monday)
Mention how heaps can be used for sorting, even "in-place" using binary heaps (Section 5.6).
Mention how compression on union-find structures gives "almost" constant amortized complexity (Section 8.4).
Go through HW3 model solutions.
Discuss Exercise 8.13 from Homework 4.
Homework 4 due Tue Sep 30 at 5pm
16: October 1 (Wednesday)
Exam 1
17: October 3 (Friday)
Go through HW4 model solutions.
Go through Exam 1 model solutions.
Graded HW3 back.
October 6 (Monday)
Student Holiday
18: October 8 (Wednesday)
Embark on Chapter 10 on the "divide and conquer" paradigm, covering polynomial multiplication (Section 10.1) and discussing lower bounds on sorting.
19: October 10 (Friday)
Discuss the upcoming Homework 5.
Graded HW4 back.
20: October 13 (Monday)
Graded Exam 1 back.
Cover merge sort (Section 10.2), motivated by the desire for a "stable" sorting algorithm.
Start on quick sort (Section 10.3).
Homework 5 due Tue Oct 14 at 5pm
21: October 15 (Wednesday)
Discuss quick sort in detail (Section 10.3).
Solve the selection problem (Section 10.4).
22: October 17 (Friday)
Embark on Greedy Algorithms, with job scheduling (Section 11.1) the motivating example.
Discuss the upcoming HW6.
October 20 (Monday)
Class canceled (Instructor out of town)
Homework 6 due Tue Oct 21 at 5pm
23: October 22 (Wednesday)
Greedy strategies for constructing a minimum-cost spanning tree (Section 11.2), one of which results in Kruskal's algorithm.
Graded HW5 back, going through model solutions.
24: October 24 (Friday)
Go through HW6 model solutions.
Briefly discuss the upcoming HW7.
25: October 27 (Monday)
Compare Kruskal's algorithm to Prim's algorithm (Section 11.2), the latter being similar to Dijkstra's shortest path algorithm (Section 11.3).
Cover Huffman codes (Section 11.4), thus finishing Chapter 11.
Discuss the upcoming HW7, in particular Exercise 11.14.
Homework 7 due Tue Oct 28 at 5pm
26: October 29 (Wednesday)
Exam 2
27: October 31 (Friday)
Go through Exam 2 model solutions.
Go through HW7 model solutions (11.9 & 11.10).
28: November 3 (Monday)
Embark on Dynamic Programming, motivated by finding optimal change (Section 12.1).
Graded HW6 back.
29: November 5 (Wednesday)
More applications of Dynamic Programming: Chained Matrix Multiplication (Section 12.2); All-Pairs Shortest Paths (Section 12.3)
30: November 7 (Friday)
Finish HW7 model solutions (11.14).
Yet another application of Dynamic Programming: the Discrete Knapsack Problem (Section 12.4).
Discuss the upcoming Homework 8.
Graded HW7 back.
31: November 10 (Monday)
Show how to conduct a generic depth-first search (Section 13.3) so as to produce a depth-first spanning tree (helpful to decide graph reachability, cf. Section 13.2) and also number the vertices in pre/postorder (helpful to decide ancestry, cf. Section 13.1)
Continue discussing Exercise 12.12 from the upcoming HW8.
Homework 8 due Tue Nov 11 at 5pm
32: November 12 (Wednesday)
See some applications of depth-first search: for undirected graphs, find articulation points (Section 13.4); for (acyclic) directed graphs, find a topological sort (Section 13.5).
33: November 14 (Friday)
Finish Chapter 13, by covering Section 13.6 on finding strongly connected components.
Discuss the upcoming Homework 9.
34: November 17 (Monday)
Embark on Chapter 14 on Network Flows, giving the Ford-Fulkerson algorithm for finding maximum flow (Section 14.1).
Further discuss Exercise 13.10 from the upcoming HW9.
Homework 9 due Tue Nov 18 at 5pm
35: November 19 (Wednesday)
Cover the Edmonds-Karp algorithm (Section 14.2).
Reduce the bipartite matching problem to maximum network flow.
Graded HW8 back; go through model solutions.
36: November 21 (Friday)
Finish Chapter 14, giving a specialized algorithm for the bipartite matching problem (Section 14.3).
Discuss the upcoming HW10.
37: November 24 (Monday)
Graded Exam II back.
Discuss Exercise 14.11 from the upcoming HW 10.
Go through Exercise 13.12 from the HW9 model solutions.
Homework 10 due Tue Nov 25 at 5pm
November 26-28 (Wednesday-Friday)
Thanksgiving holiday
38: December 1 (Monday)
Graded HW9 back; go through model solutions.
Go through HW10 model solutions.
39: December 3 (Wednesday)
Exam 3
40: December 5 (Friday)
Cover Section 16.1, introducing the sets P and NP, and the notions of NP-hard and NP-complete. Mention that Sat is NP-complete (Cook's Theorem).
Graded HW10 back.
41: December 8 (Monday)
Try to clarify the definitions of NP, NP-hard, NP-complete, etc.
Outline Sections 16.2 & 16.3, giving reductions that show the NP-completeness of various problems, thus motivating Exercises 16.7 & 16.13 from the upcoming HW11.
Motivate Exercise 17.2 from the upcoming HW11 by recalling how a greedy strategy may be suboptimal for the 0-1 knapsack problem.
42: December 10 (Wednesday)
Briefly introduce approximation algorithms (Sections 17.1 & 17.2), with focus on polynomial approximation schemes for the 0-1 knapsack problem, thus setting the stage for Exercises 17.1 and 17.2 from the upcoming HW11.
43: December 12 (Friday)
Homework 11 due at 3:30pm
Discuss fully polynomial approximation schemes (Section 17.2).
Go through model solutions for Homework 11.
Go through model solutions for Exam III.
December 16 (Tuesday)
Review session, 4:30-5:30pm in N122. Canceled due to instructor mishap.
December 17 (Wednesday)
Final exam, 4:10-6:00pm


Torben Amtoft