Design and Analysis of Algorithms (Fall, 2008)
By Charles U. Martel
To listen to an audio podcast, mouse over the title and click Play. Open iTunes to download and subscribe to podcasts.
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.
|1||CleanVideoIntroduction: Types of analysis||--||1/16/2009||Free||View in iTunes|
|2||CleanVideoFinish 6.5; sequence alignment (6.6); linear space (6.7)||--||1/16/2009||Free||View in iTunes|
|3||CleanVideoLinear space analysis (6.7); shortest paths (6.8-6.9, bit of 6.10)||--||1/16/2009||Free||View in iTunes|
|4||CleanVideoNetwork Flows (7.1, 7.2): Problem definition, residual graphs, Ford-Fulkerson algorithm||--||1/16/2009||Free||View in iTunes|
|5||CleanVideoNetwork flows: Scaling algorithm, application to bipartite matching, disjoint paths (7.3, 7.5, 7.6)||--||1/16/2009||Free||View in iTunes|
|6||VideoNetwork flow applications||--||1/20/2009||Free||View in iTunes|
|7||VideoAdvanced graph algorithms||--||1/20/2009||Free||View in iTunes|
|8||VideoHard problems: NP, decision vs. optimization, subset sum reductions||--||1/20/2009||Free||View in iTunes|
|9||VideoPspace (9.1,9.2); dealing with hard problems||--||1/20/2009||Free||View in iTunes|
|10||Video10.2 Independent set; approximations: vertex cover, scheduling 11.1||--||1/20/2009||Free||View in iTunes|
|11||VideoMidterm solutions||--||1/20/2009||Free||View in iTunes|
|12||VideoSet cover finished (11.3); weighted vertex cover 11.4||--||1/20/2009||Free||View in iTunes|
|13||VideoApproximations for: disjoint paths 11.5, 11.8 knapsack||--||1/20/2009||Free||View in iTunes|
|14||VideoLinear programming/integer programming||--||1/20/2009||Free||View in iTunes|
|15||VideoLocal search (12.1); simulated annealing (brief) (12.2)||--||1/20/2009||Free||View in iTunes|
|16||VideoRandomized Max-SAT (13.4); universal hashing (13.6); perfect hashing (CLRS 11.5)||--||1/20/2009||Free||View in iTunes|
|17||VideoClosest point (13.7); introduction to primality testing||--||1/20/2009||Free||View in iTunes|
|18||VideoPrimality testing (see Cormen, Leiserson, Rivest 31.8)||--||1/20/2009||Free||View in iTunes|
Useful and Accessible Lectures
Cohesive and logical follow up to the undergraduate algorithms class. These lectures will not teach you how to program exactly, but they will scaffold how you can think about algorithms at a high level and problem solve with computers.
Based on my experience, you'll be better equipped to evaluate and learn from the many, many resources scattered online. There's a flood of data structures and algorithms available, so it helps to know the main categories, problem types, and tools to evaluate them in practice.
Good luck and happy coding!