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

1: Aug 24 (Mon)
Introduction to course, going through syllabus.
Motivate the top-down approach to algorithm design, reducing problems to smaller problems.
Give a simple, but inefficient, implementation of the "maximum subsequence sum" problem.
Cormen Reading: Chapter 1.
2: Aug 26 (Wed)
Using the maximum subsequence sum problem and the insertion sort method as examples, we illustrate how to design algorithms by the top-down approach and then improve them by applying the bottom-up technique. Along the way, we give some simple complexity estimates.
Cormen Reading: Section 2.2.
3: Aug 28 (Fri)
We address how to prove the correctness of an algorithm, recursive or iterative, and illustrate the techniques on the various implementations of insertion sort.
Cormen Reading: Section 2.1.
Howell Reading: Sections 2.1-2.3 and 2.5-2.6.
4: Aug 31 (Mon)
We finish the correctness proof of iterative insertion sort, realizing the need to strengthen the invariant.
We introduce the "Dutch National Flag" problem, useful in a number of contexts.
Howell Reading: Section 2.4.
Homework 1 due Tue Sep 1 at 5pm
5: Sep 2 (Wed)
We develop a linear-time constant-space algorithm for the Dutch National Flag problem.
We embark on notations useful for asymptotic analysis, in particular "Big-O".
Cormen Reading: Section 3.1.
Howell Reading: Sections 3.1 & 3.2.
6: Sep 4 (Fri)
We continue the theory of asymptotic notation, reasoning about properties of "Big-O", and introducing "Big-Omega", "Big-Theta", "little-o", and "little-omega".
Cormen Reading: Section 3.2.
Howell Reading: Sections 3.3 & 3.4 & 3.10 & 3.11.
Sep 7 (Mon)
University Holiday (Labor Day)
7: Sep 9 (Wed)
We finish the theory of asymptotic notation, reasoning about how the various symbols interact, and how to soundly generalize to more than one variable.
Graded HW1 back; briefly go through model solutions.
Howell Reading: Section 3.9.
Homework 2 due Thu Sep 10 at 5pm
8: Sep 11 (Fri)
We introduce amortized analysis.
Cormen Reading: Chapter 17.
9: Sep 14 (Mon)
We discuss how to apply amortized analysis to expandable arrays.
We mention some pitfalls in the analysis of algorithms.
We embark on techniques for approximating iterative algorithms.
Howell Reading: Sections 4.3 & 4.5.
10: Sep 16 (Wed)
We show how to give tight bounds for iterative algorithms, using the concept of a smooth function.
Howell Reading: Sections 3.5 & 3.6.
Homework 3 due Thu Sep 17 at 5pm
11: Sep 18 (Fri)
We embark on solving general recurrences, motivating and stating the Master Theorem (Thm 4.1 in Cormen).
Cormen Reading: Section 2.3 & Sections 4.1-4.3.
12: Sep 21 (Mon)
We outline a proof of the Master Theorem, and briefly discuss Question 4 in HW4.
Howell Reading: Sections 3.7 & 3.8.
13: Sep 23 (Wed)
We saw an example where to apply the Master Theorem, one needs to define S(k) = T(2^k).
We saw an example, T(n) = 2T(n/2) + n log(n), where Cormen's Theorem 4.1 is not applicable, the Master Theorem from the slides gives a solution sandwiched between n log(n) and n^q for any q > 1, but Howell's Theorem 3.32 gives the exact order n log^2(n).
We continue the discussion of HW4, in particular Question 4.
We embark on discussing the heap data structure.
Cormen Reading: Chapter 6.
Homework 4 due Thu Sep 24 at 5pm
Sep 25 (Fri)
Class canceled
14: Sep 28 (Mon)
We show how a heap can be used to implement a priority queue, as well as an efficient in-place sorting algorithm.
Graded Homework 2 back.
15: Sep 30 (Wed)
We discuss ways to merge two heaps, cf. the upcoming HW5.
Howell Reading: Sections 5.2-4.
We embark on union/find structures.
Cormen Reading: Sections 21.1-3.
16: Oct 2 (Fri)
Develop union/find structures where the amortized cost of an operation is almost in O(1).
Briefly cover how to represented graphs, and virtual array initialization.
Graded Homework 3 back; go through model solutions for Homeworks 2 & 3 & 4.
Oct 5 (Mon)
Student Holiday
Homework 5 due Tue Oct 6 at 5pm
17: Oct 7 (Wed)
Exam 1
18: Oct 9 (Fri)
We now embark on a detailed study of the divide and conquer paradigm, with quicksort an important application.
Cormen Reading: Sections 7.1-2.
We discuss the question on "good/bad machines" from HW4.
19: Oct 12 (Mon)
We continue applications of the divide & conquer paradigm: multiplication of large integers (or polynomials), matrix multiplication, the selection problem (not finished).
Howell Reading: Sections 10.1 & 10.4.
20: Oct 14 (Wed)
We finish an algorithm for the selection problem that always runs in linear time.
Graded HW 4 back, and elaborate on some of the model solutions.
We briefly discuss the first two questions of the upcoming HW6.
Cormen Reading: Section 9.3.
21: Oct 16 (Fri)
By means of examples, we introduce some key concepts of probability theory, to prepare for randomized algorithms.
We continue the discussion of the upcoming HW6.
Cormen Reading: Section 5.4.1.
22: Oct 19 (Mon)
We introduce the concept of randomized algorithms, illustrated by examples.
Cormen Reading: Chapter 5 (Sect 5.4 cursory only).
Homework 6 due Tue Oct 20 at 5pm
23: Oct 21 (Wed)
We discuss how, and how not, to randomly permute an array.
We analyze randomized quicksort, and randomized selection.
Cormen Reading: Sections 7.3-4; Section 9.2.
24: Oct 23 (Fri)
We give an upper bound for expected path lengths, discuss the upcoming HW 7, and briefly start on lower bounds for problems.
Howell Reading: Section 5.5.
25: Oct 26 (Mon)
We establish lower bounds for various problems, using information theory, as well as using "adversary arguments".
Cormen Reading: Section 8.1.
26: Oct 28 (Wed)
We finish the adversary argument that shows the lower bound for graph connectivity.
We exhibit sorting algorithms, in particular counting sort, that run in linear time.
Graded HW5 back; briefly discuss model solutions.
Cormen Reading: Sections 8.2 & 8.3.
Homework 7 due Thu Oct 29 at 5pm
27: Oct 30 (Fri)
Graded Exam 1 back; go through model solutions.
We present bucket sort, another linear-time sorting algorithm.
We introduce Monte-Carlo algorithms.
Cormen Reading: Section 8.4.
28: Nov 2 (Mon)
We embark on greedy algorithms, motivating the concept and giving several examples.
Howell Reading: Section 11.1.
29: Nov 4 (Wed)
We continue greedy algorithms, with focus on computing a minimum spanning tree of a connected undirected graph:
we present Kruskal's algorithm, analyze its complexity, and prove its correctness.
Howell Reading: Section 11.2.
30: Nov 6 (Fri)
We finish the presentation of greedy algorithms, covering:
Prim's algorithm, Dijkstra's algorithm for single-source shortest paths, one-room scheduling of events with fixed start & end time.
Howell Reading: Section 11.3.
31: Nov 9 (Mon)
We show that Dynamic Programming can be used to efficiently compute optimal change even when the coin set does not permit a greedy solution.
Discuss the (first two questions from the) upcoming Assignment 8.
Howell Reading: Section 12.1.
32: Nov 11 (Wed)
We show how to apply dynamic programming to the binary knapsack problem.
We further discuss the upcoming Assignment 8.
Howell Reading: Section 12.4.
Homework 8 due Thu Nov 12 at 5pm
33: Nov 13 (Fri)
We apply dynamic programming to derive Floyd's all-pair shortest path algorithm.
We discuss the upcoming Homework 9.
We discuss model solutions for Homework 6.
Howell Reading: Section 12.3.
34: Nov 16 (Mon)
We discuss model solutions for Homeworks 7 & 8.
We further discuss the upcoming Homework 9.
We briefly sketch one more application of dynamic programming: chained matrix multiplication.
Howell Reading: Section 12.2.
Homework 9 due Tue Nov 17 at 5pm
35: Nov 18 (Wed)
Exam 2
36: Nov 20 (Fri)
We introduce the sets P and NP, the concept of polynomial many-one reduction, and the class of NP-hard problems.
Howell Reading: Sections 16.2 & 16.3.
37: Nov 23 (Mon)
Present a number of NP-hard problems, among which we reduce Clique to VertexCover (so as to establish that the latter is NP-hard provided the former is).
Cormen Reading: Sections 34.1-4.
Nov 25-27 (Wed-Fri)
Thanksgiving holiday
38: Nov 30 (Mon)
Recall various NP-complete problems and how to prove that they are indeed NP-hard; in particular, we reduce 3-Sat to Clique.
Graded Exam 2 back; go through model solutions. Graded HW 6 & 7 back.
Cormen Reading: Section 34.5 (except Sects. 34.5.3&5).
39: Dec 2 (Wed)
Sketch how to reduce from CSat to 3-Sat, and from Sat to CSat.
Introduction to Approximation Algorithms.
Discuss the last question of the upcoming HW10.
Homework 10 due Thu Dec 3 at 5pm
40: Dec 4 (Fri)
Continue Approximation Algorithms: Howell Reading: Sections 17.1 & 17.4.
41: Dec 7 (Mon)
See that some NP-complete problems can be approximated by algorithms that yield arbitrarily high precision yet are polynomial.
Graded HW8 back.
Howell Reading: Sections 17.2 & 17.5.
42: Dec 9 (Wed)
Discuss depth-first traversal of graphs, directed as well as undirected.
Illustrate that many graph problems can be solved by algorithms that build on depth-first traversal.
Cormen Reading: Sections 22.3-4.
43: Dec 11 (Fri)
Homework 11 due at 3pm
Go through model solutions for Homeworks 9, 10, and 11.
Dec 15 (Tue)
Review session, 3-4pm in N126.
Dec 16 (Wed)
Final exam, 4:10-6:00pm


Torben Amtoft