Algorithm Design and Analysis

Introduction to the videos Sep 23, 2010

This video shows the URL for printed material that accompanies the course, and a URL for more advanced lectures on material that overlaps and extends the course. The URL for printed course material is: www.cs.ucdavis.edu/~gusfield/itunesU The URL for more advanced lectures is: www.cs.ucdavis.edu/~gusfield/cs222f07/videolist.html

Introduction to the course and algorithm complexity Sep 24, 2010

This is the course introduction about algorithm complexity, including what "worst case running time" means and how it is measured.

Big-Oh, Omega and Theta notation Sep 27, 2010

In Lecture 2, Gusfield discusses Big-Oh, Omega and Theta notation. He describes Mergesort and Merge and the start of their time analysis.

Time analysis of Mergesort Sep 29, 2010

In Lecture 3, Gusfield gives the worst-case analysis of MergeSort by setting up a recurrence relation and solving it by unwrapping.

A more complex recurrence relation and counting inversions Oct 01, 2010

In Lecture 4, students learn about solving a more complex recurrence relation by unwrapping. Gusfield also addresses the problem of counting inversions in a permutation.

Counting inversions; Fast integer multiplication Oct 04, 2010

Lecture 5: Gusfield lectures about counting the number of inversions in a permutation. He introduces fast integer multiplication by divide and conquer.

Fast integer multiplication, randomized selection and median finding Oct 06, 2010

In Lecture 6, Gusfield finishes the discussion of integer multiplication by divide and conquer. He then starts randomized selection and median finding.

More on randomized selection and median finding Oct 08, 2010

During Lecture 7, students learn more on randomized selection and median finding: algorithm and start of analysis.

Expected number of comparisons in randomized select Oct 11, 2010

In Lecture 8, Gusfield completes his analysis of the expected number of comparisons in randomized version of Select(S,k) as a function of |S|. The expected number is at most 8|S|.

Greedy algorithms: Picking largest set of non-overlapping intervals Oct 13, 2010

For Lecture 9, Gusfield starts discussion of greedy algorithms: Picking the largest number of non-overlapping intervals on a line.

Greedy algorithms: The classroom scheduling problem Oct 14, 2010

In Lecture 9A, Gusfield provides another scheduling problem to be solved by a greedy algorithm.

Dijkstra's shortest path algorithm Oct 15, 2010

In Lecture 10, students learn about Dijkstra's algorithm for shortest paths in a graph with non-negative edge weights.

Start of minimum spanning tree problem Oct 18, 2010

In Lecture 11, Gusfield covers Prim's algorithm and analysis, and Kruskal's algorithm.

Correctness of Kruskal's algorithm. Oct 20, 2010

In Lecture 12, Gusfield talks about the proof of correctness of Kruskal's algorithm.

Recursive programming and memoization Oct 22, 2010

In Lecture 13, Gusfield introduces recursive programming and memoization through the problem of computing the maximum weight set of pairwise non-overlapping intervals.

Intro to dynamic programming, weighted interval problems Oct 27, 2010

Lecture 14 reviews memoization; introduction to dynamic programming (DP) for the weighted interval problem and traceback in DP.

Intro to the RNA folding problem and recurrences Oct 29, 2010

In Lecture 15, Gusfield finishes the discussion of interval selection, and then introduces the RNA folding problem and talks about recurrences for it.

Dynamic programming for RNA folding. Nov 01, 2010

Lecture 16 deals with the solution to the RNA folding problem using dynamic programming.

Dynamic programming for shortest path problem Nov 03, 2010

Lecture 17 covers dynamic programming for the shortest path problem in a weighted directed graph, as well as negative edge weights allowed but no negative cycles.

Floyd-Warshall algorithm for all-pairs shortest path Nov 05, 2010

In Lecture 18, Gusfield discusses Floyd-Warshall, the algorithm for computing the shortest path in a weighted graph between each pair of nodes in the graph.

The unique-decipherability problem Nov 08, 2010

Lecture 19 covers the unique-decipherability problem and gives definitions and the start of a graph-based solution.

Unique-Decipherability. Graph algorithm and proof of correctness Nov 10, 2010

Lecture 20 deals with unique-decipherability: efficient graph-based algorithm and proof of correctness.

Linear-time pattern matching. Z-values and Z-algorithm Nov 12, 2010

In Lecture 21, Gusfield covers linear-time pattern matching. He also discusses Z-values and Z-algorithms.

Finish of linear-time pattern matching Nov 15, 2010

Lecture 22 completes linear-time pattern matching using the Z-algorithm

Introduction to approximation algorithms Nov 17, 2010

Lecture 23 covers approximation algorithms - definition, factor of two approximation for the center cover problem.

Introduction to P and NP Nov 22, 2010

Lecture 24 gives an introduction to P and NP and polynomial-time reductions.

An intuitive view of NP Nov 24, 2010

Lecture 25 deals with an intuitive view of NP - not the correct formal definition.

Formal definition of P and NP Nov 29, 2010

In Lecture 26, Gusfield gives correct, formal definitions of P and NP, ending with a brief definition of NP-complete problems (languages).

Major theorems of NP-completeness Dec 01, 2010

Lecture 27 covers the major theorems of NP-completeness, P = NP question, and how to prove a new problem in NP-complete.

Coping with NP-completeness Dec 03, 2010

Lecture 28: Gusfield recaps NP-completeness. The professor discusses coping with NP-complete problems: approximation algorithms and lowering the exponent of exponential-time algorithms.

Our TOPPODCAST Picks

Follow Us

Stay Connected

Algorithm Design and Analysis

Related Podcasts

Links

Stay Connected