Algorithm Design and Analysis

Algorithm Design and Analysis

30 episodes

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.

Podcasts

Coping with NP-completeness

Published: Dec. 3, 2010, 8 a.m.
Duration: 39 minutes 36 seconds

Listed in: Technology

Major theorems of NP-completeness

Published: Dec. 1, 2010, 8 a.m.
Duration: 50 minutes 25 seconds

Listed in: Technology

Formal definition of P and NP

Published: Nov. 29, 2010, 8 a.m.
Duration: 45 minutes 29 seconds

Listed in: Technology

An intuitive view of NP

Published: Nov. 24, 2010, 8 a.m.
Duration: 48 minutes 2 seconds

Listed in: Technology

Introduction to P and NP

Published: Nov. 22, 2010, 8 a.m.
Duration: 50 minutes 7 seconds

Listed in: Technology

Introduction to approximation algorithms

Published: Nov. 17, 2010, 8 a.m.
Duration: 47 minutes 51 seconds

Listed in: Technology

Finish of linear-time pattern matching

Published: Nov. 15, 2010, 8 a.m.
Duration: 51 minutes 35 seconds

Listed in: Technology

Linear-time pattern matching. Z-values and Z-algorithm

Published: Nov. 12, 2010, 8 a.m.
Duration: 51 minutes 45 seconds

Listed in: Technology

Unique-Decipherability. Graph algorithm and proof of correctness

Published: Nov. 10, 2010, 8 a.m.
Duration: 51 minutes 19 seconds

Listed in: Technology

The unique-decipherability problem

Published: Nov. 8, 2010, 8 a.m.
Duration: 52 minutes 19 seconds

Listed in: Technology

Floyd-Warshall algorithm for all-pairs shortest path

Published: Nov. 5, 2010, 7 a.m.
Duration: 48 minutes 28 seconds

Listed in: Technology

Dynamic programming for shortest path problem

Published: Nov. 3, 2010, 7 a.m.
Duration: 37 minutes 29 seconds

Listed in: Technology

Dynamic programming for RNA folding.

Published: Nov. 1, 2010, 7 a.m.
Duration: 49 minutes 35 seconds

Listed in: Technology

Intro to the RNA folding problem and recurrences

Published: Oct. 29, 2010, 7 a.m.
Duration: 50 minutes 8 seconds

Listed in: Technology

Intro to dynamic programming, weighted interval problems

Published: Oct. 27, 2010, 7 a.m.
Duration: 49 minutes 36 seconds

Listed in: Technology

Recursive programming and memoization

Published: Oct. 22, 2010, 7 a.m.
Duration: 47 minutes 37 seconds

Listed in: Technology

Correctness of Kruskal's algorithm.

Published: Oct. 20, 2010, 7 a.m.
Duration: 26 minutes 41 seconds

Listed in: Technology

Start of minimum spanning tree problem

Published: Oct. 18, 2010, 7 a.m.
Duration: 49 minutes 34 seconds

Listed in: Technology

Dijkstra's shortest path algorithm

Published: Oct. 15, 2010, 7 a.m.
Duration: 51 minutes 41 seconds

Listed in: Technology

Greedy algorithms: The classroom scheduling problem

Published: Oct. 14, 2010, 7 a.m.
Duration: 16 minutes 35 seconds

Listed in: Technology

Greedy algorithms: Picking largest set of non-overlapping intervals

Published: Oct. 13, 2010, 7 a.m.
Duration: 50 minutes 30 seconds

Listed in: Technology

Expected number of comparisons in randomized select

Published: Oct. 11, 2010, 7 a.m.
Duration: 50 minutes 10 seconds

Listed in: Technology

More on randomized selection and median finding

Published: Oct. 8, 2010, 7 a.m.
Duration: 52 minutes 13 seconds

Listed in: Technology

Fast integer multiplication, randomized selection and median finding

Published: Oct. 6, 2010, 7 a.m.
Duration: 48 minutes 10 seconds

Listed in: Technology

Counting inversions; Fast integer multiplication

Published: Oct. 4, 2010, 7 a.m.
Duration: 48 minutes 11 seconds

Listed in: Technology

A more complex recurrence relation and counting inversions

Published: Oct. 1, 2010, 7 a.m.
Duration: 52 minutes 48 seconds

Listed in: Technology

Time analysis of Mergesort

Published: Sept. 29, 2010, 7 a.m.
Duration: 49 minutes 57 seconds

Listed in: Technology

Big-Oh, Omega and Theta notation

Published: Sept. 27, 2010, 7 a.m.
Duration: 48 minutes 19 seconds

Listed in: Technology

Introduction to the course and algorithm complexity

Published: Sept. 24, 2010, 7 a.m.
Duration: 49 minutes 6 seconds

Listed in: Technology

Introduction to the videos

Published: Sept. 23, 2010, 7 a.m.
Duration: 2 minutes 25 seconds

Listed in: Technology