# Data Structures and Algorithms II

#### Integer Arithmetic and RSA Encryption

 8/28 Introduction to the course 8/30 Read Chapter 0 Review of asymptotic notation 9/1 Read Section 1.1 Integer arithmetic

 9/4 Read Section 1.2 Modular arithmetic 9/6 Read Section 1.3 Primality testing 9/8 Read Section 1.4 RSA encryption Programming Assignment 1a due

#### Divide and Conquer

 9/11 Read Section 2.1 Integer multiplication 9/13 Read Section 2.2 Master theorem 9/15 Read Section 2.3 Mergesort Programming Assignment 1b due

 9/18 Read Section 2.4 Medians 9/20 Read Section 2.5 Matrix multiplication Quiz 1 9/22 Fast matrix multiplication Homework 1 due

#### Graph Algorithms

 9/25 Read Section 3.1 Graphs 9/27 Read Sections 3.2-3.3 Depth-first search (DFS) 9/29 Algorithms using DFS Programming Assignment 2a due

 10/2 Read Sections 4.1-4.2 Breadth-first search (BFS) 10/4 Read Sections 4.3-4.4 Dijkstra's Algorithm Quiz 2 10/6 Read Section 4.6 Bellman-Ford Algorithm Programming Assignment 2b due

#### Greedy Algorithms

 10/9 Read Sections 5.1.1-5.1.2 Minimum spanning tree (MST) and cut property 10/11 Read Sections 5.1.3 and 5.1.5 Algorithms for MST 10/13 Fall Break
 10/16 Read Section 5.4 Approximate set cover Homework 2 due 10/18 Midterm review 10/20 IN-CLASS MIDTERM

#### Dynamic Programming

 10/23 Read Sections 6.1-6.2 Elements of DP and Longest Increasing Subsequence 10/25 Read Section 6.3 Edit Distance 10/27 Longest Common Subsequence

 10/30 Read Section 6.4 Knapsack Homework 3 due 11/1 Catch-up day Quiz 3 11/3 Read Section 6.5 Chain Matrix Multiplication Programming Assignment 3a due

#### Parallel Programming

We will be using an alternate textbook for this section: CLRS - Chapter 27