asarkar/algorithms-design-analysis

Lecture videos and homework for Algorithms: Design and Analysis, Part 1, taught by Tim Roughgarden

Lecture videos and answers to homeworks for Algorithms: Design and Analysis, Part 1 - an online course offered by Stanford University and taught by Prof. Tim Roughgarden.

Syllabus:

1. Introduction

1.1 Why Study Algorithms?

1.2 Integer Multiplication

1.3 Karatsuba Multiplication

1.4 About the Course

1.5 Merge Sort: Motivation and Example

1.6 Merge Sort: Pseudocode

1.7 Merge Sort: Analysis

1.8 Guiding Principles for Analysis of Algorithms

2. Asymptotic Analysis

2.1 The Gist

2.2 Big-Oh Notation

2.3 Basic Examples

2.4 Big Omega and Theta

2.5 Additional Examples (Review - Optional)

3. Divide & Conquer Algorithms

3.1 O(n log n) Algorithm for Counting Inversions I

3.2 O(n log n) Algorithm for Counting Inversions II

3.3 Strassen's Subcubic Matrix Multiplication Algorithm

3.4 O(n log n) Algorithm for Closest Pair I (Advanced - Optional)

3.5 O(n log n) Algorithm for Closest Pair II (Advanced - Optional)

Homework 1

• Problem Set
• Optional Theory Problems
• Programming Assignment

4. The Master Method

4.1 Motivation

4.2 Formal Statement

4.3 Examples

4.4 Proof I

4.5 Interpretation of the 3 Cases

4.6 Proof II

5. Quicksort - Algorithm

5.1 Quicksort: Overview

5.2 Partitioning Around a Pivot

5.3 Correctness of Quicksort (Review - Optional)

5.4 Choosing a Good Pivot

6. Quicksort - Analysis

6.1 Analysis I: A Decomposition Principle (Advanced - Optional)

6.2 Analysis II: The Key Insight (Advanced - Optional)

6.3 Analysis III: Final Calculations (Advanced - Optional)

7. Probability Review

7.1 Probability Review I (Review - Optional)

7.2 Probability Review II (Review - Optional)

Homework 2

• Problem Set
• Optional Theory Problems
• Programming Assignment

8. Linear-time Selection

8.1 Randomized Selection - Algorithm

8.2 Randomized Selection - Analysis

8.3 Deterministic Selection - Algorithm (Advanced - Optional)

8.4 Deterministic Selection - Analysis I (Advanced - Optional)

8.5 Deterministic Selection - Analysis II (Advanced - Optional)

8.6 Omega(n log n) Lower Bound for Comparison-Based Sorting (Advanced - Optional)

9. Graphs and the Contraction Algorithm

9.1 Graphs and Minimum Cuts

9.2 Graph Representations

9.3 Random Contraction Algorithm

9.4 Analysis of Contraction Algorithm

9.5 Counting Minimum Cuts

Homework 3

• Problem Set
• Optional Theory Problems
• Programming Assignment

10. Graph Search and Connectivity

10.1 Graph Search - Overview

10.2 Breadth-First Search (BFS): The Basics

10.3 BFS and Shortest Paths

10.4 BFS and Undirected Connectivity

10.5 Depth-First Search (DFS): The Basics

10.6 Topological Sort

10.7 Computing Strong Components: The Algorithm

10.8 Computing Strong Components: The Analysis

10.9 Structure of the Web (Optional)

Homework 4

• Problem Set
• Optional Theory Problems
• Optional Theory Problems Code
• Programming Assignment

11. Dijkstra's Shortest-Path Algorithm

11.1 Dijkstra's Shortest-Path Algorithm

11.2 Dijkstra's Algorithm: Examples

11.3 Correctness of Dijkstra's Algorithm (Advanced - Optional)

11.4 Dijkstra's Algorithm: Implementation and Running Time

12. Heaps

12.1 Data Structures: Overview

12.2 Heaps: Operations and Applications

12.3 Heaps: Implementation Details (Advanced - Optional)

13. Balanced Binary Search Trees

13.1 Balanced Search Trees: Operations and Applications

13.2 Binary Search Tree Basics I

13.3 Binary Search Tree Basics II

13.4 Red-Black Trees

13.5 Rotations (Advanced - Optional)

13.6 Insertion in a Red-Black Tree (Advanced)

Homework 5

• Problem Set
• Optional Theory Problems
• Programming Assignment

14. Hashing: The Basics

14.1 Hash Tables: Operations and Applications

14.2 Hash Tables: Implementation Details I

14.3 Hash Tables: Implementation Details II

15. Universal Hashing

15.1 Pathological Data Sets and Universal Hashing Motivation

15.2 Universal Hashing: Definition and Example (Advanced - Optional)

15.3 Universal Hashing: Analysis of Chaining (Advanced - Optional)

15.4 Hash Table Performance with Open Addressing (Advanced - Optional)

16. Bloom Filters

16.1 Bloom Filters: The Basics

16.2 Bloom Filters: Heuristic Analysis

Homework 6

• Problem Set
• Optional Theory Problems
• Programming Assignment

Final Exam

• Final Exam