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/24: HW2 revisions are due by 2/8 at 11:59 PM.
• 1/23:
  • HW3 is now posted. It is due by 1/30 at 11:59 PM.
  • Quizzes 3 (Induction) and 4 (Equivalence Relations) are scheduled to open on 1/26. They close on 2/3 at 11:59 PM.
  • Challenge Problems 3 and 4 have been posted. They are due by 4/25 at 11:59 PM.
  • As usual, you are welcome to iterate on Challenge problems as outlined in the announcement on 1/17.
• 1/17:
  • HW1 has been graded.
  • HW1 Corrections and Reflections are due by 2/2 at 11:59 PM to OAKS.
  • You may revise any problem on HW1 for full credit, even if you did not attempt that problem on your initial submission.
  • Please ignore the numbers on Gradescope. The rubric labels are what matter. Grades of Outstanding and Proficiency count equally for full credit.
  • Challenge Problems 1 and 2 have been posted to OAKS. They are due by 4/25 at 11:59 PM.
  • I recommend attempting a Challenge problem every 2-3 weeks, until you hit your desired threshold (see the Syllabus).
  • You are welcome to turn in a Challenge problem, get feedback, and then submit revisions prior to the due date. In particular, you are welcome to do this multiple times for any Challenge problem.
  • Quiz 1- Set Equality and Quiz 2- Functions are scheduled to open on 1/19. They close on 1/26 at 11:59 PM.
  • The quizzes do not count towards the denominator of your grade. So they can help your grade, but not hurt it.
  • I view the quizzes as an opportunity for feedback ahead of the midterm.
• 1/15: PS2 is now posted. It is due on 1/23 at 11:59 PM.
• 1/14:
  • The technology issues appear to be fixed. We will be back in our regular room (HWEA 300) tonight.
  • Update: Unfortunately, the technology issues in HWEA 300 forced us to move to HWW 211 tonight. I am attempting to get these resolved. However, in the interim, it would be best to not rely on Zoom.
  • I will be holding office hours over Zoom, on Friday 1/16 from 2:15-3:15 PM.
  • As the university is closed on 1/19, I will not be holding office hours that day.
• 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.