This course investigates advanced methods, technques, and theories for algorithm analysis and design, especially in coping with the computational intractability of problems in graph, string, geometric, and operations research. Topics include approximation algorithms (semi-definite programming to improve approximation ratios, layer decomposition on planar graphs to achieve approximation schemes, approximation classes and inapproximability results), exact algorithms (parameterized algorithms, tree decomposition based algorithms, branch decomposition on planar graphs, parameterized intractability), randomized algorithms and de-randomization techniques, etc.

CSCI 6470/4470 Algorithms and CSCI 6610 Automata and Formal Languages, or approval of the department.

References:

• Computers and Intractability: A Guide to the Theory of NP-completeness, M. R. Garey and D. S. Johnson, Freeman Publishing, 1979.
  
• Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, 2nd ed, McGraw-Hill, 2001.
  
• Parameterized Complexity, Downey, Rod G. and Fellows, M.R. Springer, 1997.
  
• Approximation Algorithms for NP-Hard Problems, Hochbaum, D. (ed.) PWS, 1997
  
• Randomized Algorithms, Motwani, R. and Raghavan P., Cambridge University Press, 1995.
• Research papers
  

Leading discussions on at least one research paper: 20%
Homework assignments, research projects: 60%
Final exam: 20%

Tentative schedule:

Part I. Review on computational intractability (1 week)
Part II. Exact computation and parameterized algorithms (5 weeks)
Part III. Approximation algorithms and inapproximability (5 weeks)
Part IV. Randomized algorithms (3 weeks)

It is expected that the work you submit is your own. Plagiarism and other forms of academic dishonesty will be handled within the guidelines of the Student Handbook. The usual penalty for academic dishonesty is loss of credit for the assignment in question; however, stronger measures may be taken when conditions warrant.

Attendance policy:

Regular class attendance is required though class attendance may not be used in the final determination of grades. Students are required to attend class during the regularly scheduled tests and the final exam unless prior arrangements have been made.