Podcasts Technology Design and Analysis of Algorithms (Fall, 2008)
Design and Analysis of Algorithms (Fall, 2008)

Design and Analysis of Algorithms (Fall, 2008)

18 episodes

In this graduate class, UC Davis computer science professor Charles Martel describes advanced methods for the design and analysis of algorithms. He applies these techniques to design fast solutions for a wide range of applications including scheduling, network routing, computational biology, resource management and network design.  The techniques studied include dynamic programming, network flows  and randomized algorithms. The class also studies how to classify problems as hard via np-completeness theory and how to deal with hard problems using approximation algorithms, special cases, and search techniques.

Podcasts

Local search (12.1); simulated annealing (brief) (12.2)

Published: Jan. 20, 2009, 11:47 a.m.
Duration: 1 hour 18 minutes 24 seconds

Listed in: Technology

Randomized Max-SAT (13.4); universal hashing (13.6); perfect hashing (CLRS 11.5)

Published: Jan. 20, 2009, 11:46 a.m.
Duration: 1 hour 21 minutes 53 seconds

Listed in: Technology

Closest point (13.7); introduction to primality testing

Published: Jan. 20, 2009, 11:46 a.m.
Duration: 1 hour 20 minutes 23 seconds

Listed in: Technology

Primality testing (see  Cormen, Leiserson, Rivest 31.8)

Published: Jan. 20, 2009, 11:46 a.m.
Duration: 57 minutes 45 seconds

Listed in: Technology

Midterm solutions

Published: Jan. 20, 2009, 11:38 a.m.
Duration: 1 hour 20 minutes 6 seconds

Listed in: Technology

Set cover finished (11.3); weighted vertex cover 11.4

Published: Jan. 20, 2009, 10:52 a.m.
Duration: 1 hour 23 minutes 13 seconds

Listed in: Technology

Linear programming/integer programming

Published: Jan. 20, 2009, 10:51 a.m.
Duration: 1 hour 22 minutes 4 seconds

Listed in: Technology

Approximations for: disjoint paths 11.5, 11.8 knapsack

Published: Jan. 20, 2009, 10:51 a.m.
Duration: 1 hour 22 minutes 29 seconds

Listed in: Technology

Pspace (9.1,9.2); dealing with hard problems

Published: Jan. 20, 2009, 10:48 a.m.
Duration: 1 hour 21 minutes 44 seconds

Listed in: Technology

10.2 Independent set; approximations: vertex cover, scheduling 11.1

Published: Jan. 20, 2009, 10:48 a.m.
Duration: 1 hour 15 minutes 39 seconds

Listed in: Technology

Hard problems: NP, decision vs. optimization, subset sum reductions

Published: Jan. 20, 2009, 10:48 a.m.
Duration: 1 hour 24 minutes 42 seconds

Listed in: Technology

Advanced graph algorithms

Published: Jan. 20, 2009, 10:48 a.m.
Duration: 1 hour 23 minutes 52 seconds

Listed in: Technology

Network flow applications

Published: Jan. 20, 2009, 10:48 a.m.
Duration: 1 hour 20 minutes 47 seconds

Listed in: Technology

Finish 6.5; sequence alignment (6.6); linear space (6.7)

Published: Jan. 16, 2009, 9:13 a.m.
Duration: 1 hour 25 minutes 1 second

Listed in: Technology

Linear space analysis (6.7); shortest paths (6.8-6.9, bit of 6.10)

Published: Jan. 16, 2009, 9:13 a.m.
Duration: 1 hour 21 minutes 58 seconds

Listed in: Technology

Introduction: Types of analysis

Published: Jan. 16, 2009, 9:12 a.m.
Duration: 1 hour 23 minutes 21 seconds

Listed in: Technology

Network Flows (7.1, 7.2): Problem definition, residual graphs, Ford-Fulkerson algorithm

Published: Jan. 16, 2009, 9:12 a.m.
Duration: 1 hour 21 minutes 45 seconds

Listed in: Technology

Network flows: Scaling algorithm, application to bipartite matching, disjoint paths (7.3, 7.5, 7.6)

Published: Jan. 16, 2009, 9:12 a.m.
Duration: 1 hour 21 minutes 33 seconds

Listed in: Technology