ECS 122A: Algorithm Design and Analysis

ECS 122A: Algorithm Design and Analysis (Fall 2010, UC Davis). Taught by Professor Dan Gusfield, this course introduces fundamental techniques and viewpoints for the design and the analysis of efficient computer algorithms, and studies 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.


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 - Formal Definition of P and NP
Lecture 27 - Major Theorems of NP-completeness
Lecture 28 - Coping with NP-completeness

ECS 122A - Algorithm Design and Analysis, Fall 2010
Instructor: 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.