CSCI 410/CSIS 616 Automata Theory (Spring 2024)

Contact Information

Announcements

  • 4/22: HW10 reflections are due on 5/1 at 11:59 PM.
  • 4/15: HW11 has been posted. It consists only of challenge problems. It is due on 5/1 at 11:59 PM. However, if you turn it in reasonably early, I will work to have feedback to you in case you wanted to revise. Note that I must submit final grades to the Registrar by 5/6 at noon, and this is a hard deadline.
  • 4/11:
    • Students in 616 need only complete 4 challenge problems for an A, 3 for an A-, 2 for a B+, 1 for a B, and 0 for a B-.
    • There will be no final reflection.
  • 4/9: HW9 revisions are due on 4/26 at 11:59 PM.
  • 4/3: PS10 has been posted. It will be due on 4/19 at 11:59 PM. There are four problems for everyone (Problem 4 is broken up into two chunks for grading), and two additional grad problems. Students in 410 will have 3 added to their denominator, and students in 616 will have 5 added to their denominator. I hope this is helpful in giving you all some breathing room.
  • 4/1: MT2 will run from April 7 through April 17. It consists of 9 questions, each of which will be its own OAKS quiz. Students in 410 will be have 6 questions added to their denominator. Students in 616 will have 8 questions added to their denominator. MT2 will primarily emphasize the content on regular languages and CFLs. Turing Machines and Decidability will be lightly assessed. You should be familiar with the existence of undecidable problems, though you will not be asked to deal with reductions.
  • 3/30:
    • HW8 revisions are due on 4/15 at 11:59 PM.
    • I have extended the deadlines for the challenge problems to 5/1 at 11:59 PM. Please note that final grades are due on 5/6 by noon.
  • 3/21: HW9 is now posted. It is due on 4/1 at 11:59 PM. Despite the due date, I did not ask you all to resolve the P vs. NP problem.
  • 3/16:
    • HW8 is now posted. It is due on 3/25 at 11:59 PM.
    • HW7 revisions are due on 3/31 at 11:59 PM.
  • 3/11: PS6 revisions are due on 3/18 at 11:59 PM.
  • 3/9:
    • For HW7, Problem 2, there was a typo. The diagram is an NFA, but should be a DFA. I updated the file on OAKS to clarify.
    • For HW7, Problem 4, note that wR denotes the reverse of w. I added a clarifying sentence on Problem 4.
    • Challenge Problems 5-8 have been posted. Note that for Challenge Problems 5-7, there is one problem set with 6 parts. Every two parts yields credit for one challenge problem.
  • 2/28: HW5 has been graded. Revisions are due on 3/19 at 11:59 PM (to avoid conflicting with HW7).
  • 2/28: HW7 is now posted. It is due on 3/15 at 11:59 PM.
  • 2/23: MT1 is now scheduled as a series of 6 quizzes. While there is not explicitly a quiz on functions, they may be assessed as part of other quizzes.
  • 2/15: HW6 is now posted. It is due on 3/1 at 11:59 PM. HW6 is not particularly long; rather, with the midterm and your other classes, I hope this gives you all some breathing room.
  • 2/14:
    • HW3 and HW4 revisions are both due on 3/12 at 11:59 PM. This way, they will not interfere with the Midterm or Spring break, though it may be advisable to try and complete them as a way of studying for the Midterm.
    • Quiz 7 over Regular Expressions and Finite State Machines opens on 2/16 and closes on 2/23 at 11:59 PM.
  • 2/8:
    • HW5 is now posted. It is due on 2/16 at 11:59 PM.
    • Midterm 1 will run from 2/25 through 3/2 at 11:59 PM. It will consist of a series of OAKS quizzes; that is, each question will be its own OAKS quiz (similar in format to the weekly quizzes). Midterm 1 will cover through HW5.
  • 1/31:
    • HW4 has been posted. It is due on 2/6 at 11:59 PM.
    • Quizzes 5-6 over Combinatorics and Graph Theory, respectively, open on 2/2 and close on 2/9 at 11:59 PM.
  • 1/29: My office hours for tomorrow 1/30 have been rescheduled to 3-3:50.
  • 1/24:
    • HW2 has been graded. Revisions are due on 2/8 at 11:59 PM. Please include detailed reflections with your revisions.
    • HW3 has been posted. It is due on 1/30 at 11:59 PM.
    • Challenge problems 3-4 have been posted.
    • Quizzes 3-4 over Induction and Equivalence Relations respectively open on 1/26 and close on 2/2 at 11:59 PM.
    • Please plan to bring your
  • 1/17:
    • PS1 has been graded. Revisions are due on 2/1 at 11:59 PM. For each problem that you revise, please include reasonably detailed reflections addressing gaps in your understanding and how you addressed them. These do not have to be long, but they should be clear, direct, and precise.
    • There will be two quizzes, over Set Equality Proofs and Functions respectively. The quizzes open on 1/19 and close on 1/26 at 11:59 PM. Quizzes count towards the numerator of your grade, but not the denominator. The quizzes are intended to serve as timely feedback ahead of the midterm. So it might be worth taking advantage of these.
  • 1/15:
    • PS2 will open on 1/16. It is due on 1/23 at 8 PM.
    • Challenge Problems 1 and 2 have been posted. I recommend completing one challenge problem every 2-3 weeks, but of course you are welcome to do them as you see fit.
  • 1/10:
    • PS1 is now posted. 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.
    • 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.
  • 12/12:
    • 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.