University of Minnesota
CSCI4011: Automata, Computability & Complexity
  • 12/12 The location of the final examination has been posted on the calendar.

  • 12/1 The seventh assignment has been posted.

  • 11/16 The sixth assignment has been posted.

  • 11/2 The fifth assignment has been posted.

  • 10/24 The fourth assignment has been posted.

  • 10/24 The provisional final exam date and time have been replaced on the calendar; please note the change. The location will be posted as soon as it becomes available.

  • 10/17 The midterm exam will be confined to chapter 1 and §2.1 of the class textbook. You will NOT be asked to convert a grammar to Chomsky Normal Form.

  • 10/5 The third assignment has been posted.

  • 9/21 The second assignment has been posted.

  • 9/19 TiaTia's office hours are henceforth in Keller 1-201.

  • 9/14 The first assignment has been posted.

  • 9/1 Note that there is no discussion held the first week of teaching.

  • 9/1 Make sure that you can attend the midterm and the final examinations using the Examination Schedule in accordance with the syllabus.

  • 9/1 The Assignment Calendar contains links to the assignments. These are not yet specified. When an assignment is posted, an announcement will be made, and its link in the Assignment Calendar will become active.

  • 9/1 The links on the left “Submit Assignment” and “Grading and Grades” are not yet operational.

  • 9/1 Read the syllabus closely—you will be assumed to have done this: ignorance is not an excuse.

  • Welcome to the theory of computation. Here you will find out something about the underlying nature of computation. In an algorithms class you learn techniques that may lead to solutions when they exist. However, some problems provably do not have solutions, as in the rest of mathematics. Here a solution is an algorithm satisfying specified requirements. This class is about when solutions do and do not exist. This class is necessary for anyone who later goes to graduate school in computer science, computer engineering or software engineering.