Overview

CSCI101 is an introduction to languages and the theory of computation. The course investigates models of computation such as finite-state automata and Turing machines, formal languages such as context free grammars, and computability. Connections to applications such as lexical analysis and parsing will be explored. Along the way there will be proof-writing and coding.

The prerequisite for the class is CSCI054. CSCI062 is a co-requisite. You should not be taking (will not receive credit for) this class if you have already taken CSCI081. Send the professors (Prof. Chen and Prof. Zlatin) an email if you have questions about these requirements.

Resources

The professors for this class are Professor Chen and Professor Zlatin. We're happy to talk about the class, about theory, or about CS more generally. Our office hours are Mon 10-11am (Zlatin), Tues 1:30-3pm (Chen), Thu 2:40-4pm (Zlatin), and Fri 1:30-2:30 (Chen). We are also both happy to meet at other times by appointment. Prof. Chen is additionally available for occasional small group lunches/dinners (the sign-up sheet is on her office door) if you'd just like to chat sometime.

The mentors/TAs for the class are: Sophy Figaroa, Steven Kim, Kalyani Nair, Lawrence Stampino-Strain, and Ella Zhu. In general the mentor hours will be on the 1st or 2nd floor of Edmunds at times TBD. Please expect occasional changes and cancellations; these will be posted on Slack.

We'll use Canvas for distributing course materials. We'll use Slack for announcements and informal discussion. And We'll use Gradescope for submitting and returning assignments. Let us know if you run into issues accessing any of these.

The textbook for the class is:

• Automata, Computability, and Complexity by Elaine Rich. The book is out of print, but the pdf is freely available from the author's webpage. There are a few physical copies in Edmunds 227 which you can refer to while you're working in Edmunds 227. There are also often used copies available online.

In addition, since you'll be writing code in Haskell, it's recommended that you have access to something such as the following:

• Learn You a Haskell for Great Good! by Miran Lipovača. You can read the book for free online or buy a copy if you prefer paper. As with the Rich book, there are a few physical copies in Edmunds 227 which you can refer to while you're working in Edmunds 227.

You are encouraged to look for and to use other resources to learn more about the ideas and concepts (you may not, however, look directly for answers to individual questions on the weekly problem sets!). Some others that people have found useful are:

Peter Drake's videos on Haskell (which were designed for use with Lipovača's book)

Harry Porter's videos on the Theory of Computation

Brian O'Sullivan, Don Stewart, and John Goerzen's book Real World Haskell

Michael Sipser's book "Introduction to the Theory of Computation"

If you find anything particularly helpful you are encouraged to share it with the class on Slack!

If you need accommodations please contact the Disability Coordinator on your home campus. The process for Pomona students is available here.

More generally, life happens to all of us and we know there may be times when staying on top of the workload in this class is going to feel like too much on top of everything else that you're managing. If that happens, please come talk to a professor so that we're aware and can work with you to try to figure out a plan. Please keep in touch! (Note: we encourage you to come talk to us even if there isn't anything in particular that you feel you need to discuss!)

Logistics

The basic flow each week will be as follows:

• Monday 1:15-2:30pm (or 2:45-4pm): lecture
• Wednesday 1:15-2:30pm (or 2:45-4pm): lecture
• Thursday-Friday: small group meeting
• Friday 10pm: group assignment due
• Sunday 10pm: weekly problem set due

The lectures will be in Edmunds 101.

You will be assigned to a small group of approximately 5 students the first week of class. Your group will work together for the entire semester; your first task will be to find an hour when all of you can meet either Thursday or Friday. The plan is for each group to have an assigned TA who will attend the meetings to answer questions, talk through concepts, etc. Each week there will be a low-stakes assignment to work on during your group meeting; this should be turned in by 10pm Friday evening on Gradescope. There may occasionally be anonymous surveys for you to give feedback on how your group is doing, but please feel free to bring up concerns with either of the professors at any time.

In addition, there will be a weekly problem set. The assignments will mostly be done and submitted in pairs and will also be submitted on Gradescope. The pairs will be by assignment for the first few weeks and then at your discretion after that. Problems on the assignment will ask you to apply concepts in new ways. You may discuss the problems with anyone else currently taking cs101 (or with the TAs or myself), but each pair must write up their own solution without referring to any written/typed/etc materials that may have been generated during such discussion. In addition, you must acknowledge who you worked with and what their contribution was. Submitting an answer found on the internet or generated by an AI-powered system such as ChatGPT is not allowed. Unless stated otherwise, problem sets are due by 10pm on the due date.

Finally there will be a written, in-class checkpoint approximately every 5 weeks.

The breakdown of grades will be as follows:

• 35% problem sets
• 60%/65% checkpoints (20% each / 25% for 3rd checkpoint)
• 5%/0% group work

Schedule

This is a high-level outline of the planned schedule. Note that the calendar is subject to change. For the readings "ACC" refers to the book "Automata, Computability, and Complexity" by Elaine Rich.

Unless stated otherwise, all deadlines are at 10pm on the given date.