Courses of Study 2016-2017 
    May 13, 2021  
Courses of Study 2016-2017 [ARCHIVED CATALOG]

Add to Favorites (opens a new window)

CS 4814 - [Introduction to Computational Complexity]

Fall. Not offered 2016-2017. 3 credits.

Prerequisite: CS 4820 .

D. Steurer.

Explores the power and limitations of efficient algorithms. Compares basic models of computations such as finite automata, Boolean circuits, and Turing machines. Illustrates the notion of computational intractability through the concept NP-completeness and the computational foundations of modern cryptography. Investigates the role of randomness and approximation in the modern theory of computing.

Add to Favorites (opens a new window)