Эпизоды
-
Lecture 28: Gusfield recaps NP-completeness.
The professor discusses coping with NP-complete problems: approximation algorithms and lowering the exponent of exponential-time algorithms. -
Lecture 27 covers the major theorems of NP-completeness, P = NP question, and how to prove a new problem in NP-complete.
-
Пропущенные эпизоды?
-
In Lecture 26, Gusfield gives correct, formal definitions of P and NP, ending with a brief definition of NP-complete problems (languages).
-
Lecture 25 deals with an intuitive view of NP - not the correct formal definition.
-
Lecture 24 gives an introduction to P and NP and polynomial-time reductions.
-
Lecture 23 covers approximation algorithms - definition, factor of two approximation for the center cover problem.
-
Lecture 22 completes linear-time pattern matching using the Z-algorithm
-
In Lecture 21, Gusfield covers linear-time pattern matching. He also discusses Z-values and Z-algorithms.
-
Lecture 20 deals with unique-decipherability: efficient graph-based algorithm and proof of correctness.
-
Lecture 19 covers the unique-decipherability problem and gives definitions and the start of a graph-based solution.
-
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.
-
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.
-
Lecture 16 deals with the solution to the RNA folding problem using dynamic programming.
-
In Lecture 15, Gusfield finishes the discussion of interval selection, and then introduces the RNA folding problem and talks about recurrences for it.
-
Lecture 14 reviews memoization; introduction to dynamic programming (DP) for the weighted interval
problem and traceback in DP. -
In Lecture 13, Gusfield introduces recursive programming and memoization through the problem of computing the maximum weight set of pairwise non-overlapping intervals.
-
In Lecture 12, Gusfield talks about the proof of correctness of Kruskal's algorithm.
-
In Lecture 11, Gusfield covers Prim's algorithm and analysis, and Kruskal's algorithm.
-
In Lecture 10, students learn about Dijkstra's algorithm for shortest paths in a graph with non-negative edge weights.
-
In Lecture 9A, Gusfield provides another scheduling problem to be solved by a greedy algorithm.
- Показать больше
