ECS 222A - Fall 2007 and Supplemental Lectures: Graduate Level Algorithm Design and Analysis - Gusfield

  • This page links to the course lectures and discussion sections. A list of the topics covered in each lecture can be found at Topics by date

    Lecture Videos

  • Webcast of the first lecture 9-28-07 A formal definition of worst-case running time of an algorithm; complexity rules of the game; assymptotic notation; Merge-Sort and its analysis by setting up and solving (finding a closed form solution) of a recurrence relation.

    Unfortunately, the first 10 minutes of the lecture are missing. See complexity, rules of the game for a written version of this part of the lecture, or see the next video for a more complete treatment.

  • Supplemental video Another lecture on the same topics as the lecture of 9-28-07: Complexity rules of the game, but more complete than the 9-28-07 lecture, both because it covers more and because the video is complete.

  • Supplemental video Solving a divide and conquer recurrence by unwrapping the recurrence to set up and solve a summation.

  • Supplemental video An O(n log n) time algorithm to find the lower-envelope of a set of lines. Another example of the use of recurrence relations to analyse the running time of the algorithm.

  • Supplemental video The famous and surprising result that the median of a set of n numbers can be found in O(n) time, i.e., without sorting the numbers. This is another example of a divide and conquer algorithm, and analysis of the running time by the use of recurrence relations.

  • 10-1-07
    Counting all the inversions in a permutation in O(n log n) time. Another divide and conquer algorithm, and example of the use of recurrence relations to analyse the running time. See Section 5.3 of the Kleinberg and Tardos text. We gave a more complete proof of correctness than in the book, proving explicitly that there was no double counting between levels of the recursion, and no over or under counting at a single level of the recursion. Unfortunately, the webcast of this lecture seems to have become corrupted.

    See Counting Inversions with divide and conquer for a lecture of this material given in an undergraduate class in 2010.

  • Webcast of 10-3-07 Finding the closest pair of points on the plane by divide and conquer. See Section 5.4 of Kleinberg and Tardos.

  • Supplemental Video Randomized Quicksort in O(n) expected time. Almost complete.

  • Supplemental Video Completion of the analysis of Randomized Quicksort in O(n) expected time.

  • Supplemental Video Strassen's famous fast matrix multiplication method.

  • Supplemental Video The Four Russian's method for bit matrix multiplication.

  • Supplemental Video An introduction to Information Theory Lower Bounds for binary decision trees, then specialized to the problem of sorting by using comparisons.

  • Supplemental Video Continuation of Information Theory Lower Bounds for binary decision trees; variations on the standard model.

  • Supplemental Video Introduction to Adversary Lower Bounds arguments, illustrated by the game of battleship. Then start of the adversary argument to establish the lower bound of 1.5n comparisons needed for finding the median of n numbers.

  • Supplemental Video Continuation and completion of the adversary argument to establish the lower bound of 1.5n comparisons needed for finding the median of n numbers. Final comments on lower bounds.

  • Webcast of 10-5-07 Unweighted interval scheduling by a greedy algorithm. Weighted interval scheduling by dynamic programming.

  • Webcast of 10-8-07 Traceback for weighted interval scheduling. Weighted sequence alignment and weighted edit distance by DP.

  • Webcast of 10-10-07 Shortest path algorithms.

  • Webcast of 10-12-07 Network flow. The start of the Ford-Fulkerson algorithm.

  • Webcast of 10-15-07 Network flow. Continuation of the Ford-Fulkerson algorithm. The Max-Flow Min-Cut Theorem.

  • Webcast of 10-17-07 Proof of the Max-Flow Min-Cut Theorem for integer capacities, based on the FF algorithm. Bipartite matching. Start of the Preflow-Push algorithm.

  • Webcast of 10-19-07 Continuation of the Preflow-Push algorithm. Proof that if f is a preflow and h is a compatible node labeling, then there is no s-t path in the augmentation graph Gf defined from f. Details of the Preflow-Push algorithm.

  • Webcast of 10-22-07 Time analysis of the Preflow-Push algorithm. Bounding the number of relabels and saturating pushes

  • Webcast of 10-24-07 Finish of the time alanysis for preflow-push. Bounding the number of non-saturating pushes. Reducing the time bound by picking the node with maximum height among the nodes with excess.

  • Webcast of 10-29-07 Use of network flow in end of the season elimination problems. Extension to other scoring systems beyond baseball.

  • Webcast of 10-31-07 Introduction to Reductions and the classes P and NP

  • Webcast of 11-2-07 NP, NP-Completeness, co-NP

  • Webcast of 11-5-07 Continutation of NP, NP-Completeness, co-NP

  • Webcast of 11-7-07 Dealing with NP-hard problems: special cases - Greedy, yet optimal Node Cover on a tree, Weighted node cover via DP on a tree.

  • Webcast of 11-9-07 Fixed parameter tractability: weighted node cover when there are at most k nodes in the node cover.

  • Webcast of 11-14-07 Bounded error approximation bounds: unweighted node cover via maximal matching; Steiner string problem.

  • Webcast of 11-16-07 Approximation algorithms: Steiner string problem. Disjoint paths in a graph.

  • Webcast of 11-19-07 Disjoint paths in a graph. Non-approximability of the Travelling Salesman Problem.

  • Webcast of 11-21-07 Linear-time String Matching: The Z-algorithm.

  • Suffix Array Linear-time algorithm to build a suffix array for a string S.

  • Computing the LCP array Linear-time algorithm to find the Longest Common Prefix (LCP) values. The LCP values, along with the suffix array allow the linear-time computation of many string tasks and solution of string problems. For example, with the suffix array and the LCP array for a string S, the suffix tree for S can be found in linear time.

  • Webcast of 11-26-07 A Deterministic algorithm for global minimum cut in an undirected graph without using network flow. This algorithm is not discussed in the book, but a randomized algorithm for the problem is discussed.

  • Webcast of 11-28-07 Randomized Global Min-Cut

  • Webcast of 11-30-07 Constant-Time Least Common Ancestor algorithm - almost completed.

  • Webcast of 12-3-07 Constant-Time Least Common Ancestor algorithm - finished, Introduction to Tree Decomposition.

  • Webcast of 12-5-07 Hashing - guest lecture by Chip Martel

  • Webcast of 12-7-07 Tree Decomposition and Tree Width.
    Oops, at the end of the lecture (the end of the course) things got a bit rushed and I wrote that the DP for independent set for graph G runs in time that is polynomial in w(T) and n and m, where w(T) is the width of the tree decomposition T, and n and m are the number of nodes and edges in the graph G. What is correct is that the DP runs in time that is exponential in w(T) (in fact it contributes a factor of 4^{w(T)}), and polynomial in n and m. The actual running time is something like O(4^{w(T)}nm). The point is that if w(T) is bounded, independent of n and m, then 4^{w(T)} is just a constant number, so independent set problem can be solved in polynomial time as a function of n and m (again if w(T) is bounded independent of n and m). Similarly, even if w(T) is not bounded, if it is small, then the running time is practical for realistic n and m. The smaller w(T) is, the more tree-like is the graph, and the faster the DP. I think I also said something wrong about the approximation bound.

  • Supplimental Lecture: Computing a Minimum Cost Arborescence

  • Webcast of 12-11-07 Seems to be missing

  • webcast of discussion Oct. 10, 2007
  • webcast of discussion Oct. 17, 2007
  • webcast of discussion Oct. 24, 2007
  • webcast of discussion Oct. 31, 2007
  • webcast of discussion Nov. 7, 2007
  • webcast of discussion Nov. 14, 2007
  • There are no webcasts of discussions between Nov. 14 and Dec. 5, although the videos of those are available.
  • webcast of Discussion Dec. 5, 2007