This course is no longer offered

20365 Computability and Introduction to Complexity 1

Credits: 6 advanced credits in Computer Science

Prerequisites: Students must fulfill all English requirements and take bibliographic instruction in the Library.

Required: Data Structures and Introduction to Algorithms (or Data Structures), Automata Theory and Formal Languages

The course is based on chapters 1-7 and 15 of Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.), by M.D. Davis, R. Sigal, and E.J. Weyuker (Academic Press, 1994).

The course is the upper tier of a series of courses presenting the theoretical foundations of Computer Science on the undergraduate level.

Topics: Computability – programs and computable functions, primitive recursive functions, a universal program, calculations on strings, Turing machines, processes and grammars; Complexity – polynomial-time computability.


1There is some overlap in the content of this and other courses. For details, see Overlapping Courses.