# 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 top-down approach and then improve them by applying the bottom-up technique. Along the way, we give some simple complexity estimates.
Cormen Reading: Chapter 1 and Section 2.2.
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.
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.
4: Aug 27 (Mon)
• We develop a linear-time constant-space algorithm for the Dutch National Flag problem
• We introduce the "Big-O" symbol, useful for asymptotic analysis, and reason about its properties.
5: Aug 29 (Wed)
We continue the theory of asymptotic notation, and
• introduce "Big-Omega", "Big-Theta", "little-o", and "little-omega"
• 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 Big-O notation to more than one variable.
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
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.
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
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.1-2 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.1-2&6).
15: Sep 24 (Mon)
• Show how to use heaps for efficient and in-place 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 1-3 (or Howell Chapter 8, Sections 1-3)
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 all-pair shortest paths algorithm (Howell 12.3 or Cormen 25.2)
• chained matrix multiplcation (Howell 12.2 or Cormen 15.2)
Assignment 6 due at 5pm.
21: Oct 8 (Mon)
• Motivate Assignment 7, just posted.
• 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 minimum-cost 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 minimum-cost spanning tree
• Present Dijkstra's algorithm for single-source 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.3-4 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 "Monte-Carlo" 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 K-State Online).
30: Oct 31 (Wed)
Exam 2
31: Nov 2 (Fri)
• Study decision trees, and establish a lower bound for comparison-based sorting algorithms, cf. Cormen 8.1.
• We exhibit sorting algorithms, in particular counting sort, that run in linear time, cf. Cormen 8.2-4.
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 many-one reduction
• we introduce the class of NP-hard (and NP-complete) problems.
Reading: Cormen 34.2-3 (or Howell 16.3).
34: Nov 9 (Fri)
We present a number of NP-hard problems, and prove that they are indeed NP-hard:
• we reduce Clique to VertexCover;
• we reduce 3-Sat to Clique;
• we sketch how to reduce from CSat to 3-Sat.
Reading: Cormen Sections 34.4-5, except Sects. 34.5.3&5 (or Howell 16.4-5)
Assignment 10 due at 4pm.
35: Nov 12 (Mon)
• Discuss and hand back graded Exam 2.
• Wrap up the reductions showing NP-hardness, in particular sketch the reduction from Sat to CSat.
36: Nov 14 (Wed)
• Hand back, and discuss, graded Assignment 10.
• Discuss the reduction from 3-Sat to 3-Col 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 19-23 (Mon-Fri)
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 (Max-Cut) can in polynomial time be approximated within a fixed relative error (but it is not clear how to further increase precision)
• one (Min-Cluster) does not allow any polynomial-time fixed-precision 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 depth-first traversal of graphs, directed as well as undirected (Cormen 22.3 or Howell 13.1-3).
• As a result, we can view a graph as a tree together with certain kinds of extra edges.
• See how depth-first 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 depth-first 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 Ford-Fulkerson method and the Edmonds-Karp optimization, cf. Cormen 26.2 or Howell 14.1-2.
• 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.