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:
-
in some situations,
we can construct polynomial algorithms
that are guaranteed to approximate within a factor two;
-
in other situations, such algorithms cannot exist (unless P = NP).
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