University of Minnesota
CSCI4011: Automata, Computability & Complexity
  • 12/12 The location of the final exam is posted on the assignment calendar.

  • 11/30 The final examination will cover chapters 1,2(§2.1 only),3,4,5,7 of the book.

  • 11/30 The seventh homework assignment has been posted.

  • 11/17 The sixth homework assignment has been posted.

  • 11/2 The fifth homework assignment has been posted.

  • 10/26 The fourth homework assignment has had its due date extended by one week, to 11/3.

  • 10/19 The midterm will be confined to the material covered from chapters 1 & 2 of the book.

  • 10/19 The fourth homework assignment has been posted.

  • 10/5 The third homework assignment has been posted.

  • 9/23 The second homework assignment has been posted.

  • 9/20 Registration is closed, so you have been added to Gradescope and should have received an automated email to that effect, telling you how to log in. The links “Submit Assignment” and “Grading and Grades” on this site are now functional.

  • 9/14 The first homework assignment has been posted.

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

  • 9/5 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/5 The links on the left “Submit Assignment” and “Grading and Grades” are not yet operational.

  • 9/5 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. The class will be taught on campus and no recording of lecture will be made.