Algorithm Design and Analysis

Latest Episodes:

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

Show notes

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.

Dynamic programming for shortest path problem Nov 03, 2010

Show notes

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.

Dynamic programming for RNA folding. Nov 01, 2010

Show notes

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

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

Show notes

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

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

Show notes

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

Recursive programming and memoization Oct 22, 2010

Show notes

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

Correctness of Kruskal's algorithm. Oct 20, 2010

Show notes

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

Start of minimum spanning tree problem Oct 18, 2010

Show notes

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

Dijkstra's shortest path algorithm Oct 15, 2010

Show notes

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

Greedy algorithms: The classroom scheduling problem Oct 14, 2010

Show notes

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