Jan 29, 2023  
2014-2015 Graduate Catalog 
    
2014-2015 Graduate Catalog ARCHIVED CATALOG: CONTENT MAY NOT BE CURRENT. USE THE DROP DOWN ABOVE TO ACCESS THE CURRENT CATALOG.

CS 715 - Advanced Analysis of Algorithms


Credits 3

Analysis of the complexity and correctness of asymptotically efficient algorithms, including set partitioning, matrix multiplication, integer multiplication and pattern matching algorithms. The theory of NP-completeness; Cook’s theorem and polynomial transformations. Basic NP-complete problems, such as the three-satisfactory, three dimensional matching and Hamiltonian circuit problems. PSPACE-completeness results, such as quantified Boolean formulas.

Prerequisites
  and