Sign up to save your podcasts
Or
Share Algorithm Design and Analysis
Share to email
Share to Facebook
Share to X
Share to email
Share to Facebook
Share to X
Or
Algorithm Design and Analysis
By Dan Gusfield
Algorithm Design and Analysis episodes
- Floyd-Warshall algorithm for all-pairs shortest pathIn 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.49 min
- Dynamic programming for shortest path problemLecture 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.38 min
- Dynamic programming for RNA folding.Lecture 16 deals with the solution to the RNA folding problem using dynamic programming.50 min
- Intro to the RNA folding problem and recurrencesIn Lecture 15, Gusfield finishes the discussion of interval selection, and then introduces the RNA folding problem and talks about recurrences for it.51 min
- Intro to dynamic programming, weighted interval problemsLecture 14 reviews memoization; introduction to dynamic programming (DP) for the weighted intervalproblem and traceback in DP.50 min
- Recursive programming and memoizationIn Lecture 13, Gusfield introduces recursive programming and memoization through the problem of computing the maximum weight set of pairwise non-overlapping intervals.48 min
- Correctness of Kruskal's algorithm.In Lecture 12, Gusfield talks about the proof of correctness of Kruskal's algorithm.27 min
- Start of minimum spanning tree problemIn Lecture 11, Gusfield covers Prim's algorithm and analysis, and Kruskal's algorithm.50 min
- Dijkstra's shortest path algorithmIn Lecture 10, students learn about Dijkstra's algorithm for shortest paths in a graph with non-negative edge weights.52 min
- Greedy algorithms: The classroom scheduling problemIn Lecture 9A, Gusfield provides another scheduling problem to be solved by a greedy algorithm.17 min
About Algorithm Design and Analysis
From the publisher's feed
The purpose of this undergraduate course is to introduce fundamental techniques and viewpoints for the design and the analysis of efficient computer algorithms, and to study important specific…
algorithms. The course relies heavily on mathematics and mathematical thinking in two ways: first as a way of proving properties about particular algorithms such as termination, and correctness; and second, as a way of establishing bounds on the worst case (or average case) use of some resource, usually time, by a specific algorithm. The course covers some randomized algorithms as well as deterministic algorithms.