OpenClassroom
Universality: Proof Idea
CS 161 - Design and Analysis of Algorithms
Lecture 115 of 172
< Previous
Go to Video:
Why are you here?
Example: Internet Routing
Shortest-Path Algorithms
Example: Sequence Alignment (Part 1)
Example: Sequence Alignment (Part 2)
Beating Brute Force Search
Administrivia
Recursive Algorithms for Integer Multiplication
Gauss's Trick
Merge Sort: Motivation
Merge Sort: Formal Definition
Running Time of Merge
Running Time of Merge Sort (Part 1)
Running Time of Merge Sort (Part 2)
Guiding Principles of CS161 (Part 1)
Guiding Principles of CS161 (Part 2)
Review of Asymptotic Notation
Asymptotic Notation: Example #1
Asymptotic Notation: Example #2
Big-Omega and Big-Theta
Integer Multiplication Revisited
Master Method: Formal Statement (Part 1)
Master Method: Formal Statement (Part 2)
Master Method: Examples
Proof of Master Method (Part 1)
Proof of Master Method (Part 2)
Master Method: Interpretation of the Three Cases
Proof of Master Method (Part 3)
The Selection Problem
Partitioning Around a Pivot
A Generic Selection Algorithm
Median of Medians
Recap
Rough Recurrence
Key Lemma (Part 1)
Key Lemma (Part 2)
The Substitution Method
Analysis of Rough Recurrence
Graph Primitives
Representing Graphs: Adjacency Matrices and Lists
Breadth-First and Depth-First Search
Dijkstra's Algorithm (Part 1)
Dijkstra's Algorithm (Part 2)
Dijkstra's Algorithm: Example
Dijkstra's Algorithm: Proof of Correctness (Part 1)
Dijkstra's Algorithm: Proof of Correctness (Part 2)
Undirected Connectivity
Strongly Connected Components
SCCs: A Two-Pass Algorithm
Depth-First Search Revisited
Example (Part 1)
Example (Part 2)
Two-Tier Structure of Directed Graphs
Correctness of Algorithm
Correctness Intuition
Proof of Key Lemma
Structure of the Web, Small World Property, and PageRank
Course Roadmap
Application and Final Exam Info
A Scheduling Problem
Two Greedy Algorithms
Correctness Proof
Cost-Benefit Analysis
Introduction
Prim's Algorithm
Graph Theory Preliminaries
Feasibility of Prim's Algorithm
The Cut Property
Proof of Cut Property
Key Exchange Argument
Naive Running Time and Heap Review
Implementing Prim with Heaps (Part 1)
Implementing Prim with Heaps (Part 2)
New Running Time Analysis
Kruskal's Algorithm
Proof of Correctness (Part 1)
Proof of Correctness (Part 2)
Naive Running Time
Union-Find Data Structure
Union by Rank
Rank and Size of Subtrees
Open Research Question
Path Compression
Path Compression and the Ackermann Function
Union-Find Review
Path Compression
Rank Blocks
Counting Pointer Updates
Clustering
A Greedy Algorithm
Correctness of Greedy Algorithm (Part 1)
Correctness of Greedy Algorithm (Part 2)
The Min Cut Problem
The Contraction Algorithm
Probability Review
Analysis of Contraction Algorithm
Success Through Independent Trials
Final Comments
The QuickSort Algorithm
Best-Case and Worst-Case Pivots
Running Time of Randomized QuickSort
Probability Review Part 2
Linearity of Expectation
Counting Comparisons
Crux of Proof
Final Calculations
Lower Bound of Comaprison-Based Sorting
Hashing: Introduction
Hashing: High-Level Idea
Running Time
How to Analyze Hashing
Universal Hashing
Proof of O(1) Running Time
A Universal Family
Universality: Proof Idea
Bloom Filters
Review of Binary Search Trees
Deleting from a BST
Red-Black Trees
Height of Red-Black Trees
Rotations
Insertion to a Red-Black Tree
Skip Lists: High-Level Idea
Skip Lists: Intuition for Analysis
Dynamic Programming: A First Example
Structure of Optimal Solution
A Recursive Algorithm
Bottom-Up Formulation
Reconstruction Algorithm
The Knapsack Problem
Dynamic Programming Solution
Sequence Alignment
Optimal Substructure
Dynamic Programming Solution
Dynamic Programming Algorithm
Shortest Paths with Negative Edge Lengths
On Negative Cycles
Optimal Substructure (Part 1)
Optimal Substructure (Part 2)
Single-Source Shortest Paths Revisited
The Bellman-Ford Algorithm
Negative Cycle Checking
Space Optimization
The Floyd-Warshall Algorithm (Part 1)
The Floyd-Warshall Algorithm (Part 2)
Dynamic Programming Algorithm
Polynomial Time Algorithms and P
The Traveling Salesman Problem
Reductions
Completeness
NP-Completeness
Many Problems are NP-Complete
Does P=NP?
Coping with NP-Completeness
The Vertex Cover Problem
Smarter Brute-Force Search
Performance Guarantees for Heuristics
A Greedy Knapsack Algorithm
Proof of Performance Guarantee
Final Exam Info
Better Performance via Dynamic Programming
Accuracy Analysis
Running Time Analysis
Bipartite Matching
Stable Matching
Gale-Shapley Proposal Algorithm
Maximum Flow
Selfish Flow and Braess's Paradox
Linear Programming
Computational Geometry
Approximation and Randomized Algorithms
Complexity and Epilogue
Next >