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.

There are two sections of this class. Section 1 is the one that's scheduled for Tuesdays and Thursday from 11am-12:15pm. Section 2 is the one that's scheduled for Tuesdays and Thursdays from 12:45-2:00pm (Pacific time).

Framework

It's going to be a quirky semester. The most important thing to know is there will be a link for each week on Sakai that contains some subset of: learning goals, videos, readings, practice problems, and an assignment. Then the basic flow each week will be as follows (all times are AOE = "anywhere on Earth").

Before Tuesday's lecture you should watch the videos and do the readings while reflecting on the learning goals and working on the practice problems. While the practice problems are not due until 8pm on Tuesday (you'll submit them by uploading a pdf on gradescope), you are strongly encouraged to try them out and to turn them in before Tuesday's lecture! Note that the practice problems will always ask if you have questions about the material. You are free to discuss practice problems with anyone else in the class, but must write up the solutions yourself. These problems will be graded (only) on effort: did you turn in something before the deadline with something reasonable for every problem? (Note that if you're not sure how to do a particular practice problem, it is entirely reasonable to answer that problem by explaining why you're confused or stuck!)

During Tuesday lecture I will answer questions about the practice problems and about the material (starting with the questions that were turned in). I will record these sessions and make them available afterwards (but can't guarantee that this will happen before the practice problems are due Tuesday night).

On Thursday you will meet with me in a small group (~4 people per group) for approximately half an hour. These will be problem-solving sessions with a combination of discussion (all of us) and presentations (you). You will be graded on both attendance (were you there?) and participation (how well did you demonstrate your understanding of the concepts? did you enhance the group learning environment?).

The assignment for the week will be due at 8pm on Sunday. The assignments will mostly be done in pairs (assigned by me for the first few weeks and then at your discretion for the remainder of the semester) and will also be submitted on gradescope. 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.

Resources

We will be using Sakai, and applications linked from the class Sakai page (e.g. Gradescope, Zoom), for most things. We will use Piazza for Q&A and general announcements; please make sure you're signed up for this class.

People

Please keep in touch! While the exact details are still evolving, there will be a professor and TAs who will hold office/mentor hours, check Piazza, and care about how you're doing in the class. Note that I am expecting everyone's work/life "balance" to be more complex in this online environment (mine certainly will be); please let me know when "life happens" and we will try to figure out a plan that works.

• Prof. Chen
• TAs: Naomi Amuzie, Adam Guo, Janice Lee, Phuong Nguyen

References

The main textbooks for the class are:

• 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 should also be used copies available online.
• Learn You a Haskell for Great Good! by Miran Lipovača.
You can read the book online or buy a copy if you prefer paper.

We will also be referring to Peter Drake's videos on Haskell (which were designed for use with Lipovača's book) and to Harry Porter's videos on the Theory of Computation.

You are encouraged to look for and to use other resources. Some others are: Real World Haskell and 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!

Calendar

This is a very general outline of the topics we will be covering. For more details go to the class Sakai page.

Grading