Design and Analysis of Algorithms

Course Description

Course Overview: Introduction to fundamental techniques for designing and analyzing algorithms, including asymptotic analysis; divide-and-conquer algorithms and recurrences; greedy algorithms; data structures; dynamic programming; graph algorithms; and randomized algorithms.

Required textbook: Kleinberg and Tardos, Algorithm Design, 2005. We will be covering most of Chapters 4–6, some parts of Chapter 13, and a couple of topics not in the book.

Prerequisites: Introduction to proofs, and discrete mathematics and probability (e.g., CS 103 and Stat116). If you have not taken a probability course, you should expect to do some independent reading during the course on topics including random variables, expectation, conditioning, and basic combinatorics.

1. INTRODUCTION (1/4/2011)

• 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

2. BASIC DIVIDE & CONQUER (1/6/2011)

• 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

3. THE MASTER METHOD (1/11/2011)

• 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)

4. LINEAR-TIME MEDIAN (1/13/2011) We apologize for the poor audio quality in this video.

• 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

5. GRAPH SEARCH & DIJKSTRA's ALGORITHM (1/18/2011)

• 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

6. CONNECTIVITY IN DIRECTED GRAPHS (1/20/2011)

• 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

7. Introduction to Greedy Algorithms (1/25/2011)

• Course Roadmap
• Application and Final Exam Info
• A Scheduling Problem
• Two Greedy Algorithms
• Correctness Proof
• Cost-Benefit Analysis

8. Minimum Spanning Trees (1/27/2011)

• 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

9. Kruskal's Algorithm and Union-Find (2/1/2011)

• 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

10. Path Compression and Clustering (2/3/2011)

• 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)

11. Introduction to Randomized Algorithms (2/8/2011)

• The Min Cut Problem
• The Contraction Algorithm
• Probability Review
• Analysis of Contraction Algorithm
• Success Through Independent Trials
• Final Comments

12. QuickSort (2/10/2011)

• 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

13. Hashing (2/15/2011)

• 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

14. Balanced Search Trees and Skip Lists (2/17/2011)

• 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

15. Introduction to Dynamic Programming (2/22/2011)

• Dynamic Programming: A First Example
• Structure of Optimal Solution
• A Recursive Algorithm
• Bottom-Up Formulation
• Reconstruction Algorithm
• The Knapsack Problem
• Dynamic Programming Solution

16. Sequence Alignment (2/24/2011)

• 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)

17. Shortest Paths: Bellman-Ford and Floyd-Warshall (3/1/2011)

• 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

18. NP-Complete Problems (3/3/2011)

• 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

19. Approximation Algorithms (3/8/2011)

• 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

20. The Wider World of Algorithms (3/10/2011)

• 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

Teacher: Prof. Tim Roughgarden