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

1: Aug 20 (Mon)


Introduction to course,
going through syllabus.

Using the insertion sort method as example,
we illustrate how to design algorithms by the topdown
approach and then improve them
by applying the bottomup technique.
Along the way, we give some simple complexity estimates.
Cormen Reading: Chapter 1 and Section 2.2.
(Howell Reading: Sections 1.11.4.)

2: Aug 22 (Wed)

We address how to prove the correctness of an algorithm,
recursive or iterative,
and illustrate the techniques on various implementations
of insertion sort.
Cormen Reading: Section 2.1.
(Howell Reading: Sections 2.12.3.)

3: Aug 24 (Fri)


We finish the correctness proof of iterative insertion sort
(Theorem 2.7 in Howell),
realizing the need to strengthen the invariant.

Students introduce themselves and their motivation for taking the course.

We introduce the "Dutch National Flag" problem,
useful in a number of contexts.
(Howell Reading: Section 2.4.)

4: Aug 27 (Mon)


We develop a lineartime constantspace algorithm for
the Dutch National Flag problem

We introduce the "BigO" symbol, useful for asymptotic analysis,
and reason about its properties.
Cormen Reading: Chapter 3.
(Howell Reading: Sections 3.13.2.)

5: Aug 29 (Wed)

We continue the theory of asymptotic notation, and

introduce
"BigOmega",
"BigTheta",
"littleo", and
"littleomega"

reason about how the various symbols interact
Howell Reading: Sections 3.3 & 3.10.
We also discuss Assignment 1, due tomorrow at 4pm.

6: Aug 31 (Fri)


We mention some pitfalls in the analysis of algorithms.

We discuss how to soundly generalize the BigO notation
to more than one variable.
Howell Reading: Section 3.9.

Sep 3 (Mon)

University Holiday (Labor Day)

7: Sep 5 (Wed)

We address the complexity of iterative algorithms,
where we need to estimate sums:

Upper approximations are straightforward

Lower approximations require that the
functions are smooth
Howell reading: Section 3.46
Assignment 2 due tomorrow at 4pm.

8: Sep 7 (Fri)


Hand back graded Assignment 1 and go through model solutions

Motivate general recurrences:

they show up when
analyzing divide and conquer algorithms

to check a proposed solution,
the substitution method can be used.
Cormen Reading: Sections 2.3 & 4.3.

9: Sep 10 (Mon)


We give a general recipe for solving recurrences,
cf. the Master Theorem (Thm 4.1 in Cormen),
and look at simple applications.

We discuss the upcoming Assignment 3.
Cormen Reading: Sections 4.4 & 4.5.
(Howell reading: Sections 3.78.)

10: Sep 12 (Wed)


Hand back graded Assignment 2 and go through model solutions.
We finish discussing the Master Theorem:

we give an example where to apply the Master Theorem,
one needs to define S(k) = T(2^k).

we give 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 outline a proof
Optional Cormen Reading: Section 4.6.1.
Assignment 3 due tomorrow at 4pm.

11: Sep 14 (Fri)

We embark on a detailed study of the
divide and conquer paradigm, with applications such as

merge sort (Howell Section 10.2 or Cormen Section 2.3)

quicksort (Cormen Sections 7.12 or Howell Section 10.3)

multiplication of large integers, or polynomials
(Howell Section 10.1)

12: Sep 17 (Mon)

We continue our study of the divide and conquer paradigm,
with applications such as

matrix multiplication
(Cormen Section 4.2)

the selection problem
which has a clever solution that
always runs in linear time
(Cormen Section 9.3 or Howell Section 10.4).

13: Sep 19 (Wed)


Hand back graded Assignment 3 and go through model solutions.

Discuss Question 2 in the upcoming Assignment 4.

Introduce amortized analysis,
cf.
Cormen Chapter 17 (or Howell Sections 4.3&4.5).
Assignment 4 due tomorrow at 4pm.

14: Sep 21 (Fri)


Motivate Question 1 in the upcoming Assignment 5

Introduce expandable arrays and give amortized analysis

Introduce the heap data structure,
and use heaps to implement priority queues.
Reading: Cormen Chapter 6
(or Howell Sections 5.12&6).

15: Sep 24 (Mon)


Show how to use heaps for
efficient and inplace sorting

Motivate Question 2 in the upcoming Assignment 5.

16: Sep 26 (Wed)


Hand back graded Assignment 4 and go through model solutions.

Further discuss the upcoming Assignment 5.

Discuss previous exam questions.
Assignment 5 due tomorrow at 4pm.

17: Sep 28 (Fri)

Exam 1

18: Oct 1 (Mon)


We introduce union/find structures,
useful to represent equivalence classes of nodes;
it is possible to obtain an amortized cost per operation
which is almost in O(1).

Briefly cover possible graph representations.

Briefly mention virtual array initialization.
Cormen: Chapter 21, Sections 13
(or Howell Chapter 8, Sections 13)

19: Oct 3 (Wed)

Introduce dynamic programming
(Cormen 15.1 & 15.3),
often allowing an efficient implementation of
exhaustive search, and illustrated by

giving optimal change (Howell 12.1)

binary knapsack problem (Howell 12.4)

20: Oct 5 (Fri)

We see more applications of dynamic programming:

Floyd's allpair shortest paths
algorithm (Howell 12.3 or Cormen 25.2)

chained matrix multiplcation (Howell 12.2 or Cormen 15.2)
Hand back graded Assignment 5.
Assignment 6 due at 5pm.

21: Oct 8 (Mon)


Motivate Assignment 7, just posted.

Discuss graded Assignment 5.

Discuss and hand back graded Exam 1.

22: Oct 10 (Wed)

Karthik, the TA, will be in class to discuss
the upcoming Assignment 7.

Oct 12 (Fri)

Class canceled
Assignment 7 due at 4pm.

23: Oct 15 (Mon)

We embark on greedy algorithms
(the topic of
Cormen 16 or Howell 11):

motivate the concept

show a greedy strategy for
the fractional knapsack problem, cf.
Cormen 16.2

present Kruskal's algorithm
for constructing a
minimumcost spanning tree, cf.
Cormen 23 or Howell 11.2

24: Oct 17 (Wed)


Present the proof that Kruskal's algorithm
returns a correct solution

Discuss how the above proof technique
is generally applicable for greedy algorithms

Present Prim's algorithm (a variation of Kruskal's)
for constructing a minimumcost spanning tree

Present Dijkstra's algorithm for singlesource shortest paths,
cf. Howell 11.3 or Cormen 24.3

Discuss the upcoming Assignment 8

25: Oct 19 (Fri)

Finish Greedy Algorithms:

Scheduling of events, cf. Cormen 16.1

Huffman codes, cf. Howell 11.4 or Cormen 16.3
Introduction to
key concepts
of probability theory, cf Cormen Chapter 5 (Sect 5.4 cursory only).

we calculate how many people must be present in order
for a shared birthday to be more likely than not
Assignment 8 due at 4pm.

26: Oct 22 (Mon)

Finish the introduction to probability theory, discussing

expected wait time until success

strategies for optimal hiring.
Introduce randomized algorithms:

motivation

how, and how not, to randomly permute an array

27: Oct 24 (Wed)


Randomized selection (Cormen: Section 9.2)

Randomized quicksort
(Cormen 7.34 or Howell 10.3)

Comparison of various sorting algorithms

Discuss the upcoming Assignment 9.

28: Oct 26 (Fri)


Hand back, and discuss, graded Assignment 8.

Give an upper bound for the expected random path length in
an arbitrary binary tree.

Mention "MonteCarlo" algorithms,
in particular for testing if a given number is a prime.

Further discuss Assignment 9.

29: Oct 29 (Mon)


Discuss Assignment 9 which was due at 10am.

Discuss previous exam questions (uploaded on KState Online).

30: Oct 31 (Wed)

Exam 2

31: Nov 2 (Fri)


Study decision trees, and establish a lower bound
for comparisonbased sorting algorithms,
cf. Cormen 8.1.

We exhibit sorting algorithms, in particular counting sort,
that run in linear time,
cf. Cormen 8.24.

32: Nov 5 (Mon)


We use "adversary arguments" to establish
lower bounds that are more precise than what
information theory would yield
(cf. Cormen 9.1 on finding minimum and maximum).

We embark on discussing what constitutes a really hard problem,
introducing the class P
and motivating the class NP.
Reading: Cormen 34.1 (or Howell 16.2).

33: Nov 7 (Wed)

We continue the discussion of tractability:

we formally define the class NP

we define the concept of polynomial manyone reduction

we introduce the class of NPhard (and NPcomplete) problems.
Reading: Cormen 34.23 (or Howell 16.3).

34: Nov 9 (Fri)

We present a number of NPhard problems,
and prove that they are indeed NPhard:

we reduce Clique to VertexCover;

we reduce 3Sat to Clique;

we sketch how to reduce from CSat to 3Sat.
Reading: Cormen Sections 34.45, except Sects. 34.5.3&5
(or Howell 16.45)
Assignment 10 due at 4pm.

35: Nov 12 (Mon)


Discuss and hand back graded Exam 2.

Wrap up the reductions showing NPhardness,
in particular sketch the reduction from Sat to CSat.

36: Nov 14 (Wed)


Hand back, and discuss, graded Assignment 10.

Discuss the reduction from 3Sat to 3Col in the upcoming Assignment 11.

Mention that optimization problems can often be reduced to
decision problems, and vice versa
(cf. Howell 17.1).

Sketch a hierarchy of complexity classes,
where in most cases it is unknown whether the inclusion is strict.

Introduction to Approximation Algorithms, cf.
Cormen Section 35.0.

37: Nov 16 (Fri)

Continue Approximation Algorithms, cf.
Cormen 35.1&2 and
Howell 17.2&4.

for some problems,
we can construct polynomial algorithms
that are guaranteed to approximate within a fixed factor (often two);

often, we can even get arbitrarily high precision
where each such approximation is polynomial
but with degree that depends on the precision;

in certain cases, like for the binary knapsack problem,
we can approximate within
an error of 1/k at a cost polynomial even in k.
Assignment 11 due Tuesday at 4pm.

Nov 1923 (MonFri)

Thanksgiving holiday

38: Nov 26 (Mon)


Finish the fully polynomial approximation scheme for
the binary knapsack problem.

Consider two
seemingly equivalent problems (Howell 17.5) where

one (MaxCut) can in polynomial time be
approximated within a fixed
relative error (but it is not clear how to further increase precision)

one (MinCluster) does not allow any polynomialtime
fixedprecision approximation algorithm
(unless P = NP).

Prove that for the general (no triangle inequality)
traveling salesman problem,
there exists no approximation algorithm (unless P = NP).

39: Nov 28 (Wed)

Discuss depthfirst traversal of graphs, directed as well
as undirected (Cormen 22.3 or Howell 13.13).

As a result, we can view a graph as a tree together with
certain kinds of extra edges.

See how depthfirst traversal can be augmented
into an algorithm for topological sort,
cf. Cormen 22.4 or Howell 13.5.

40: Nov 30 (Fri)

See more graph problems that can be solved by
algorithms that build on depthfirst traversal:

Illustrate topological sort by examples

Find "articulation points",
cf. Howell 13.4

Find "bridges",
cf. Assignment 12, Question 2.
Embark on Network Flow, cf. Cormen 26.1:

introduce key concepts

show that a naive algorithm doesn't always generate the maximal flow.

41: Dec 3 (Mon)

Continue Network Flow:

introduce the FordFulkerson method and the
EdmondsKarp optimization, cf.
Cormen 26.2 or Howell 14.12.

discuss Q3 in the upcoming Assignment 12.

42: Dec 5 (Wed)

Finish Network Flow:

Show how to use it for Maximum Bipartite Matching,
cf. Cormen 26.3 or Howell 14.3.

Show that the maximum flow equals the minimum cut,
cf. Cormen's Theorem 26.6.

Discuss Q3 in Assignment 12, due today at 4pm.
Discuss graded Assignment 11.

43: Dec 7 (Fri)

General review session.
 Discuss the recently submitted Assignment 12.
 Discuss the final exam from Fall'11.
 Discuss the final exam from Fall'10.

Dec 11 (Tue)

Final exam, 11:50am1:40pm
Torben Amtoft