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.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)

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 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