CSCI 410/CSIS 616 Automata Theory (Spring 2026)

Contact Information

• Instructor: Michael Levet (He/Him/His)
  • Contact: lastnamefirstinitial (at) cofc (dot) edu
  • Office: Harbor Walk East 312
  • Location:
    • HWEA 300 (Wednesdays 5:30-8:15 PM)
    • Zoom- Remote Synchronous, for those who wish to participate remotely.
  • Office Hours (Tentative):
    • Monday 9:30-10:30 AM; Tuesday 3-4 PM (Zoom)
    • By appointment
• CSCI 410 Syllabus
• CSIS 616 Syllabus
• Syllabus Companion (=TeX'd up version of the Syllabi)
• Course Textbook
• Google Forms: (You must be signed in to your CofC account to access these forms.)
  • Google Drive
  • Extension Request
  • Regrade Request
  • Anonymous Feedback

Announcements

• 1/7:
  • PS1 is now posted. It is due on 1/16 at 11:59 PM, to explicitly avoid conflicts with the meeting time for CSIS 605.
  • For CSCI 410 students, PS1 adds 8 problems to the denominator, and you can earn credit for all 9 problems towards your numerator. For CSIS 616 students, PS1 adds 9 problems to the denominator.
  • The handwritten notes from today are in the Google Drive. We stated, but did not prove, that the congruence mod-n relation was an equivalence relation. We will start with the proof next class.
• 1/3:
  • In order to prepare homework and quizzes, you will need a tool to convert LaTeX source files into PDFs. I use MikTeX on my local machine (Windows). Overleaf is an online option; note that Overleaf is an interpreter and will sometimes push past compilation errors (this is not a good thing).
  • Please fill out this Day One survey. It is optional, and is intended to help me get to know you all and plan the course.
• 1/2:
  • Website created. I am looking forward to proving beautiful theorems with you all next semester!
  • The official course text will be my lecture notes (linked above). If you would like a supplemental text, I recommend the following:
    • Sipser-- the third edition is the most recent, but the second edition will suffice. In particular, Sipser's text is the standard for similar courses at other institutions. It's a very readable book that provides solid intuition.
    • Introduction to Automata Theory, Languages, and Computation, First Edition (see here). The First Edition is targeted towards graduate students and researchers in theoretical computer science, back in the 70's when the field was getting off the ground. The second and third editions took out all the good stuff.
    • Savage's text, specifically Chapters 4-5. Chapters 2-3 would make an excellent theoretical course in Digital Logic-- Savage is after the NC hierarchy in these earlier chapters, but does not use this language.
    Be aware that my treatment and notation will differ in minor ways from these books. This is unavoidable at a course of this level.