A1-Beveled.gif

CSCI 670, Fall 2013
Advanced Analysis of Algorithms

=================================================

What's new?

 =================================================

 Course Info:

 


Course descriptions and objectives

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 well-established 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:

  • Mathematical Proofs, in particular induction and contradiction.
  • Big-Oh notation (Big-O, Omega, Theta), how to apply them.
  • Basic data structures: arrays, linked lists, trees, balanced trees, heaps (priority queues), graphs.
  • Basic graph algorithms: connected components, BFS, DFS.
  • Other algorithms: binary search, sorting.
  • Discrete mathematics: evaluating sums and simple recurrences.
Undergraduate classes in these subjects should be sufficient. If you have doubts about meeting these prerequisites, please contact the instructor.


Instructor

Professor Shang-Hua Teng
Office hours at RTH 402: Monday 1:00-1:50 pm or by appointment;
Email : shanghua[]usc.edu

TA

Anand Narayanan  
Office hours: TBA
Email: aknaraya[]usc.edu

Textbook

Algorithm Design
Jon Kleinberg and Eva Tardos

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

Lectures

10:00 -- 11:25am Monday and Wednesday, in room VKC 203.  

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 anti-intellectual behavior will be dealt with severely. This includes the possibility of failing the course or being expelled from the University. 

 

Course Outline (subject to changes)

Lec#
Date
Topic and/or Event Required Reading "Fun" Research Reading
1
08/26
Class organization:

Type of Computational Problems
      Decision
      Search
      Optimization
      Games, puzzles, and interactions
      Game theory and dynamics

Type of Algorithms
      Sequential
      Parallel
      Distributed
      On-line

Complexity Theory and Algorithm Analysis

Chapters 1-3
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 divide-and-conquer, 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
      Koebe Embedding
      The Lake Problem
      Duality on Sphere
      Centerpoint
      How many lakes can a random great circle cross

Search on the Web for the research papers:
      Lipton and Tarjan: "A Separator Theorem for Planar Graphs," SIAM J. Appl. Math. 36, 177-189 (1979),
      Miller et al: Separators for sphere-packings 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 349-358.
Spielman and Teng, "Spectral partitioning works: Planar graphs and finite element meshes", Linear Algebra and its Applications Volume 421, Issues 2-3, 1 March 2007, Pages 284-305 (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 sphere-packings 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): 346-358
Gilbert and Tarjan: The analysis of a nested dissection algorithm, Numerische Mathematik 50 (4): 377-404.
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 max-flow min-cut 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: "Speed-Up in Dynamic Programming", SIAM. J. on Algebraic and Discrete Methods 3, pp. 532-540 (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): 753-782

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
      Turing Machine
      Computable Functions
      Godel indexing and Godel numbers
      Halting Problem and Diagonalization Proofs

Complexity Theory
      NP and P
      Polynomial-Time Reduction

Chapter 8 and Web  
20
10/30
Guest Lecture: Anand Narayanan

NP Completeness and Polynomial-Time Reduction
      NPC
      3SAT
      CLIQUE

Chapter 8  
21
11/04
Guest Lecture: Anand Narayanan (first half if needed)

NP Completeness and Polynomial-Time Reduction
      SUBSET SELECTION
      PARTITION

Beyond NP (Shang-Hua Teng)
      PSPACE and Board Games
      Interactive Proofs and NP

Chapter 8 and Chapter 9  
22
11/06
Quiz 2    
23
11/11
Approximation Algorithms
      Scheduling
      PARTITION and NP-Hardness
      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): 365-374

Goemans and Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM (JACM), 1115--1145, 1995.

30
12/04
On-Line Algorithms
Parallel Algorithms
Streaming Algorithms
   
31
12/16 Monday: 8-10 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 2-Dimensional Mesh Generation", Journal of Algorithms Volume 18, Issue 3, May 1995, Pages 548-585
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: 381-413