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/17 Read Section 1.3
Primality testing
1/19 Read Section 1.4
Cryptography and RSA

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.4
Mergesort and medians
2/2 Read Section 2.5
Matrix multiplication
Quiz 1 in class

Graph Algorithms

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

2/14 Read Sections 4.1-4.2
DFS 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 Paths
Homework 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)