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)