Captain's Log: CIS 775, Analysis of Algorithms, Fall 2010

1: Aug 23 (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 25 (Wed)

We address how to prove the correctness of an algorithm, recursive or iterative, and illustrate the techniques on various implementations of insertion sort.
Cormen Reading: Section 2.1.

3: Aug 27 (Fri)

• We finish the correctness proof of iterative insertion sort, realizing the need to strengthen the invariant.
• We introduce the "Dutch National Flag" problem, useful in a number of contexts, and develop a linear-time constant-space algorithm for it.

4: Aug 30 (Mon)

We introduce the "Big-O" symbol, useful for asymptotic analysis, and reason about its properties.
Cormen Reading: Chapter 3.

5: Sep 1 (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

HW1 due tomorrow at 5pm

6: Sep 3 (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 6 (Mon)

University Holiday (Labor Day)

7: Sep 8 (Wed)

We introduce amortized analysis, and apply it to expandable arrays.
Cormen Reading: Chapter 17.
HW2 due tomorrow at 5pm

8: Sep 10 (Fri)

We discuss how to give tight bounds for iterative algorithms, using the concept of smooth functions.

9: Sep 13 (Mon)

We embark on solving general recurrences, as show up when analyzing divide and conquer algorithms.
Graded HW1 back; discuss solutions.
Cormen Reading: Section 2.3 & Sections 4.3-4.4.

10: Sep 15 (Wed)

We motivate the Master Theorem (Thm 4.1 in Cormen), give examples of how to apply it, and outline a proof.
Cormen Reading: Section 4.5. (Optional: Section 4.6.1)
HW3 due tomorrow at 5pm

11: Sep 17 (Fri)

We discuss the Master Theorem, looking at applications and twists:

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

Graded HW2 back; discuss solutions.

12: Sep 20 (Mon)

We introduce the heap data structure, useful to

• implement priority queues
• do efficient and in-place sorting (as we shall see next time).

Cormen Reading: Chapter 6.

13: Sep 22 (Wed)

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).
Cormen Reading: Sections 21.1-3.
HW4 due tomorrow at 5pm

14: Sep 24 (Fri)

• Briefly cover possible graph representations, and virtual array initialization.
• We embark on a detailed study of the divide and conquer paradigm, with quicksort an important application.

Cormen Reading: Sections 7.1-2.

15: Sep 27 (Mon)

We continue applications of the divide & conquer paradigm:

• multiplication of large integers (or polynomials)
• matrix multiplication

Cormen Reading: Section 4.2

16: Sep 29 (Wed)

• We present an algorithm for the selection problem which, by clever divide & conquer, always runs in linear time.
• We discuss Question 4 in the upcoming HW5.
• Graded HW3 back; discuss Question 1.

Cormen Reading: Section 9.3.

17: Oct 1 (Fri)

• Briefly discuss Questions 2-4 in HW3.
• Graded HW4 back; discuss solutions.
• Discuss the upcoming HW5, in particular Question 5.

18: Oct 4 (Mon)

HW5 due today at 11am

• Discuss solutions to HW5.
• Discuss last year's Exam1.

19: Oct 6 (Wed)

Exam 1

20: Oct 8 (Fri)

• By examples, we illustrate key concepts of probability theory

Cormen Reading: Chapter 5 (Sect 5.4 cursory only).

21: Oct 11 (Mon)

We introduce randomized algorithms.

• How, and how not, to randomly permute an array
• Randomized selection
• Discuss the upcoming HW6.

Cormen Reading: Section 9.2.

22: Oct 13 (Wed)

• Randomized quicksort
• Comparison of various sorting algorithms
• Upper bound for expected path length
• Continue discussing the upcoming HW6

Cormen Reading: Sections 7.3-4.
HW6 due tomorrow at 5pm

23: Oct 15 (Fri)

• We mention "Monte-Carlo" algorithms, in particular for testing if a given number is a prime.
• We study decision trees, and establishes a lower bound for comparison-based sorting algorithms.

Cormen Reading: Section 8.1.

24: Oct 18 (Mon)

• We use "adversary arguments" to establish lower bounds that are more precise than what information theory would yield.
• Graded Exam 1 back; discuss solutions and grading policies.

25: Oct 20 (Wed)

• We exhibit sorting algorithms, in particular counting sort, that run in linear time.
• Graded HW5 back; discuss solutions

Cormen Reading: Sections 8.2 - 8.4.
HW7 due tomorrow at 5pm

26: Oct 22 (Fri)

• We embark on greedy algorithms, motivating the concept and giving several examples.
• Graded HW6 back; discuss solutions

Cormen Reading: Sections 16.1 - 16.2.

27: Oct 25 (Mon)

We continue greedy algorithms:

• max-profit scheduling
• min-cost spanning tree, presenting Kruskal's algorithm

Cormen Reading: Chapter 23.

28: Oct 27 (Wed)

We continue the presentation of greedy algorithms, covering:

• The correctness proof for Kruskal's algorithm
• Prim's algorithm (with correctness proof much as for Kruskal's but with different complexity)
• Dijkstra's algorithm for single-source shortest paths

Cormen Reading: Section 24.3.

29: Oct 29 (Fri)

• Revisit the complexity of Prim's algorithm.
• Wrap up greedy algorithms with one more scheduling problem.
• Introduce dynamic programming, showing that it can be used to efficiently compute "optimal change" even when the coin set does not permit a greedy solution.
• Discuss Question 1 in the upcoming HW8.

30: Nov 1 (Mon)

HW8 due at 11am

• Graded HW7 back; discuss solutions
• Discuss solutions to HW8

31: Nov 3 (Wed)

Exam 2

32: Nov 5 (Fri)

We see several applications of dynamic programming:

• giving optimal change
• binary knapsack problem
• all-pair shortest paths (we didn't finish)

Cormen Reading: Sections 15.1 & 15.3.

33: Nov 8 (Mon)

More applications of dynamic programming:

• Floyd's all-pair shortest path algorithm (continued from last time)
• chained matrix multiplcation

Cormen Reading: Sections 15.2 and 25.2.

34: Nov 10 (Wed)

We embark on discussing what constitutes a really hard problem, and introduce

• the sets P and NP;
• the concept of polynomial many-one reduction;
• and the class of NP-hard problems.

Cormen Reading: Sections 34.1-3.
HW9 due tomorrow at 5pm

35: Nov 12 (Fri)

Present a number of NP-hard problems, among which we

• reduce Clique to VertexCover (so as to establish that the latter is NP-hard provided the former is).

Cormen Reading: Sections 34.4-5 (except Sects. 34.5.3&5).

36: Nov 15 (Mon)

Recall various NP-complete problems and how to prove that they are indeed NP-hard:

• we reduce 3-Sat to Clique;
• we sketch how to reduce from CSat to 3-Sat, and from Sat to CSat.

Discuss solutions to HW9.

37: Nov 17 (Wed)

• Discuss depth-first traversal of graphs, directed as well as undirected.
• Illustrate that many graph problems can be solved by algorithms that build on depth-first traversal.

Cormen Reading: Sections 22.3-4.
HW10 due tomorrow at 5pm

38: Nov 19 (Fri)

One more application of depth-first search:

• finding articulation points.

Introduction to Approximation Algorithms:

• we consider problems for which an exact polynomial solution would imply that P = NP;
• in some situations, we can construct polynomial algorithms that are guaranteed to approximate within a factor two;
• often, we can even get arbitrary high precision yet each such approximation is polynomial (but with degree that depends on the precision).

Cormen Reading: Sections 35.0 and 35.2.

Nov 22-26 (Mon-Fri)

Thanksgiving holiday

39: Nov 29 (Mon)

• Discuss the upcoming HW11.
• Graded Exam 2 back; discuss solutions.
• Continue Approximation Algorithms, and show:
  • for the binary knapsack problem, we can approximate within an error of 1/k at a cost polynomial even in k.

40: Dec 1 (Wed)

• Finish Approximation Algorithms:
  • some problems (like binary knapsack) can in polynomial time be approximated arbitrarily well
  • some problems (like Max-Cut) can in polynomial time be approximated within a fixed relative error but it is not clear how to further increase precision
  • some problems (like Min-Cluster) do not allow any polynomial-time fixed-precision approximation algorithm (unless P = NP).
• Discuss solutions to HW10
• Graded HW8&9&10 back

HW11 due tomorrow at 11am

41: Dec 3 (Fri)

Exam 3