A1-Beveled.gif

CSCI 670, Fall 2017
Advanced Analysis of Algorithms

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

 Course Info:

 


Course descriptions and objectives

In Spring 2015, CS department has decided to make CSCI 670 a required class for all its Ph.D. students. While I personally never prefer to make any class that I teach a required class -- computer science has evolved so rapidly for me or maybe anyone to determine what each successful student should take -- this requirement has inspired me to modernize this class.

In the age of Big Data, efficient algorithms are now in higher demand more than ever before. While Big Data takes computing into the asymptotic world envisioned by our pioneers, it also challenges the classical notion of efficient algorithms: Algorithms that used to be considered efficient, according to polynomial-time characterization, may no longer be adequate for solving today's problems. It is not just desirable, but essential, that efficient algorithms should be scalable. In other words, their complexity should be nearly linear or sub-linear with respect to the problem size. Thus, scalability, not just polynomial-time computability, should be elevated as the central complexity notion for characterizing efficient computation.

This revision -- an evolving project -- has shifted the focus of this class towards "modern" algorithm design and analysis, both in techniques/methodologies and example problems. While the class materials cover mostly known and well-established results in the literature, I will also cover topics of potential research interests. I hope each student will be able to learn something to benefit his/her research.

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, probability, and complexity theory. Specifically, the following will be assumed:

  • Mathematical Proofs, in particular induction and contradiction.
  • Asymptotic 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 basic algorithms: binary search, sorting, median selection.
  • Discrete mathematics: evaluating sums and simple recurrences.
  • Basic complexity theory: Turing machines, computability, NP completeness, polynomial-time reduction.
Undergraduate classes in these subjects should be sufficient. If you have doubts about meeting these prerequisites, please contact the instructor.

This is a theory class. Students will be required and tested not just to design algorithms but also to rigorously characterize their performance. This is also a fast-paced class. If a student does not do the reading assignments and homeworks in a timely fashion, then they will experience limited benefit from the class.


Instructor

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

TA

Ehsan Emamjomeh-Zadeh  
Office hours at Theoroom SAL 2nd floor: TBA
Email: emamjome@usc.edu

Textbook

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

Lectures

14:00 -- 15:50 Monday and Wednesday, in room GFS 116  

Grades

  • 10 points - 5 points - two theoretical thinking projects
  • 45 points - 15 points each - three quizzes on homeworks (closed book & notes)
  • 50 points - 25 points each - midterm and final exams (open book)

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
Topics and/or Events Required Reading "Fun" Research Reading
1
08/21
General Topics:
      Class Organization:
      Theoretical Computer Science

Specific Subjects:
      algorithms and complexity theory: a quick review

***************************************

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
      P-Space, NP, PLS, PPAD
      polynomial-time algorithms
      scalable algorithms

***************************************

Book 1: 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"
      "google scalable algorithms
Lipton's brilliant blog: "Goedel's Lost Letter and P=NP"
2
08/23
General Topics:
      Algorithms and Heuristics
Specific Subjects:
      merging files, merging lists, Huffman codes, mergesort revisit
      clustering and minimum spanning trees
Algorithmic Techniques:
      greedy algorithms
Mathematical Concepts:
      prefix-free codes
      minmum spanning trees
      low-stretch spanning trees
Book 1: Chapter 4 Noga Alon, Richard M. Karp, David Peleg, and Douglas West, A Graph-Theoretic Game and Its Application to the k-Server Problem

Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng Lower-Stretch Spanning Trees

3
08/28
General Topics:
      Graph Algorithms
Specific Subjects:
      shortest paths in a graph
Algorithmic Techniques:
      greedy algorithms
Mathematical Concepts:
      shortest path
      graph metrics
      network routing
Book 1: Chapter 4 Thorup and Zwick: Approximate distance oracles, ournal of the ACM (JACM), Volume 52 Issue 1, January 2005
4
08/30
General Topics:
      Network Analysis
Specific Subjects:
      social influence
Algorithmic Techniques:
      greedy algorithms
      submodular function maximization
Mathematical Concepts:
      network process
      triggering models
      submodular functions
David Kempe, Jon Kleinberg, and Eva Tardos, Maximizing the Spread of Influence through a Social Network

George Nemhauser, Laurence Wolsey, and Marshall Fisher: An analysis of the approximations for maximizing submodular set functions I. Mathematical Programming, 14(1), 265-294, 1978

Andreas Krause, Submodular Function Maximization
Theorem 1.5 (Page 6-7)

Christian Borgs, Michael Brautbar, Jennifer Chayes, Brendan Lucier, Maximizing Social Influence in Nearly Optimal Time

Y. Tang, X. Xiao, and Y. Shi. Influence maximization: near-optimal time complexity meets practical efficiency. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD, pages 75-86, 2014

Y. Tang, Y. Shi, and X. Xiao. Influence maximization in near-linear time: A martingale approach. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD, pages 1539-1554, 2015

Wei Chen, Shang-Hua Teng, Interplay between Social Influence and Network Centrality: Shapley Values and Scalable Algorithms

5
09/04
Labor Day (No Class)    
6
09/06
General Topics:
      Optimization and Approximation
Specific Subjects:
      set cover
Algorithmic Techniques:
      greedy algorithms
Mathematical Concepts:
      potential analysis
Book 1: Chapter 11 (11.1 -- 11.5, 11.8)  
7
09/11
General Topics:
      Geometric Data
Specific Subjects:
      clustering
      dimension reduction
Algorithmic Techniques:
      iterative algorithms
      local search; potential games
Mathematical Concepts:
      Voronoi diagrams
      well-separated clusters
      outliers
      clustering stability
      singular value decomposition
S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129-137, 2006

Search on the Web. For example:
      "google Voronoi diagram"
      "google SVD"
      "google dimension reduction"
      "google potential games"
      "google Polynomial Local Search (PLS)"

D. Arthur, B. Manthey, and H. RoLlin. Smoothed analysis of the k- means method. Journal of the ACM, 58(5), 19:1-19:31, 2011

Balcan, Blum, and Gupta: Approximate clustering without the approximation

8
09/13
2:00-3:00pm: Quiz 1

3:00-3:50pm: Discussion: network centrality

   
9
09/18
General Topics:
      Geometric Data
Specific Subjects:
      robust statistics
      median and extensions
Algorithmic Techniques:
      sampling and randomization
      local data analysis
      evolutionary algorithms
Mathematical Concepts:
      centerpoints
      VC dimensions
      tail analysis
      convex geometry: the theorems of Radon and Helly
Book 2: Chapter 5 V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16, 264-280, 1971

M. Hubert and P. J. Rousseeuw. The catline for deep regression. J. Multivariate Analysis, 66:270-296, 1998

N. Amenta, M. Bern, D. Eppstein, and S.-H. Teng. Regression depth and center points. Discrete & Computational Geometry, 23(3), 305-323, 2000

10
09/20
General Topics:
      Geometric Data
Specific Subjects:
      geometric divide and conquer
Algorithmic Techniques:
      divide and conquer
      generalized binary search
Mathematical Concepts:
      NNG
      point location data structures
Book 2: Chapter 5

Miller, Teng, Thurston, Vavasis: Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM, Volume 44 Issue 1, Jan. 1997

Bentley: Multidimensional divide-and-conquer, Communications of the ACM, Volume 23 Issue 4, April 1980

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.

11
09/25
General Topics:
      Geometric Data
Specific Subjects:
      geometric separators and clustering
      geometric graphs: grids, nearest neighbor graphs (NNG), planar graphs, and meshes
Algorithmic Techniques:
      sampling and randomization
      divide and conquer
Mathematical Concepts:
      planar and geometric separator theorems
      geometric duality
      Koebe embedding and the lake problem
      geometric duality
      Delaunay triangulations
Book 2: Chapter 5

Lipton and Tarjan: "A Separator Theorem for Planar Graphs," SIAM J. Appl. Math. 36, 177-189 (1979)

Miller, Teng, Thurston, Vavasis: 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)
12
09/27
General Topics:
      FFT
Specific Subjects:
      machine learning perspectives of FFT
      Discrete Fourier Transform
      inverse DFT
Algorithmic Techniques:
      divide and conquer
      algorithmic view of proof by induction
Mathematical Concepts:
      complex numbers
      Fundamental Theorem of Algebra
Book 1: Chapter 5
Search on the Web. For example:
      "google FFT"
      "google Discrete Fourier Transform"
      "google Fourier Transform"
      "google Fourier Analysis"
 
13
10/02
General Topics:
      FFT
Specific Subjects:
      integer multiplication
Algorithmic Techniques:
      divide and conquer
Mathematical Concepts:
      linear algebra: review
      polynomials
            representations
            evaluation
            interpolation
      convolution and polynomial multiplication
Book 1: Chapter 5
Search on the Web. For example:
      "google FFT"
      "google Discrete Fourier Transform"
      "google Fourier Transform"
      "google Fourier Analysis"
 
14
10/04
General Topics:
      Graph Algorithms
Specific Subjects:
      maximum flow and minimum cuts in a network
Algorithmic Techniques:
      iterative algorithms
Mathematical Concepts:
      linear programming duality
Book 1: 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
15
10/09
Midterm: good luck    
16
10/11
Guest Lecture: Ehsan Emamjomeh-Zadeh
General Topics:
      Binary Search in Graphs
TBA TBA
17
10/16
Guest Lecture: Ehsan Emamjomeh-Zadeh
General Topics:
      Interactive Learning
TBA TBA
18
10/18
Quiz 2    
19
10/23
General Topics:
      Network Analysis
Specific Subjects:
      network centrality
      PageRank; personalized PageRank
Algorithmic Techniques:
      sampling and randomization
      local network exploration
      simulated annealing
Mathematical Concepts:
      Markov chain
      matrix powers
      random-walk matrix polynomials
Book 2: Chapter 3 S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks, 30(1-7), 107-117, 1998
20
10/25
General Topics:
      Network Analysis
Specific Subjects:
      significant PageRank identification
Algorithmic Techniques:
      sampling and randomization
      local network exploration
      simulated annealing
Mathematical Concepts:
      personalized PageRank matrix
      centrality conforming Markov chain
Book 2: Chapter 3
21
10/30
General Topics:
      Spectral Graph Theory
Specific Subjects:
      Laplacian matrices
Algorithmic Techniques:
      spectral method
Mathematical Concepts:
      clusterability
      conductance
      spectral embeddings
      Rayleigh quotient
Book 2: Chapter 4

M. Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathemat- ical Journal, 23(2):298 - 305, 1973

F. R. K. Chung. Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92). American Mathematical Society, Feb. 1997.

22
11/01
General Topics:
      Spectral Graph Theory
Specific Subjects:
      graph partitioning
Algorithmic Techniques:
      sweep and spectral partitioning
      local clustering algorithms
Mathematical Concepts:
      Cheeger's inequality
Book 2: Chapter 4
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)

Frank McSherry, Spectral Partitioning of Random Graphs, FOCS '01

23
11/06
General Topics:
      Spectral Graph Theory
Specific Subjects:
      scalable Laplacian paradigm
Algorithmic Techniques:
      SDD solvers
Mathematical Concepts:
      spectral approximation
      learning on graphs
Book 2: Chapter 7
J. Batson, D. A. Spielman, N. Srivastava, and S.-H. Teng. Spectral sparsification of graphs: Theory and algorithms. Communications of the ACM, 56(8):87-94, Aug. 2013.

Ioannis Koutis, Gary L. Miller, Richard Peng, A fast solver for a class of linear systems, Communications of the ACM CACM, Volume 55 Issue 10, October 2012 Pages 99-107

N. K. Vishnoi. Lx = b. Foundations and TrendsbR in Theoretical Com- puter Science, 8(1-2):1-141, 2013.

24
11/08
General Topics:
      Advanced Sampling
Specific Subjects:
      graph and metric embedding
      spectral sparsification
Algorithmic Techniques:
      sampling and projection
Mathematical Concepts:
      Johnson-Lindenstrauss low-distortion embeddings
W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26, 189-206, 1984  
25
11/13
General Topics:
      Advanced Sampling
Specific Subjects:
      spectral sparsification
Algorithmic Techniques:
      effective resistance based sampling
Mathematical Concepts:
      spectral similarity
      effective resistances
Book 2: Chapter 6
D. A. Spielman and N. Srivastava. Graph sparsification by effective resistances. In Proceedings of the 40th ACM Symposium on the Theory of Computing, pages 563-568, 2008.
26
11/15
2:00-3:00pm: Quiz 3

3:00-3:50pm: Discussion
      random projection vs spectral projection

Book 2: Chapter 5  
27
11/20
General Topics:
      Optimization and Approximation
Specific Subjects:
      mathematical programming
Algorithmic Techniques:
      linear programming
Mathematical Concepts:
      convex optimization
      linear programming basics
Book 1: 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.

28
11/22
Thanksgiving (No Class)    
29
11/27
General Topics:
      Optimization and Approximation
Specific Subjects:
      mathematical programming
Algorithmic Techniques:
      multiplicative weight updates
Mathematical Concepts:
      convex optimization
      linear programming basics
Book 1: Chapter 11.6
The Multiplicative Weights Update Method: a Meta Algorithm and Applications Sanjeev Arora, Elad Hazan, and Satyen Kale
 
30
11/29
General Topics:
      algorithm analysis
Specific Subjects:
      beyond worst case analysis
Algorithmic Techniques:
      input and solution characterizations
Mathematical Concepts:
      instance-based complexity
      output-sensitive algorithm
      smoothed analysis
      algorithmic condition numbers
Book 2: Chapter 8
Daniel A. Spielman, Shang-Hua Teng, Smoothed Analysis: An Attempt to Explain the Behavior of Algorithms in Practice Communications of the ACM, Vol. 52 No. 10, Pages 76-84
31
12/08
Final December 8, 2017, 2-4pm Good Luck