# Algorithm Design and Analysis

#### Integer Arithmetic and RSA Encryption

 8/24 Read Chapter 0 Watch Big Oh Notation (Tim Roughgarden) Introduction to the course 8/26 Read Sections 1.1-1.2 Watch Integer Multiplication (Tim Roughgarden) and RA1: Modular Arithmetic (Eric Vigoda) Bitwise arithmetic

 8/31 Read Section 1.3 Watch RA2: RSA (Eric Vigoda) Primality Homework 1 due 9/2 Read Section 1.4 Watch RSA-129 (Ron Rivest) RSA encryption Quiz 1

#### Divide and Conquer

 9/7 Read Section 2.1 Watch Karatsuba Multiplication (Tim Roughgarden) Integer multiplication 9/9 Read Section 2.2 Master theorem Homework 2 due

 9/14 Read Sections 2.3-2.4 Watch Randomized Selection (Tim Roughgarden) Mergesort and Median/Select Quiz 2 9/16 Read Section 2.5 Watch Strassen's Subcubic Matrix Multiplication (Tim Roughgarden) Matrix multiplication Homework 3 due

#### Graph Algorithms

 9/21 Read Section 3.1 Watch Graph Representations (Tim Roughgarden) Graphs 9/23 Read Sections 3.2-3.3 Watch DFS The Basics (Tim Roughgarden) Depth-first search (DFS) Homework 4 due

 9/28 Read Sections 4.1-4.3 Watch BFS The Basics (Tim Roughgarden) Breadth-first search (BFS) Quiz 3 9/30 Read Sections 4.4-4.6 Watch Dijkstra's Algorithm Examples (Tim Roughgarden) Dijkstra's and Bellman-Ford Algorithms Homework 5 due

 10/5 IN-CLASS MIDTERM 10/7 Fall Break (no class)

#### Greedy Algorithms

 10/12 Read Section 5.1 Watch Greedy Algorithms and MST (Charles Leiserson) Minimum spanning tree (MST) 10/14 Read Section 5.4 Approximate set cover

#### Dynamic Programming

 10/19 Read Sections 6.1-6.2 Watch Dynamic Programming and Longest Common Subsequence (Charles Leiserson) Elements of DP and Longest Increasing Subsequence 10/21 Read Section 6.3 Watch videos 2-12 of Algorithms@Udacity (Charles Brubaker) Edit Distance and Longest Common Subsequence Homework 6 due

 10/26 Read Section 6.4 Watch DP2: Knapsack (Eric Vagoda) Knapsack 10/28 Read Section 6.6 All-Pairs Shortest Paths Quiz 4 Homework 7 due

#### Parallel Programming

We will be using alternate materials for this section:
Chapter 27 of Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein

 11/2 Read Section 27.1 of CLRS Watch Multithreaded Programming (Charles Leiserson) PRAM model, performance measures, and thread scheduling 11/4 Read Section 27.2 of CLRS Watch Multithreaded Algorithms (Charles Leiserson) Parallel matrix multiplication Homework 8 due

 11/9 Read Section 27.3 of CLRS Parallel merge sort Quiz 5 11/11 Parallel dynamic programming

#### NP-Complete Problems

 11/16 Read Sections 8.1-8.2 Watch NP1: Definitions (Eric Vagoda) P vs NP and NP-complete problems Homework 9 due 11/18 Read Section 8.3 Watch NP2: 3SAT (Eric Vagoda) Reductions Quiz 6

 11/23 Read Section 9.1 Backtracking and branch-and-bound Homework 10 due 11/25 Thanksgiving Break (no class)

 11/30 Read Section 9.2 Approximation algorithms 12/2 Final Review (last day of class) 12/6 FINAL EXAM (9am)