CS 572 - Computability & Computational Complexity

Credits: 4
Emphasis on the limits to the power of computation and a systematic analysis of the algorithms that harness it. Computability topics include the Chomsky hierarchy, several automata and language models, and demonstrations of incomputable problems. Complexity topics include various design strategies such as greedy, divide and conquer, and backtracking, and fundamental computing algorithms, such as searching, sorting, graphs, trees, pattern matching, and computational geometry, with a short foray into distributed algorithms.