Technology

Algorithm Design and Analysis

Dan Gusfield

Algorithm Design and Analysis

Episodes

Introduction to the videos
0:02:25
2017-09-26 16:57:26 UTC 0:02:25
Introduction to the videos

Introduction to the course and algorithm complexity
0:49:06
2017-09-26 16:57:26 UTC 0:49:06
Introduction to the course and algorithm complexity

Big-Oh, Omega and Theta notation
0:48:19
2017-09-26 16:57:26 UTC 0:48:19
Big-Oh, Omega and Theta notation

Time analysis of Mergesort
0:49:57
2017-09-26 16:57:26 UTC 0:49:57
Time analysis of Mergesort

A more complex recurrence relation and counting inversions
0:52:48
2017-09-26 16:57:26 UTC 0:52:48
A more complex recurrence relation and counting inversions

Counting inversions; Fast integer multiplication
0:48:11
2017-09-26 16:57:26 UTC 0:48:11
Counting inversions; Fast integer multiplication

Fast integer multiplication, randomized selection and median finding
0:48:10
2017-09-26 16:57:26 UTC 0:48:10
Fast integer multiplication, randomized selection and median finding

More on randomized selection and median finding
0:52:13
2017-09-26 16:57:26 UTC 0:52:13
More on randomized selection and median finding

Expected number of comparisons in randomized select
0:50:10
2017-09-26 16:57:26 UTC 0:50:10
Expected number of comparisons in randomized select

Greedy algorithms: Picking largest set of non-overlapping intervals
0:50:30
2017-09-26 16:57:26 UTC 0:50:30
Greedy algorithms: Picking largest set of non-overlapping intervals

Greedy algorithms: The classroom scheduling problem
0:16:35
2017-09-26 16:57:26 UTC 0:16:35
Greedy algorithms: The classroom scheduling problem

Dijkstra's shortest path algorithm
0:51:41
2017-09-26 16:57:26 UTC 0:51:41
Dijkstra's shortest path algorithm

Start of minimum spanning tree problem
0:49:34
2017-09-26 16:57:26 UTC 0:49:34
Start of minimum spanning tree problem

Correctness of Kruskal's algorithm.
0:26:41
2017-09-26 16:57:26 UTC 0:26:41
Correctness of Kruskal's algorithm.

Recursive programming and memoization
0:47:37
2017-09-26 16:57:26 UTC 0:47:37
Recursive programming and memoization

Intro to dynamic programming, weighted interval problems
0:49:36
2017-09-26 16:57:26 UTC 0:49:36
Intro to dynamic programming, weighted interval problems

Intro to the RNA folding problem and recurrences
0:50:08
2017-09-26 16:57:26 UTC 0:50:08
Intro to the RNA folding problem and recurrences

Dynamic programming for RNA folding.
0:49:35
2017-09-26 16:57:26 UTC 0:49:35
Dynamic programming for RNA folding.

Dynamic programming for shortest path problem
0:37:29
2017-09-26 16:57:26 UTC 0:37:29
Dynamic programming for shortest path problem

Floyd-Warshall algorithm for all-pairs shortest path
0:48:28
2017-09-26 16:57:26 UTC 0:48:28
Floyd-Warshall algorithm for all-pairs shortest path

The unique-decipherability problem
0:52:19
2017-09-26 16:57:26 UTC 0:52:19
The unique-decipherability problem

Unique-Decipherability. Graph algorithm and proof of correctness
0:51:19
2017-09-26 16:57:26 UTC 0:51:19
Unique-Decipherability. Graph algorithm and proof of correctness

Linear-time pattern matching. Z-values and Z-algorithm
0:51:45
2017-09-26 16:57:26 UTC 0:51:45
Linear-time pattern matching. Z-values and Z-algorithm

Finish of linear-time pattern matching
0:51:35
2017-09-26 16:57:26 UTC 0:51:35
Finish of linear-time pattern matching

Introduction to approximation algorithms
0:47:51
2017-09-26 16:57:26 UTC 0:47:51
Introduction to approximation algorithms

Introduction to P and NP
0:50:07
2017-09-26 16:57:26 UTC 0:50:07
Introduction to P and NP

An intuitive view of NP
0:48:02
2017-09-26 16:57:26 UTC 0:48:02
An intuitive view of NP

Formal definition of P and NP
0:45:29
2017-09-26 16:57:26 UTC 0:45:29
Formal definition of P and NP

Major theorems of NP-completeness
0:50:25
2017-09-26 16:57:26 UTC 0:50:25
Major theorems of NP-completeness

Coping with NP-completeness
0:39:36
2017-09-26 16:57:26 UTC 0:39:36
Coping with NP-completeness