18.404J | Fall 2020 | Undergraduate, Graduate Theory Of Computation

• Syllabus • Calendar • Instructor Insights • Readings • Lecture Notes • Video Lectures • Assignments • Exams

Course Description

This course emphasizes computability and computational complexity theory. Topics include regular and context-free languages, decidable and undecidable problems, reducibility, recursive function theory, time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, …Show more

Course Info

INSTRUCTOR

• Prof. Michael Sipser

DEPARTMENTS

• Mathematics
• Electrical Engineering and Computer Science

TOPICS

• Engineering
  • Computer Science
    • Theory of Computation
• Mathematics

LEARNING RESOURCE TYPES

theatersLecture Videos

assignmentProblem Sets

gradingExams

notesLecture Notes

co_presentInstructor Insights