# 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.
2: January 23 (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.
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.1-3.3, and
• introduce the "Big-O" symbol
• reason about the properties of Big-O
• introduce "Big-Omega" while distinguishing between "best-case" and "worst-case" interpretation (cf. Cormen p.49).
6: February 2 (Monday)
• Finish the theory of asymptotic notation, by introducing "Big-Theta" and "little-o" and "little-omega".
• 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.4-6) 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 K-State 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 worst-case 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)
• 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 linear-time constant-space 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 K-State 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 in-place 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 (comparison-based) sorting cannot be done better than Theta(n!) = Theta(n lg(n)).
• We introduce union/find structures (cf Cormen Chapter 21, Sections 1-3) 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 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).
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 16-20
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.2-2 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 all-pair 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 K-State 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 (All-University 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.2-1).
31: April 15 (Wednesday)
Present algorithms for constructing a minimum-cost 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 single-source 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 depth-first traversal of graphs (Cormen 22.3)
• show how to compute a spanning tree.
Assignment 9 due tomorrow night.
35: April 24 (Friday)
Continue depth-first 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 depth-first 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 depth-first traversal:
• illustrate the topological sort algorithm developed last time
• show how to find "articulation points", cf. Cormen Problem 22-2
• motivate the notion of "bridges", cf Question 1 in the upcoming Assignment 10.
37: April 29 (Wednesday)
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 concept of residual networks, cf. Cormen 26.2
Further discuss Assignment 10, due tomorrow night.
38: May 1 (Friday)
Elaborate on the Ford-Fulkerson method, motivated last time and described in Cormen 26.2:
• introduce the Edmonds-Karp optimization (cf. Cormen 26.2)
• show how to use the Ford-Fulkerson 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:10-6:00pm

Torben Amtoft