CSE681, Spring 2012

Formal Languages I: Low-Level Complexity

Instructor:

Dr. Kenneth W. Regan

326 Davis

645-4738

Office hours: TBA

email

Lectures:

MWF 12:00--12:50pm

146 Park Hall

Blog

Syllabus

Lecture Notes

  1. Book Chapters on Computational Complexity for the CRC Handbook on Algorithms and Theoretical Computer Science: Complexity Classes, Reducibility and Completeness, Other Complexity Classes and Measures. These open as 2-column PDF files.
  2. Lecture Notes by Alexis Maciel and David Mix Barrington: Originals here; I have converted them into PDFs conveniently here. The 'B' notes are the more-basic ones and will be selected from first.
  3. Notes for the last part of the course will be selected later.

Assignments

Assignment 1,

Assignment 2, including problems (1) and (2) of the Spring 2010 assignment 2.

Assignment 3, due Mon. Mar. 26.

Assignment 4, due Fri. Apr. 6. Blog notes on ACC.

Assignment 5, due Mon. Apr. 30.

Take-Home Final, due Tue. May 15.