CSCI 670, Fall 2013


The course is intended as a first Ph.D. course in the design and analysis of algorithms. While the main focus is on known and wellestablished results in the literature, we will also cover topics of potential research interests. The course will give an overview of common techniques, and applications of these techniques in different settings. Students in the class are expected to have a reasonable degree of mathematical sophistication, and to be familiar with the basic notions of algorithms and data structures, discrete mathematics, and probability. Specifically, the following will be assumed:


Professor ShangHua Teng 
Anand Narayanan 

Textbook 
Algorithm Design The class will also cover additional material drawn from research papers as well as other books in Theoretical Computer Science.

Lectures 

Grades 
45%  15% each  Quizzes on homeworks (closed book & notes), Midterm 25% (open book), Final 30% (open book)

Exams 
3 quizzes, midterm and final 
Homeworks 

Integrity 
Plagiarism and other antiintellectual behavior will be dealt with severely. This includes the possibility of failing the course or being expelled from the University. 
Lec# 
Date

Topic and/or Event  Required Reading  "Fun" Research Reading  
1

08/26

Class organization:
Type of Computational Problems
Type of Algorithms
Complexity Theory and Algorithm Analysis 
Chapters 13 Search on the Web. For example: "google P NP" "google linear programming" "google graph partitioning" "google clustering" "google nearest neighbors" "google Nash Equilibrium" "google Page Rank" "google network flow" 
Lipton's brilliant blog: "Goedel's Lost Letter and P=NP"  
2

08/28

Divide and Conquer
Algorithmic View of Proof by Induction Preference and Similarity of Preferences Merge Sort: Review Recurrences: Review A Divide & Conquer Algorithm for Counting Inversions 
Chapter 5  Bentley: Multidimensional divideandconquer, Communications of the ACM, Volume 23 Issue 4, April 1980  
3

09/02

Labor Day (No Class)  
4

09/04

Divide and Conquer
Integer Multiplication Linear Algebra: Review Polynomials representations Evaluation Interpolation Convolution and polynomial multiplication 
Chapter 5  
5

09/09

FFT
Complex numbers Fundamental Theorem of Algebra Machine Learning Perspectives of FFT Discrete Fourier Transform Inverse DFT 
Search on the Web. For example:
"google FFT" "google Discrete Fourier Transform" "google Fourier Transform" "google Fourier Analysis" 

6

09/11

Graph Partitioning and Separator Theorems
Grid graphs Geometric Graphs Planar Graphs
Randomized Algorithms: Planar and Geometric Separator Theorems

Search on the Web for the
research papers:
Lipton and Tarjan: "A Separator Theorem for Planar Graphs," SIAM J. Appl. Math. 36, 177189 (1979), Miller et al: Separators for spherepackings and nearest neighbor graphs, Journal of the ACM, Volume 44 Issue 1, Jan. 1997 Spielman and Teng: Disk Packings and Planar Separators, SCG 96: 12th Annual ACM Symposium on Computational Geometry, pages 349358. 
Spielman and Teng, "Spectral partitioning works: Planar graphs and finite element meshes", Linear Algebra and its Applications Volume 421, Issues 23, 1 March 2007, Pages 284305 (Special Issue in honor of Miroslav Fiedler)  
7

09/16

Geometric Divide and Conquer
Closest pairs Nearest Neighborhood Graph Computation 
Miller et al: Separators for spherepackings and nearest neighbor graphs, Journal of the ACM, Volume 44 Issue 1, Jan. 1997  
8

09/18

Graph Divide and Conquer
Graphs and Matrices Linear Systems Gaussian Elimination Sparse Matrix Computation Graph Theoretical Interpretation of Gaussion Elimination Nested Dissection via Separator Theorems 
Search on the Web for these
research papers
Lipton, Rose, and Tarjan: Generalized nested dissection, SIAM Journal on Numerical Analysis 16 (2): 346358 
Gilbert and Tarjan: The analysis of a nested dissection algorithm, Numerische Mathematik 50 (4): 377404.  
9

09/23

Greedy Algorithms
Merging files, merging lists, Huffman Codes, Mergesort revisit Clustering and Minimum Spanning Trees 
Chapter 4  Balcan, Blum, and Gupta: Approximate clustering without the approximation  
10

09/25

Quiz 1  
11

09/30

Greedy Algorithms
Shortest Paths in a Graph 
Chapter 4  Thorup and Zwick: Approximate distance oracles, ournal of the ACM (JACM), Volume 52 Issue 1, January 2005  
12

10/02

Iterative Algorithms Bubble Sort Network Flow 
Chapter 7  Christiano, Kelner, Madry, Spielman, and Teng: Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs, ACM STOC  
13

10/07

The Duality of Maximum Flow and Minimum Cuts in a Network  Chapter 7  Tom Leighton and Satish Rao: Multicommodity maxflow mincut theorems and their use in designing approximation algorithms, Journal of the ACM, Volume 46 Issue 6, Nov. 1999  
14

10/09

Iterative Algorithms: Matching 
Chapter 7  
15

10/14

Dynamic Programming: Context Free Languages  Chapter 6 
Frances Yao: "SpeedUp in Dynamic Programming", SIAM. J. on Algebraic and Discrete Methods 3, pp. 532540 (former journal of SIAM J. on Matrix Analysis and Applications / Volume 3 / Issue 4)
Arora: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (ACM) 45 (5): 753782 

16

10/16

Dynamic Programming: Optimal Binary Search Trees  Chapter 6  
17

10/21

Midterm  Good Luck  
18

10/23

Dynamic Programming:
LCS: Sequence Alignment 
Chapter 6  
19

10/28

Guest Lecture: Anand Narayanan
Computability
Complexity Theory

Chapter 8 and Web  
20

10/30

Guest Lecture: Anand Narayanan
NP Completeness and PolynomialTime Reduction

Chapter 8  
21

11/04

Guest Lecture: Anand Narayanan (first half if needed)
NP Completeness and PolynomialTime Reduction
Beyond NP (ShangHua Teng)

Chapter 8 and Chapter 9  
22

11/06

Quiz 2  
23

11/11

Approximation Algorithms
Scheduling PARTITION and NPHardness Graham's algorithm 
Chapter 11 (11.1  11.5, 11.8)  
24

11/13

Approximation Algorithms
The Center Selection Problem Mutually Distant Sampling 
Chapter 11 (11.1  11.5, 11.8)  
25

11/18

Approximation Algorithms: Analysis
Set Cover Reduce the Center Selection to Set Cover TSP 
Chapter 11 (11.1  11.5, 11.8)  
26

11/20

Randomized Algorithms  Chapter 13  
27

11/25

Quiz 3  
28

11/27

Thanksgiving (No Class)  
29

12/02

Linear Programming Basic Linear Programming, Randomization, and Approximation 
Chapter 11.6 Michel Goemans's note on Linear Programming and Polyhedral combinatorics 
Raghavan and Thompson, "Randomized rounding: A technique for provably good algorithms and algorithmic proofs", Combinatorica 7 (4): 365374
Goemans and Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM (JACM), 11151145, 1995. 

30

12/04

OnLine Algorithms Parallel Algorithms Streaming Algorithms 

31

12/16 Monday: 810 am

FINAL  Good Luck and make sure to go to bed early enough the night before!  
xx

xx/xx

Materials that I will try to work in Delaunay triangulation and Voronoi Diagram in Two Dimensions 
Ruppert, "A Delaunay Refinement Algorithm for Quality 2Dimensional Mesh Generation", Journal of Algorithms Volume 18, Issue 3, May 1995, Pages 548585  
xx

xx/xx

Materials that I will try to work in Iterative Algorithms for 2D Delaunay triangulation and Voronoi Diagrams 
Guibas, Knuth, and Sharir "Randomized incremental construction of Delaunay and Voronoi diagrams". Algorithmica 7: 381413 