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.