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 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 (on zoom to start the semester and hopefully eventually also in person; best to email me first to make sure what modes are available!) to talk about the class, about theory more generally, or just about life. My weekly office hours are Tuesdays 1:30-2:30pm and Wednesdays 7-8pm. I'm also happy to meet with you at other times by appointment: 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: Alan Guo, Claire LeBlanc, Guy Thampakkul, and David Yang.

We'll be using piazza for distributing course materials as well as making announcements and answering question. We'll be using gradescope for submitting and returning assignments. Let me know if you have problems accessing either.

The textbooks for the class are:

You are encouraged to look for and to use other resources. Some others 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 Real World Haskell
  • Michael Sipser's "Introduction to the Theory of Computation"
    •  If you find anything particularly helpful you are encouraged to share it with the class on the Piazza forum!

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

    Logistics

    The basic flow each week will be as follows:

    The lectures will be on zoom for the start of the semester (see the class piazza page for the link); once we're allowed to be back in person the lectures will be in Edmunds 101.

    You will be assigned to a small group of approximately 4 students the first week of classes. Your group will work together for the entire semester; your first task will be to find a time when you can all meet for an hour on 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 will be turned in on Friday evening on gradescope.

    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. As with the practice problems 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.

    Finally there will be checkpoints approximately every 5 weeks.

    The breakdown of grades will be as follows:

    Calendar

    This is a high-level outline of the planned syllabus. Note that the calendar is subject to change. For the readings "ACC" refers to the book "Automata, Computability, and Complexity" by Elaine Rich and "LYAH" refers to the book "Learn You a Haskell for Great Good!" by Miran Lipovača.

    Week Day Date Topic Reading Due
    1 W 1/19 introductions: content, class, people, Haskell LYAH: Ch 1-4
    2 M 1/24 (review) sets, logic, functions, relations, proofs ACC: Ap A week01-ps due 8pm 1/23
    W 1/26 basic definitions, languages, FSM, regular languages ACC: Ch 2, 5.1-3
    3 M 1/31 constructing FSM, closure properties of regular languages, NDFSM ACC: Ch 5.4 week02-ps due 8pm 1/30
    W 2/2 equivalence of DFSM, NDFSM ACC: Ch 5.4
    4 M 2/7 FSM: closure, minimization, Myhill-Nerode theorem ACC: Ch 5.7 week03-ps due 8pm 2/6
    W 2/9 regular expressions, grammars, languages ACC: Ch 6, 7
    5 M 2/14 review, modelling DFSM in Haskell LYAH: Ch 5-7 week04-ps due 8pm 2/13
    W 2/16
    checkpoint 1
    6 M 2/21 non-regular languages, pumping lemma ACC: Ch 8 week05-ps due 8pm 2/20
    W 2/23 CFGs ACC: Ch 11.1-8
    7 M 2/28 pushdown automata ACC: Ch 12.1-3 week06-ps due 8pm 2/27
    W 3/2 *** no class ***
    8 M 3/8 pumping lemma for CFLs ACC: Ch 12.3, 13.1-5 week07-ps due 8pm 3/7
    W 3/10 closure, algorithms for CFLs ACC: Ch 14
    M 3/14 *** no class - spring break ***
    W 3/16 *** no class - spring break ***
    9 M 3/21 lexers and parsers ACC: Ch 15.1-2, parsing handout
    W 3/23 parsing continued (arith) parsing handout
    10 M 3/28 review
    W 3/30
    checkpoint 2
    11 M 4/4 Turing machines ACC: Ch 17.1-2 week09-ps due 8pm 4/3
    W 4/6 Turing machines variations ACC: Ch 17.3
    12 M 4/11 universal Turing machines ACC: Ch 17.6-7 week11-ps due 8pm 4/10
    W 4/13 (review) diagonalization ACC: App A.6.8-A.6.9
    13 M 4/18 halting problem ACC: Ch 19 week11-ps due 8pm 4/17
    W 4/20 decidability, semi-decidability, undecidability ACC: Ch 20
    14 M 4/25 more undecidability, Rice's theorem, Church-Turing thesis ACC: Ch 21.4-7, 18 week13-ps due 8pm 4/24
    W 4/27 semantics, PCF interpreter handout
    15 M 5/2 PCF, interpreters interpreter handout week14-ps due 8pm 5/1
    W 5/4 wrap-up
    The take-home final exam will need to be completed no later than Monday, May 9 at noon.