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

1: January 20 (Wednesday)
• go through syllabus
• emphasize that the task of an algorithm is to implement a specification
• specify the sorting and the selection problems.
2: January 22 (Friday)
Using the insertion sort method (Cormen Sections 2.1-2.2) as example, we
• illustrate how to design algorithms by the top-down approach
• show how to improve the implementation by applying the bottom-up technique
• give some simple complexity estimates.
Embark on how to prove the correctness of algorithms:
• for recursive algorithms, this requires induction, cf. Section 2.2 in Howell.
3: January 25 (Monday)
We address, and illustrate on examples, how to prove the correctness of
• recursive algorithms (continued from last time)
• iterative algorithms (this requires a loop invariant), cf. Cormen p.19 or Howell Sect 2.3.
Discuss the upcoming Assignment 1.
4: January 27 (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.
• Motivate the theory of asymptotic notation.
• Further discuss Assignment 1, due tomorrow night.
5: January 29 (Friday)
We introduce the theory of asymptotic notation, cf. Cormen Chapter 3 or Howell Sections 3.1-3.3, and
• introduce the "Big-O" symbol
• reason about the properties of Big-O
• introduce "Big-Omega" and "Big-Theta" while distinguishing between "best-case" and "worst-case" interpretation (cf. Cormen p.49).
Motivate the upcoming Assignment 2 (this web site may come handy).
February 1 (Monday)
Class canceled (instructor out of town).
6: February 3 (Wednesday)
• Finish the theory of asymptotic notation, by introducing "little-o" (and "little-omega").
• 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.
• We address (as in Howell 3.4-6) the complexity of iterative algorithms where we need to estimate sums; the "rectangle" is
• trivially an upper approximation
• in our initial example, also a lower approximation, modulo a constant factor.
Assignment 2 due tomorrow night.
7: February 5 (Friday)
Motivate, state and illustrate a general result (Theorem 3.28 in Howell) that is often useful for estimating sums found in the analysis of iterative programs:
• the "rectangle" is even a lower approximation (modulo a constant factor) provided that the function is smooth.
8: February 8 (Monday)
Mention various pitfalls in algorithm analysis:
• it may be that not all iterations can exhibit worst-case behavior
• numbers may become so big that they cannot realistically be handled in constant time.
Wrap up the discussion of iterative algorithms:
• motivate the upcoming Assignment 3.
• they show up when analyzing divide and conquer algorithms (cf Cormen Section 2.3).
Last day for 100% refund
9: February 10 (Wednesday)
We address how to solve recurrences:
• to check a proposed solution, the substitution method can be used (cf Cormen Section 4.3):
• one kind of example is straightforward
• for another kind of example, the presence of logarithms requires a careful phrasing of the induction hypothesis
Assignment 3 due tomorrow night.
10: February 12 (Friday)
• Wrap up the substitution method:
• for a third kind of example, one needs some creativity to phrase the induction hypothesis
• Briefly introduce a general recipe, the "Master Theorem", for solving recurrences.
11: February 15 (Monday)
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.
12: February 17 (Wednesday)
Elaborate on the Master Theorem:
• we show how recurrences can sometimes be twisted, by "change of variables" (cf. p.86 in Cormen), to fit the Master Theorem template
• we give an example where Howell's Theorem 3.32 (or Wikipedia) gives better precision than the Master Theorem from the slides (whereas Cormen's version gives nothing)
Assignment 4 due tomorrow night.
13: February 19 (Friday)
Introduce the "Dutch National Flag" problem, cf. Section 2.4 in Howell:
• argue it is useful in a number of contexts
• develop a linear-time constant-space algorithm.
14: February 22 (Monday)
Review session for the upcoming midterm exam:
• discuss relevant exam questions from 2015 (uploaded on K-State Online)
15: February 24 (Wednesday)
Exam I.
16: February 26 (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: February 29 (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 2 (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 in-place sorting algorithm, heap sort (Cormen 6.4).
Further discuss Assignment 5, due tomorrow night.
19: March 4 (Friday)
Introduce union/find structures (cf Cormen Chapter 21, Sections 1-3):
• they are useful for representing equivalence classes
• we can implement the operations so that we can prove they run in time O(lg(n))
March 7 (Monday)
Class canceled (instructor not well)
20: March 9 (Wednesday)
• Hand back, and discuss, graded Exam 1.
• Discuss Assignment 6, due tomorrow night.
21: March 11 (Friday)
• discuss (not yet graded) Assignment 6.
• Introduce Ackermann's function which quickly assumes exorbitant values;
• mention that one can implement union/find such that the
"amortized" (average) cost per operation is the inverse Ackermann function, that is almost in O(1).
March 14-18
Spring break.
22: March 21 (Monday)
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.
Motivate, and discuss in detail, the upcoming Assignment 7.
23: March 23 (Wednesday)
We see some clever applications of the Divide & Conquer paradigm:
• after recalling from primary school how to multiply big numbers given that we know how to multiply small numbers,
we show how to multiply n-bit 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).
Further discuss Assignment 7, due tomorrow night.
24: March 25 (Good 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).
Motivate Assignment 8.
25: March 28 (Monday)
Continue dynamic programming:
• apply it to the binary knapsack problem (Howell 12.4),
given as Exercise 16.2-2 in Cormen and with solution listed on page 50 here;
• further discuss the upcoming Assignment 8, illustrated by a simple example.
26: March 30 (Wednesday)
Continue Dynamic Programming:
• Present Floyd's all-pair shortest paths algorithm (Cormen 25.2)
• mention that a subpart of an optimal solution is not necessarily an optimal solution to the subproblem.
• Further discuss Assignment 8, due tomorrow night.
27: April 1 (Friday)
One more application of the Divide and Conquer paradigm:
• the selection problem which has a clever (deterministic) solution that always runs in linear time (Cormen Section 9.3).
Motivate the chained matrix multiplication problem (Cormen 15.2).
April 4-8 (Monday-Friday)
Classes canceled (instructor out of town).
28: April 11 (Monday)
Review session for the upcoming midterm exam:
• Discuss relevant exam questions from 2015 (uploaded on K-State Online)
• Discuss model solutions for Assignments 7 and 8.
29: April 13 (Wednesday)
Exam II.
April 15 (Friday)
Class canceled (All-University Open House)
30: April 18 (Monday)
We embark on greedy algorithms, the topic of Cormen 16:
• motivate the concept
• show a greedy strategy for minimizing total waiting time for jobs with duration
• discuss how to extend the above strategy when jobs have priorities, as in the upcoming Assignment 9
• show a greedy strategy for the fractional knapsack problem (cf. Cormen Exercise 16.2-1).
31: April 20 (Wednesday)
We address how to construct a minimum-cost spanning tree, cf. Cormen 23:
• present and illustrate Kruskal's algorithm, and analyze its complexity, cf. Cormen 23.2
Discuss and hand back graded Exam 2.
Assignment 9 due tomorrow night.
32: April 22 (Friday)
Introduce depth-first traversal of graphs, directed as well as undirected (Cormen 22.3):
• show how to compute a spanning tree;
• show that we can view a graph as a rooted tree together with certain kinds of extra edges (back, forward, cross);
• show how to augment the depth-first algorithm to do topological sort, cf. Cormen 22.4.
Motivate Question 2 in the upcoming Assignment 10.
33: April 25 (Monday)
Continue algorithms based on depth-first traversal:
• show how to find "articulation points", cf. Cormen Problem 22-2
• motivate the notion of "bridges", cf Question 1 in the upcoming Assignment 10.
34: April 27 (Wednesday)
Continue the construction of minimum-cost spanning trees:
• present and illustrate Prim's algorithm, and analyze its complexity, cf. Cormen 23.2
• briefly mention a general correctness proof, cf. Cormen Theorem 23.1.
Continue the detection of shortest paths:
• present Dijkstra's algorithm for single-source shortest paths, cf. Cormen 24.3 (illustrated by Fig 24.6 there)
• discuss how to use Dijkstra's algorithm, and Floyd's, to find shortest paths for single/multiple sources and single/multiple destinations.
Assignment 10 due tomorrow night.
35: April 29 (Friday)
Embark on Network Flow, cf. Cormen 26.1-3:
• introduce key concepts, cf. Cormen 26.1
• show that a naive algorithm doesn't always generate the maximal flow
• hence motivate the Ford-Fulkerson method, cf. Cormen 26.2, which
• uses the concept of residual networks
• can be optimized by the Edmonds-Karp algorithm.
36: May 2 (Monday)
Continue and finish Network Flow:
• show how to use the Ford-Fulkerson method for Maximum Bipartite Matching, cf. Cormen 26.3
• introduce the notion of a cut in a flow network
• show that the maximum flow equals the minimum cut, cf. Cormen's Theorem 26.6.
37: May 4 (Wednesday)
Wrap up Greedy Algorithms:
• schedule events with fixed start/end time, cf. Cormen 16.1
• introduce Huffman codes, cf. Cormen 16.3.
Discuss graded Assignments 9 & 10.
Assignment 11 due tomorrow night.
38: May 6 (Friday)
Prepare for final exam:
• discuss model solutions for Assignment 11
• discuss relevant questions from the 2015 final exam
• briefly discuss questions from the 2014 final exam.
May 9 (Monday)
Final exam, 4:10-6:00pm

Torben Amtoft