15-559: Independent Study in Theoretical Computer Science

Course Calendar

Week Topic   Assignments  
1

Jan. 10 - 14
 Computational Complexity:

Selection, Insertion and Shell Sorts
Complexity of sorting in general
 
2 - 3

Jan. 17 - 27
 Solving Difference Equations:

First Order Recurrences
Higher Order Linear Recurrences
Solution to Binary Search Recurrence
Solution to MergeSort Recurrence  
hw - 1
4 - 5

Jan. 31 - Feb. 11
 Generating Functions:

OGF and EGF
Solution to QuickSort Recurrence
OGF in combinatorics  
hw - 2
6 - 8

Feb. 14 - Mar. 04
 Divide-and-Conquer:

Multiplication (Karatsuba, Toom-Cook)
Exponentiation
Matrix Multiplication (Strassen)
Shamir's Algorithm for n!
Polynomial Multiplication (using the FFT)  
hw - 3

write-up
  Spring Break  
9 - 10

Mar. 14 - 25
 Probabilistic Algorithms:

Complexity of QuickSort
Hashing  
 
11 - 12

Mar. 28 - Apr. 08
 Dynamic Programming:

0-1 Knapsack Problem
Chain Matrix Multiplication
Floyd's Algorithm
Approximate String Matching  
hw - 4

write-up
13 - 14

Apr. 11 - 22
 Greedy Algorithms:

Matrix Multiplication
Shortest Paths
Minimum Spanning Tree
Network Flows  
write-up
15

Apr. 25 - 29
 Final Project:

Undirected SSSP in Linear Time  
 

Victor S. Adamchik
Computer Science Department, 
Carnegie Mellon University, Pittsburgh, PA.