Data Structures and Algorithms II

Integer Arithmetic and RSA Encryption

1/13 Read Chapter 0
Watch Big Oh Notation (Tim Roughgarden)

Introduction to the course
1/15 Read Section 1.1
Watch Integer Multiplication (Tim Roughgarden)

Integer arithmetic
1/17 Read Section 1.2
Watch videos 2-22 of RA1: Modular Arithmetic (Eric Vigoda)

Modular arithmetic

1/20 MLK Day: No class
1/22 Read Section 1.3
Watch videos 1-23 of RA2: RSA (Eric Vigoda)

Primality testing
Homework 1 due
1/24 Read Section 1.4
Watch RSA-129 (Ron Rivest)

RSA encryption
Quiz 1

Divide and Conquer

1/27 Read Section 2.1
Watch Karatsuba Multiplication (Tim Roughgarden)

Integer multiplication
1/29 Read Section 2.2
Master theorem
Homework 2 due
1/31 Read Section 2.3

2/3 Read Section 2.4
Watch Randomized Selection (Tim Roughgarden)

2/5 Read Selection (Avrim Blum)
Watch videos 1-15 of DC2: Linear-Time Median (Eric Vigoda)

Deterministic Selection
Homework 3 due
2/7 Read Section 2.5
Watch Strassen's Subcubic Matrix Multiplication (Tim Roughgarden)

Matrix multiplication
Quiz 2

Graph Algorithms

2/10 Read Section 3.1
Watch Graph Representations (Tim Roughgarden)

2/12 Read Sections 3.2-3.3
Depth-first search (DFS)
Programming Assignment 1a due
2/14 (Optional) Work on PA 1b

2/17 Read Sections 4.1-4.2
Breadth-first search (BFS)
2/19 Read Section 4.3
Finish BFS
Programming Assignment 1b due
2/21 Read Section 4.4
Watch Dijkstra's Algorithm Examples (Tim Roughgarden)

Dijkstra's Algorithm
Quiz 3

Greedy Algorithms

2/24 Read Sections 5.1.1-5.1.2
Watch Greedy Algorithms and MST (Charles Leiserson)

Minimum spanning tree (MST) and cut property
2/26 Read Sections 5.1.3 and 5.1.5
Algorithms for MST
Homework 4 due
2/28 Read Section 5.1.4
A data structure for disjoint sets

3/2 Read Section 5.4
Approximate set cover
3/4 Midterm Review

3/9 Spring Break: No class
3/11 Spring Break: No class
3/13 Spring Break: No class
3/16 Canceled due to COVID-19: No class
3/18 Canceled due to COVID-19: No class
3/20 Canceled due to COVID-19: No class

Dynamic Programming

3/23 Read Sections 6.1-6.2
Watch Dynamic Programming and Longest Common Subsequence (Charles Leiserson)

Elements of DP and Longest Increasing Subsequence
3/25 Read Section 6.3
Watch videos 2-12 of Algorithms@Udacity (Charles Brubaker)

Edit Distance
3/27 Read Section 6.4
Watch videos 1-16 of DP2: Knapsack, Chain Multiply (Eric Vagoda)


3/30 Dynamic Programming Catch up

Parallel Programming

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

4/1 Read Section 27.1 of CLRS
Watch Multithreaded Programming (Charles Leiserson)

PRAM model, performance measures, and thread scheduling
Programming Assignment 2a due
4/3 Read Section 27.2 of CLRS
Watch Multithreaded Algorithms (Charles Leiserson)

Analyzing parallel algorithms: matrix multiplication

4/6 Read Section 27.3 of CLRS
Analyzing parallel algorithms: merge sort
4/8 Parallel dynamic programming
Programming Assignment 2b due
4/10 Good Friday: No class

NP-Complete Problems

4/13 Read Sections 8.1-8.2
Watch videos 1-12, 8-21 of NP1: Definitions (Eric Vagoda)

P vs NP and NP-complete problems
Watch videos 22-27 of NP1: Definitions (Eric Vagoda)

Satisfiability and other search problems
Homework 5 due
4/17 Read Section 8.3
Watch videos 1-16 of NP2: 3SAT (Eric Vagoda)


4/20 Watch videos 1-11 of NP3: Graph Problems (Eric Vagoda) Reductions (continued)
4/22 Read Section 9.1
Coping with NP-completeness
Homework 6 due
4/24 Backtracking and branch-and-bound

4/27 Read Section 9.2
Approximation algorithms
4/29 Final Review (last day of class)
5/1 FINAL EXAM (2pm)