ECS122A - Algorithm Design and Analysis

UC Davis - ECS122A - Algorithm Design and Analysis (Fall 2010). This consists of 28 video lectures given by Professor Dan Gusfield. This is an undergraduate course that introduces fundamental techniques and viewpoints for the design and the analysis of efficient computer algorithms, and studies important specific algorithms. Lectures cover topics: Complexity of algorithms, bounds on complexity, sorting algorithms, graph algorithms, pattern matching, dynamic programming, approximation algorithms, and NP-completeness.


Lecture 01 - Introduction to the Course and Algorithm Complexity
Lecture 02 - Big-Oh, Omega and Theta Notation
Lecture 03 - Time Analysis of Mergesort
Lecture 04 - A More Complex Recurrence Relation and Counting Inversions
Lecture 05 - Counting Inversions; Fast Integer Multiplication
Lecture 06 - Fast Integer Multiplication, Randomized Selection and Median Finding
Lecture 07 - More on Randomized Selection and Median Finding
Lecture 08 - Expected Number of Comparisons in Randomized Select
Lecture 09 - Greedy Algorithms: Picking Largest Set of Non-Overlapping Intervals
Lecture 9A - Greedy Algorithms: The Classroom Scheduling Problem
Lecture 10 - Dijkstra's Shortest Path Algorithm
Lecture 11 - Start of Minimum Spanning Tree Problem
Lecture 12 - Correctness of Kruskal's Algorithm
Lecture 13 - Recursive Programming and Memoization
Lecture 14 - Intro to Dynamic Programming, Weighted Interval Problems
Lecture 15 - Intro to the RNA Folding Problem and Recurrences
Lecture 16 - Dynamic Programming for RNA Folding
Lecture 17 - Dynamic Programming for Shortest Path Problem
Lecture 18 - Floyd-Warshall Algorithm for All-pairs Shortest Path
Lecture 19 - The Unique-decipherability Problem
Lecture 20 - Unique-Decipherability - Graph Algorithm and Proof of Correctness
Lecture 21 - Linear-time Pattern Matching, Z-values and Z-algorithm
Lecture 22 - Finish of Linear-time Pattern Matching
Lecture 23 - Introduction to Approximation Algorithms
Lecture 24 - Introduction to P and NP
Lecture 25 - An Intuitive View of NP
Lecture 26 - Lecture
Lecture 27 - Major Theorems of NP-completeness
Lecture 28 - Coping with NP-completeness


Web.. ECS122A - Algorithm Design and Analysis, Fall 2010
Professor Dan Gusfield. This index page will just link to the various course handouts that are available on the web, and provide some description of them.
www.cs.ucdavis.edu/~gusfield/cs122f10/