# DATA STRUCTURES AND ALGORITHMS II

#### Cryptography

 1/10 Introduction to the course, computing Fibonacci numbers, review of big Oh notation 1/12 Read Sections 1.1 and 1.2 Modular arithmetic Programming Assignment 1 posted on Sakai

 1/24 Finish up RSA

#### Divide and Conquer

 1/26 Read Sections 2.1-2.2 Multiplication and recurrence relations Programming Assignment 1 Due

 1/31 Read Sections 2.3-2.4Mergesort and medians 2/2 Read Section 2.5 Matrix multiplication Quiz 1 in class

#### Graph Algorithms

 2/7 Read Sections 3.1-3.3Graphs and DFS 2/9 Algorithms using DFSHomework 1 Due

 2/14 Read Sections 4.1-4.2DFS and BFS 2/16 Read Section 4.3-4.4 Dijkstra's Algorithm Quiz 2 in class

#### Greedy Algorithms

 2/21 Read Section 5.1 Minimum Spanning Tree 2/23 Read Section 5.4 Set Cover Programming Assignment 2 Due

#### Midterm

 2/28 Midterm Review 3/2 IN-CLASS MIDTERM

 3/7 Spring Break 3/9 Spring Break

#### Dynamic Programming

 3/14 Read Sections 6.1-6.2 Elements of DP and Longest Increasing Subsequence 3/16 Read Section 6.3 Edit Distance and Longest Common Subsequence Quiz 3 in class

 3/21 Read Sections 6.4-6.5 Knapsack and Chain Matrix Multiplication 3/23 Read Section 6.6 Floyd-Warshall - All-Pairs Shortest PathsHomework 2 Due 3/24

#### Parallel Programming

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

 3/28 Read Section 27.1 Parallel Random Access Machine model 3/30 Read Section 27.2 Multithreaded matrix multiplication Quiz 4 in class

 4/4 Read Section 27.3 Multithreaded mergesort 4/6 Memory models and data movement Programming Assignment 3 Due

#### NP-complete Problems

 4/11 Read Sections 8.1-8.2 P vs NP and NP-complete problems 4/13 Read Section 8.3 Reductions Quiz 5 in class

 4/18 Read Section 9.1 Coping with NP-completeness 4/20 Read Section 9.2 Approximation algorithms Homework 3 Due

 4/25 Final Review (last day of class)

 4/29 FINAL EXAM (9am)