• 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 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
• Meeting Place: DL480
• Meeting Time: 2:00--3:40  TuTh
• Office Hours: 4:00-5:00TuTh