Analysis of algorithms-insertion sort, asymptotic analysis, merge sort, recurrences
Screencast Leiserson 80 min
Asymptotic notation, standard notation, and common functions.
Textbook 22 pages
Asymptotic notation, recurrences, substitution, master method (start at 16 min)
Screencast Demaine 71 min
Stacks, queues, linked lists, pointers and objects, rooted trees.
Textbook 21 pages
The hiring problem, indicator random variable, randomized algorithms
Textbook 16 pages
Skip lists, from Goodrich and Tamassia’s Data Structures and Algorithms in Java
Textbook 10 pages
Examples of hash functions and universal chaining
Screencast Suthers 13 min
Using open addressing to avoid the overhead of linked lists.
Screencast Suthers 16 min
Direct address tables, hash tables, hash functions, and open addressing
Textbook 23 pages
Introduction to the divide and conquer algorithm
Screencast Suthers 14 min
How to generate a guess for the form of the solution to the recurrence.
Screencast Suthers 19 min
Find solutions to recurrence relations of form T(n) = aT(n/b) + h(n), where a and b are constants, a ≥ 1 and b > 1
Screencast Suthers 17 min
The maximum subarray problem, strassen’s algorithm for matrix multiplication, substitution method, recursion tree method, and the master method.
Textbook 30 pages
Divide and conquer: binary search, powering a number, fibonacci numbers, matrix multiplication
Screencast Demaine 68 min
What is a binary search tree; querying, insertion, and deletion.
Textbook 13 pages
Heapsort, heaps, maintaining the heap property, building a heap, priority queues
Textbook 19 pages
Description and performance of quicksort, a randomized version, and analysis.
Textbook 20 pages
Lower bounds for sorting, counting sort, radix sort, bucket sort.
Textbook 22 pages
Conceptual overview of balanced tree operations
Screencast Suthers 14 min
Top-down 2-3-4 trees, red-black trees, other algorithms
Textbook 14 pages
Example of dynamic programming using the cut rod problem.
Screencast Suthers 24 min
Example of dynamic programming using steps and LCS.
Screencast Suthers 17 min
Example of dynamic programming using LCS.
Screencast Suthers 18 min
Summary of dynamic programming.
Screencast Suthers 18 min
Rod cutting, matrix-chain multiplication, elements of DP, longest common subsequence, optimal BSTs
Textbook 55 pages
Knapsack problem, matrix chain product, optimal BSTs, shortest paths, time and space requirements
Textbook 14 pages
Dynamic programming and greedy algorithsm.
Screencast Suthers 8 min
Illustration of the greedy strategy.
Screencast Suthers 23 min
Activity selection problems, elements of the greedy algorithm strategy, huffman codes (16.1 -16.3)
Textbook 23 pages
Greedy algorithms, the activity selection problem, greedy strategy, and Huffman codes.
Notes
Breadth first search and applications to finding the shortest path
Screencast Suthers 16 min
Representations of graphs, breadth-first search, depth-first search, topological sort, strongly connected components
Textbook 24 pages
Depth first search, transitive closure, topological sorting, strongly connected components
Textbook 12 pages
Undirected graphs, directed graphs, minimum spanning trees, shortest paths
Textbook 12 pages
The graph ADT, data structures for graphs, graph traversals, directed graphs, weighted graphs, shortest paths, minimum spanning trees
Textbook 70 pages
Graph definitions, examples, the ADT, representations, breadth first seach, depth first search, topological sort, strongly connected components
Notes
Aggregate, accounting, and potential methods
Screencast Suthers 23 min
aggregate analysis, the accounting method, the potential method, dynamic tables
Textbook 30 pages
The general idea, multipop example, aggregate analysis, accounting method, potential method, dynamic tables.
Notes
disjoint set operations, linked-list representation of disjoint sets, disjoint-set forests, analysis of union by rank with path compression
Textbook 25 pages
Disjoint sets, finding connected components, linked list representations, and forest representations
Notes
Including the generic algorithm and the safe edge theorem
Screencast Suthers 17 min
Kruskal’s minimum spanning tree algorithm, with example and analysis.
Screencast Suthers 13 min
Prim’s minimum spanning tree algorithm, with example and analysis.
Screencast Suthers 15 min
Growing a minimum spanning tree, the algorithms of Kruskal and Prim.
Textbook 19 pages
Minimum spanning trees, shortest path, dense paths, geometric problems
Textbook 14 pages
Minimum spanning trees, the generic algorithm, Kruskal’s and Prim’s algorithms
Notes
Properties of the problem, supporting algorithms
Screencast Suthers 19 min
Dijkstra’s algorithm
Screencast Suthers 20 min
Bellman-Ford algorithm, SSSP in directed acyclic graphs, Dijkstra’s algorithm
Textbook 20 pages
Minimum spanning trees, shortest path, dense paths, geometric problems
Textbook 14 pages
Shortest paths problem, Bellman-Ford algorithm, Shortest paths in a DAG, Dijkstra’s algorithm
Notes
Floyd-Warshall’s algorithm
Screencast Suthers 20 min
Shortest paths and matrix multiplication, Floyd-Warshall algorithm, Johnson’s algorithm for sparse graphs
Textbook 22 pages
All pairs shortest paths problem, using single source algorithms, Johnson’s bright idea, Floyd-Warshall: dynamic programming for dense graphs, transitive closure
Notes
Residual graphs, augmenting flows, and the min cut max flow theorem
Screencast Suthers 20 min
Ford-Fulkerson, Edmonds-Karp and Bipartite Matching.
Screencast Suthers 14 min
Flow networks, Ford-Fulkerson method, Maximum bipartite matching.
Textbook 29 pages
Flow networks, maximum flow problem, Ford-Fulkerson algorithm, Edmonds-Karp algorithm, maximum bipartite matching
Notes
A simple example, outline of the method, variations and extensions
Textbook 10 pages
Linear programs, geometric interpretation, simplex method
Textbook 15 pages
Standard and slack forms, formulating problems as linear programs, the simplex algorithm.
Textbook 35 pages
Introduction, formulating problems as linear programs, foundations in gaussian elimination, the simplex method
Notes
The basics of dynamic multithreading, multithreaded matrix multiplication, multithreaded merge sort.
Textbook 36 pages
Concepts of dynamic multithreading, modeling and measuring dynamic multithreading, analysis of multithreaded algorithms, matrix multiplication example, merge sort example
Notes
The naive string matching algorithm, the Robin-Karp algorithm, string matching with finite automata, the Knuth-Morris-Pratt algorithm
Textbook 29 pages
Naive (brute force) string matching, matching with finite state automata, Knuth-Morris-Pratt algorithm, Rabin-Karp algorithm
Notes
Examples of problems from logic, graph theory, and arithmetic
Screencast Suthers 25 min
P and NP classes, encoding problems and polynomial time verification, constructing NPC
Notes
Vertex cover example, TSP example, randomization and linear programming strategies
Notes