# Design and Analysis of Algorithms

Location type

Need more information? Get more details on the site of the provider.

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

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

Didn't find what you were looking for? See also: Mathematics, Algorithms, Programming, Ruby on Rails, and Ruby.

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

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

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

There are no reviews yet.