Coping with NP-completeness
Coping with NP-completeness
Lecture 28: Gusfield recaps NP-completeness.The professor discusses coping with NP-complete problems: approximation alg... Read more
3 Dec 2010
•
39mins
Major theorems of NP-completeness
Major theorems of NP-completeness
Lecture 27 covers the major theorems of NP-completeness, P = NP question, and how to prove a new problem in NP-complete.
1 Dec 2010
•
50mins
Similar Podcasts
Algorithms + Data Structures = Programs
All-In with Chamath, Jason, Sacks & Friedberg
The Jordan B. Peterson Podcast
Formal definition of P and NP
Formal definition of P and NP
In Lecture 26, Gusfield gives correct, formal definitions of P and NP, ending with a brief definition of NP-complete pro... Read more
29 Nov 2010
•
45mins
An intuitive view of NP
An intuitive view of NP
Lecture 25 deals with an intuitive view of NP - not the correct formal definition.
24 Nov 2010
•
48mins
Most Popular Podcasts
The Joe Rogan Experience
TED Talks Daily
The Tim Ferriss Show
The Daily
Stuff You Should Know
Oprah's SuperSoul Conversations
Armchair Expert with Dax Shepard
Introduction to P and NP
Introduction to P and NP
Lecture 24 gives an introduction to P and NP and polynomial-time reductions.
22 Nov 2010
•
50mins
Introduction to approximation algorithms
Introduction to approximation algorithms
Lecture 23 covers approximation algorithms - definition, factor of two approximation for the center cover problem.
17 Nov 2010
•
47mins
Finish of linear-time pattern matching
Finish of linear-time pattern matching
Lecture 22 completes linear-time pattern matching using the Z-algorithm
15 Nov 2010
•
51mins
Linear-time pattern matching. Z-values and Z-algorithm
Linear-time pattern matching. Z-values and Z-algorithm
In Lecture 21, Gusfield covers linear-time pattern matching. He also discusses Z-values and Z-algorithms.
12 Nov 2010
•
51mins
Unique-Decipherability. Graph algorithm and proof of correctness
Unique-Decipherability. Graph algorithm and proof of correctness
Lecture 20 deals with unique-decipherability: efficient graph-based algorithm and proof of correctness.
10 Nov 2010
•
51mins
The unique-decipherability problem
The unique-decipherability problem
Lecture 19 covers the unique-decipherability problem and gives definitions and the start of a graph-based solution.
8 Nov 2010
•
52mins
