| |
Dec 28, 2024
|
|
|
|
|
2024-2025 Graduate 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
|
|