CS 372 - Computability and Computational Complexity

Institution:

Valparaiso University

Subject:

Computer Science

Description:

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 uncomputable 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. Prerequisites: CS 257 and MATH 269.

Credits:

4.00

Credit Hours:

Prerequisites:

CS-257 AND MATH-269

Corequisites:

Exclusions:

Level:

Instructional Type:

Lecture

Notes:

Additional Information:

Historical Version(s):

Institution Website:

valpo.edu

Phone Number:

(219) 464-5000

Regional Accreditation:

North Central Association of Colleges and Schools

Calendar System:

Semester

The Course Profile information is provided and updated by third parties including the respective institutions. While the institutions are able to update their information at any time, the information is not independently validated, and no party associated with this website can accept responsibility for its accuracy.