# Design and Analysis of Algorithms

### Description

## 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 in…

### Frequently asked questions

trainings.faqs. There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.

## 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

### Share your review

Do you have experience with this course? Submit your review and help other people make the right choice. As a thank you for your effort we will donate $1.- to Stichting Edukans.trainings.faqs. There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.