# Data Structures and Algorithms II

#### Integer Arithmetic and RSA Encryption

 1/14 Introduction to the course 1/16 Read Chapter 0 and Section 1.1 Review of asymptotic notation and integer arithmetic 1/18 Finish integer arithmetic

 1/21 MLK Day: No class 1/23 Read Section 1.2 Modular arithmetic 1/25 Read Section 1.3 Primality testing

#### Divide and Conquer

 1/28 Read Section 1.4 RSA encryption Programming Assignment 1a due 1/30 Read Section 2.1 Integer multiplication 2/1 Read Section 2.2 Master theorem Quiz 1

 2/4 Read Section 2.3 Mergesort Programming Assignment 1b due 2/6 Read Section 2.4 Medians 2/8 Read Section 2.5 Matrix multiplication Homework 1 due

#### Graph Algorithms

 2/11 Read Section 3.1 Graphs 2/13 Read Sections 3.2-3.3 Depth-first search (DFS) 2/15 Algorithms using DFS Programming Assignment 2a due

 2/18 Read Sections 4.1-4.2 Breadth-first search (BFS) 2/20 Read Sections 4.3-4.4 Dijkstra's Algorithm Quiz 2 2/22 Read Section 4.6 Bellman-Ford Algorithm Programming Assignment 2b due
 2/25 Midterm review 2/27 IN-CLASS MIDTERM 3/1 No class

#### Greedy Algorithms

 3/4 Read Sections 5.1.1-5.1.2 Minimum spanning tree (MST) and cut property 3/6 Read Sections 5.1.3 and 5.1.5 Algorithms for MST 3/8 Read Section 5.4 Approximate set cover Homework 2 due

 3/11 Spring Break: No class 3/13 Spring Break: No class 3/15 Spring Break: No class

#### Dynamic Programming

 3/18 Read Sections 6.1-6.2 Elements of DP and Longest Increasing Subsequence 3/20 Read Section 6.3 Edit Distance 3/22 Longest Common Subsequence

 3/25 Read Section 6.4 Knapsack Homework 3 due 3/27 Read Section 6.5 Chain Matrix Multiplication Quiz 3 3/29 Catch-up day Programming Assignment 3a due

#### Parallel Programming

We will be using alternate materials for this section:
Lecture 1 (Leiserson)
Lecture 2 (Leiserson)

 4/1 Read Section 1 of Minicourse PRAM model, performance measures, and thread scheduling 4/3 Read Section 2 of Minicourse Analyzing parallel algorithms: matrix multiplication 4/5 Analyzing parallel algorithms: merge sort

 4/8 Review of matrix multiplication and merge sort Programming Assignment 3b due 4/10 Floyd-Warshall and multithreaded all-pairs shortest paths 4/12 Memory models and data movement

#### NP-complete Problems

 4/15 Read Sections 8.1-8.2 P vs NP and NP-complete problems Homework 4 Due 4/17 Satisfiability and other search problems Quiz 4 4/19 Good Friday: No class

 4/22 Read Section 8.3 Reductions 4/24 Reductions (continued) 4/26 Read Section 9.1 Coping with NP-completeness

 4/29 Backtracking and branch-and-bound Homework 5 Due 5/1 Final Review (last day of class)

 5/8 FINAL EXAM (2pm)