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:
Minicourse on Multithreaded Programming
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)