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

 2/3 Read Section 2.4 Watch Randomized Selection (Tim Roughgarden) Median/Select 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) Graphs 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/6 IN-CLASS MIDTERM

 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) Knapsack

 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 4/15 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) Reductions

 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)