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 including 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. Send me (Prof. Chen) an email if you have questions about these requirements.

Resources

The professor for this class is Professor Chen. Please stop by my office hours (Mon 9-10am, Tues 1:30-3pm, and Thu 9-10am) if you want to talk about the class, about theory more generally, or anything else. I'll also be available for occasional small group lunches/dinners (see sign-up sheet on my office door) if you'd just like to chat sometime. I'm also happy to meet with you at other times by appointment (in person or on zoom): send me an email with some times that are good for you and a sense of what you want to talk about.

The mentors/TAs for the class are: Grace Chang, Cameron Hatler, Cassidy Liu, Justin Long, and Sumi Vora. 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 either Canvas or Slack.

We'll be using Canvas for distributing course materials as well as making announcements. We'll be using Slack for informal discussion. We'll be using Gradescope for submitting and returning assignments. Let me know if you run into issues accessing any of these.

The textbook for the class is:

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

You are encouraged to look for and to use other resources. 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 Slack channel!

    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 I 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 me so that I'm aware and so that we can work together to try to figure out a plan. Please keep in touch!

    Logistics

    The basic flow each week will be as follows:

    The lectures will be in Edmunds 114.

    You will be assigned to a small group of approximately 5-6 students the first week of classes. 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 will occasionally be anonymous surveys for you to give feedback on how your group is working.

    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. 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. There will also be a take-home final exam that will need to be completed no later than noon on Wednesday 5/1 (for graduating seniors) and noon on Wednesday 5/8 (for non-seniors).

    The breakdown of grades will be as follows:

    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.

    Week Day Date Topic Reading Due
    1 W 1/17 (review) sets, logic, function, relations, proofs; groups ACC: Ap A intro survey due 5pm on 1/16
    F 1/21 week01-group
    Su 1/23 week01-ps-coding
    2 M 1/22 basic definitions, languages, FSM, regular languages ACC: 5.1
    W 1/24 constructing FSM, closure properties of regular languages ACC: Ch 5.1-3
    F 1/26 week02-group
    Su 1/28 week02-ps
    3 M 1/29 NDFSM ACC: Ch 5.4
    W 1/31 Myhill-Nerode, minimization ACC: Ch 5.7
    F 2/2 week03-group
    Su 2/4 week03-ps
    4 M 2/5 regular grammars, expressions ACC: Ch 6, 7
    W 2/7 non-regular languages, pumping lemma ACC: Ch 8
    F 2/9 week04-group
    Su 2/11 week04-ps
    5 M 2/12 Haskell data types, modelling DFSM, lexers
    W 2/14 review
    F 2/16 week05-group (optional)
    6 M 2/19 *** checkpoint 1 in class ***
    W 2/21 CFGs ACC: Ch 11.1-8
    F 2/23 week06-group
    Su 2/25 week06-ps, week06-ps-coding
    7 M 2/26 pushdown automata ACC: Ch 12.1-3
    W 2/28 CFGs, CFLs, PDAs; ambiguity and parse trees ACC: Ch 11.6-7, 12.3-6
    F 3/1 week07-group
    Su 3/3 week07-ps
    8 M 3/4 non-CFLs, pumping lemma for CFLs 13.1-4
    W 3/6 closure for CFLs, algorithms for CFLs ACC: Ch 14
    F 3/8 week08-group (optional)
    9 M 3/11 *** no class - Spring break ***
    W 3/13 *** no class - Spring break ***
    10 M 3/18 parsers: big picture, LL(k) grammars, LL(1) grammars parsing handout
    W 3/20 no class (work on week10 assignments!)
    F 3/22 week10-group
    Su 3/24 week10-ps, week10-ps-coding
    11 M 3/25 recognizers vs. parsers, AST parsing handout
    W 3/27 review
    F 3/29 week11-group (optional)
    12 M 4/1 *** checkpoint 2 in class ***
    W 4/3 Turing machines, TM variations ACC: Ch 17.1-3
    F 4/5 week12-group
    Su 4/7 week12-ps, week12-ps-coding
    13 M 4/8 Turing machine variations, universal Turing machines ACC: Ch 17.3, 17.6-7
    W 4/10 UTM, halting problem ACC: 17.6-7, 19
    F 4/12 week13-group
    Su 4/14 week13-ps
    14 M 4/15 halting problem, proving undecidability with reductions (HALT, ACCEPT) ACC: Ch 19, 21
    W 4/17 more reductions ACC: Ch 21
    F 4/19 week14-group
    Su 4/21 week14-ps
    15 M 4/22 more reductions, D vs SD vs not SD, Rice's theorem, Church-Turing ACC: Ch 21.1-7, 18
    W 4/24 semantics, PCF, type-checkers type-checker handout
    F 4/26 week15-groups
    Su 4/28 week15-ps
    16 M 4/29 semantics, PCF, type-checkers, wrap-up type-checker handout
    W 5/1 review final by noon (grad. seniors)
    17 W 5/8 final by noon (rest of class)