Cover image of Algorithm Design and Analysis

Algorithm Design and Analysis

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 algorit... Read more

Podcast cover

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

Podcast cover

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

Podcast cover

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

Podcast cover

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

Podcast cover

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

Podcast cover

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

Podcast cover

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

Podcast cover

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

Podcast cover

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

Podcast cover

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

“Podium: AI tools for podcasters. Generate show notes, transcripts, highlight clips, and more with AI. Try it today at https://podium.page”