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

1: January 21 (Wednesday)


go through syllabus

emphasize that the task of an algorithm is to
implement a specification

specify the sorting and the selection problems.
Cormen reading: Chapter 1.

2: January 23 (Friday)

Using the insertion sort method
(Cormen Sections 2.12.2)
as example, we

illustrate how to design algorithms by the topdown
approach

show how to improve the implementation
by applying the bottomup technique

give some simple complexity estimates.
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

a recursive algorithm (this requires induction),
cf. Section 2.2
in Howell

an iterative algorithm (this requires a loop invariant),
cf. Cormen p.19 or Howell Sect 2.3.

4: January 28 (Wednesday)


Do the correctness proof of iterative insertion sort,
where for the inner loop
it is not obvious how to find an invariant that is strong enough.

Discuss Assignment 1, due tomorrow night.

Motivate the theory of asymptotic notation.

5: January 30 (Friday)

We introduce the theory of asymptotic notation, cf. Cormen
Chapter 3 or Howell Sections 3.13.3, and

introduce the "BigO" symbol

reason about the properties of BigO

introduce "BigOmega"
while distinguishing between
"bestcase" and "worstcase" interpretation
(cf. Cormen p.49).

6: February 2 (Monday)


Finish the theory of asymptotic notation,
by introducing
"BigTheta"
and "littleo" and
"littleomega".

Discuss the upcoming Assignment 2
(where this web site
may come handy).

February 4 (Wednesday)

Class canceled (instructor out of town).
Assignment 2 due tomorrow night.

7: February 6 (Friday)

We address (as in Howell 3.46) the complexity of iterative algorithms
where we need to estimate sums; the "rectangle" is

trivially an upper approximation

also a lower approximation, modulo a constant factor,
provided that the function is smooth.
Also introduce the notion of a "barometer instruction"

which is executed at least as frequently as any other instruction
and therefore may serve to easily estimate running time.
Discuss model solutions for Assignment 2 (uploaded on KState Online).

8: February 9 (Monday)


Further discuss selected parts of Assignment 2
(which had caused more problems than expected)

Discuss model solutions for Assignment 1 (recently graded)

State a general result (Theorem 3.28 in Howell)
that is often useful for estimating sums found in the
analysis of iterative programs

Discuss the upcoming Assignment 3.
Last day for 100% refund.

9: February 11 (Wednesday)

Mention various pitfalls in algorithm analysis:

it may be that not all iterations can exhibit worstcase behavior

numbers may become so big that they cannot realistically
be handled in constant time.
Wrap up the complexity of iterative algorithms:

illustrate by further examples

further discuss Assignment 3, due tomorrow night.

10: February 13 (Friday)

Address general recurrences:

they show up when
analyzing divide and conquer algorithms
(cf Cormen Section 2.3);

to check a proposed solution,
the substitution method can be used
(cf Cormen Section 4.3),
as illustrated by two examples.

11: February 16 (Monday)


Give one more example (trickier than the previous two)
of the substitution method.

Present a general recipe,
the "Master Theorem",
for solving recurrences:

we give a (very) informal proof

we illustrate by several examples

Cormen reading: Sections 4.4 & 4.5.

Discuss the upcoming Assignment 4.

12: February 18 (Wednesday)

Elaborate on the Master Theorem:

we show how recurrences can sometimes be twisted, by "change
of variables", to fit the Master Theorem template

we give an example where
Howell's Theorem 3.32 gives better precision
than the Master Theorem from the slides.
Introduce the "Dutch National Flag" problem,
cf. Section 2.4 in Howell:

argue it is useful in a number of contexts.
Further discuss Assignment 4, due tomorrow night.

13: February 20 (Friday)


Develop a lineartime constantspace algorithm
for the Dutch National Flag problem.

Discuss model solutions for Assignments 3 & 4.

14: February 23 (Monday)

Review session for the upcoming midterm exam:

Discuss relevant exam questions
from 2013 and 2014 (uploaded on KState Online)

15: February 25 (Wednesday)

Exam I.

16: February 27 (Friday)

Introduce graphs, cf Cormen Appendix B.4, which

are either directed or undirected

may be acyclic and/or connected

may be represented by an adjacency matrix or by adjacency lists,
cf Cormen 22.1.
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:

define the heap property

show how to maintain the heap property (Cormen 6.2)

use heaps to implement priority queues (Cormen 6.5).
Motivate and discuss the upcoming Assignment 5.

18: March 4 (Wednesday)

Conclude the treatment of heaps:

show an efficient representation (Cormen 6.1)

show how to convert an array into a heap (Cormen 6.3)

so as to develop an efficient and inplace sorting
algorithm, heap sort (Cormen 6.4).
Further discuss (Question 3 in) Assignment 5, due tomorrow night.

19: March 6 (Friday)


Motivate the upcoming Assignment 6.

Argue that (comparisonbased) sorting cannot be done
better than Theta(n!) = Theta(n lg(n)).

We introduce union/find structures
(cf Cormen Chapter 21, Sections 13)
that are useful for representing equivalence classes.

20: March 9 (Monday)


Discuss and hand back graded Exam 1.

Conclude union/find structures:

we can implement the operations so that we can prove they run in time O(lg(n))

it is possible to obtain an "amortized" (average)
cost per operation
which is almost in O(1).

Further discuss the upcoming Assignment 6.

21: March 11 (Wednesday)

Explore the Divide and Conquer paradigm,
already motivated by merge sort (Cormen Section 2.3)
and with further examples:

quicksort (Cormen Section 7.1) where the key part to
good performance (Cormen Section 7.2)
is to properly design pivot selection;

we recall from primary school how to multiply big numbers
given that we know how to multiply small numbers.
Assignment 6 due tomorrow night.

22: March 13 (Friday)

Continue exploring the Divide & Conquer paradigm:
we see clever applications that allow

multiplication of nbit integers
(or polynomials of degree n, cf Howell Section 10.1)
in time O(n^b) where b is less than 2 (and may actually be arbitrarily
close to 1);

multiplication of n x n matrices in time
O(n^b) where b is much less than 3
(Cormen Section 4.2).
Mention the quests to

improve the complexity of multiplying large matrices

improve the upper bound for the number of flips necessary
to solve the "pancake problem".

March 1620

Spring break.

23: March 23 (Monday)


Discuss model solutions for Assignments 5 and 6 (recently graded).

Motivate and discuss the upcoming Assignment 7.

24: March 25 (Wednesday)

One more application of the Divide and Conquer paradigm:

the selection problem
which has a clever solution that
always runs in linear time
(Cormen Section 9.3).
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:

motivate by examples of how to avoid duplicated computations

show how to apply it to the problem of giving optimal change
(cf. Howell 12.1).

26: March 30 (Monday)

Continue dynamic programming:

apply it to the binary knapsack problem
(Howell 12.4),
given as Exercise 16.22 in Cormen
and with solution listed on page 50
here

discuss the upcoming Assignment 8.

27: April 1 (Wednesday)

Continue Dynamic Programming:

Present Floyd's allpair shortest paths
algorithm (Cormen 25.2)

Further discuss Assignment 8, due tomorrow night.

28: April 3 (Good Friday)

Review session for the upcoming midterm exam:

Discuss model solutions for Assignments 7 and 8

Discuss relevant exam questions
from 2013 and 2014 (uploaded on KState Online)

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 (AllUniversity Open House)

30: April 13 (Monday)

We embark on greedy algorithms,
the topic of Cormen 16:

motivate the concept

show a greedy strategy for minimizing total waiting time

show a greedy strategy for
the fractional knapsack problem
(cf. Cormen Exercise 16.21).

31: April 15 (Wednesday)

Present algorithms for constructing a
minimumcost spanning tree, cf.
Cormen 23:

present and illustrate Kruskal's algorithm,
and analyze its complexity,
cf. Cormen 23.2

sketch a correctness proof, cf. Cormen Theorem 23.1

present and illustrate Prim's algorithm, and analyze its complexity,
cf. Cormen 23.2

32: April 17 (Friday)


Discuss and hand back graded Exam 2.

Present Dijkstra's algorithm for singlesource shortest paths,
cf. Cormen 24.3 (illustrated by Fig 24.6 there)

33: April 20 (Monday)


Discuss how to use Dijkstra's algorithm (and Floyd's)
to find shortest paths for single/multiple sources
and single/multiple destinations.

Discuss various greedy strategies, some correct and some not,
for scheduling of events with fixed start/end time,
cf. Cormen 16.1.

Discuss the upcoming Assignment 9.

34: April 22 (Wednesday)

Wrap up Greedy Algorithms:

introduce Huffman codes, cf. Cormen 16.3.
Introduce depthfirst traversal of graphs (Cormen 22.3)

show how to compute a spanning tree.
Assignment 9 due tomorrow night.

35: April 24 (Friday)

Continue depthfirst traversal of graphs, directed as well
as undirected (Cormen 22.3);

we can view a graph as a rooted tree together with
certain kinds of extra edges (back, forward, cross);

show how to augment the depthfirst algorithm
to do topological sort, cf. Cormen 22.4.
Motivate Question 2 in the upcoming Assignment 10.

36: April 27 (Monday)

Continue algorithms based on depthfirst traversal:

illustrate the topological sort algorithm developed last time

show how to find
"articulation points",
cf. Cormen Problem 222

motivate the notion of "bridges", cf
Question 1 in the upcoming Assignment 10.

37: April 29 (Wednesday)

Embark on Network Flow, cf. Cormen 26.13:

introduce key concepts, cf. Cormen 26.1

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

hence motivate the concept of residual networks,
cf. Cormen 26.2
Further discuss Assignment 10, due tomorrow night.

38: May 1 (Friday)

Elaborate on the FordFulkerson method,
motivated last time and described in Cormen 26.2:

introduce the EdmondsKarp optimization
(cf. Cormen 26.2)

show how to use the FordFulkerson method for
Maximum Bipartite Matching,
cf. Cormen 26.3

briefly introduce the notion of a cut
in a flow network.
Discuss model solutions for (graded) Assignment 9.

39: May 4 (Monday)

Finish Network Flow:

show that the maximum flow equals the minimum cut,
cf. Cormen's Theorem 26.6.
Wrap up Dynamic Programming:

find optimal solution for chained matrix multiplication (Cormen 15.2)
Motivate the upcoming Assignment 11.

40: May 6 (Wednesday)

Wrap up Dynamic Programming:

find the complexity of computing the optimal solution
(presented last time)
for chained matrix multiplication

mention that a subpart of an optimal solution
is not necessarily an optimal solution to the subproblem.
Prepare for final exam:

discuss relevant exam questions from 2013.
Assignment 11 due tomorrow night.

41: May 8 (Friday)

Prepare for final exam:

discuss model solutions for Assignments 10 & 11

discuss relevant exam questions from 2014.

May 15 (Friday)

Final exam, 4:106:00pm
Torben Amtoft