CSE6332
Advanced Algorithms

Instructor: Tamal K. Dey
Content Description : Advanced algorithms that are usually not covered in standard Algorithm course (6331). They include graph algorithms, linear programming, Fourier transforms, string algorithms, approximation algorithms, randomized algorithms, geometric algorithms and such others.
Objectives

Be familiar with advanced topics in algorithms such as the ones listed above
Master a subset of algorithms: Linear programming, advanced graph algorithms, approximation algorithms
Be familiar with how to design algorithms for problems in applications
Be familiar with how to research the background of a topic in algorithms

Prerequisites: CSE6331; or grad standing and permission of instructor
Papers for critique:

Beyond the flow decomposition barrier, A. V. Goldberg and S. Rao, JACM, Vol 45, 783--797, 1998.
Matrix multiplication via arithmetic progression, D. Coppersmith and S. Winograd. J. of Symbolic Computation, 9(3), 1990, 251--280
A strongly polynomial algorithm to solve combinatorial linear programs, E. Tardos, Operations Research, 34(2), 250--256, 1986
Linear-time algorithms for linear programming in R^3 and related problems, N. Megiddo. SIAM J. Computing, 12(4), 759--776, 1983

Materials (Transparencies)

Text and class material	Introduction to Algorithms- T.H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein
Text and class material	Class presentations on transparencies posted on this page may be useful
Topics 1. Network Flow
	a. Flow networks [transparencies]
	b.Augmenting paths, Ford-Fulkerson Algorithm, [transparencies]
	c. Edmonds-Karp algorithm [transparencies]
	d. Push-relabel algorithm [transparencies] (this is O(V^2E) algorithm, not O(VE^2) as the first transparency says)
	e. Maximum bipartite matching [transparencies], Hopcroft-Karp algorithm [WWW]

2. Numerical Algorithms	a. Matrix multiplication [transparencies] b. Operations on polynomials [transparencies] b. DFT and FFT algorithm [transparencies]
3. Linear Programming	a. Framework [transparencies] c. Simplex algorithm [transparencies] d. Duality [transparencies] e. LP rounding and vertex cover [transparencies] f. Randomized LP rounding [transparencies]
4. String Algorithms	a. Rabin-Karp and finite automaton algorithm [transparencies] b. Knuth-Moris-Pratt algorithm [transparencies]
5. Approximation Algorithms	a. Vertex-cover and TSP [transparencies] b. TSP with 1.5-approximation [transparencies] c. Set-cover [transparencies] d. Subset-sum [transparencies]
6. Randomized Algorithms	a. Approx weighted vertex cover [transparencies] b. Randomized max 3-SAT [transparencies] [transparencies] c. Probabilistic Maxcut [transparencies] d. Derandomization of Maxcut [transparencies] e. Radomized MST [transparencies] c. Randomized median finding [pdf]
7. Geometric Algorithms	a. Some preliminaries [transparencies] b. Convex Hull c. Segment intersection [transparencies] d. Closest-pair [transparencies] e. Voronoi-Delaunay diagrams, Flip algorithm [Delaunay Mesh Generation book]

Tentative Class Schedule

Homework

Meeting Place: DL480
Meeting Time: 2:00--3:40 TuTh
Office Hours: 4:00-5:00TuTh
Grading

Homeworks	15%
Presentation on survey topic	35%
Final	40%
Attendance	10%

Deadlines

Term paper : (a) topic selection by Feb. 15 (b) Prelim. draft March 22 (c) submission by April 19

Template for Scribing

Last updated 01/04/19

CSE6332 Advanced Algorithms

CSE6332
Advanced Algorithms