2022 November 29,

CS 254: Computability and Complexity

Carleton College, Fall 2022, Joshua R. Davis, , CMC 324, x4095

Introduction

This course ponders fundamental questions of computer science: What can computers do, and how much time and space do they require to do it? To address these questions, the course proceeds in three stages:

1. We begin by studying regular languages and context-free languages. We learn about regular expressions, which are a useful programming tool, and parsing, which is important in programming languages. But the real purpose of this first stage is to serve as a warm-up to the second stage.
2. We introduce Turing machines, which are a central concept of theoretical computer science. We study what Turing machines can do and, more suprisingly, what they cannot do.
3. Focusing on problems that are solvable by Turing machines, we analyze the time and space needed to solve them. Compared to CS 252: Algorithms, we operate at a higher level of abstraction. For example, sometimes we analyze an entire class of problems at once.

Along the way, we encounter some fascinating connections to philosophy, mathematics, and linguistics. Your work is a mixture of writing proofs, executing algorithms by hand, and Python programming. For example, you learn how to determine whether a programming problem is solvable by regular expressions, and solve it with them if it is.

The official prerequisites for this course are Data Structures (CS 201) and a proof course (CS 202 or Math 236). If you don't know Python, then study it on your own (using the links below or other tutorials). Talk to me if you are concerned about your background.

Responsibilities

The College's accreditation says that a 6-credit course is 150 hours of work. That's about 15 hours per week or 5 hours per class meeting. Those 5 hours break down into about 1 hour for class itself and 4 hours for homework, reading, studying, etc. If you find yourself spending less time and struggling, then talk to me. If you find yourself spending much more time, then talk to me.

Class Participation

Our class meets in Leighton 305 during period 2A (MonWed 9:50-11:00, Fri 9:40-10:40). You are expected to attend every class meeting, take notes, participate in discussion and group work, and ask and answer questions. You can make up for a deficiency in class participation by talking with me in office hours. Additionally, you are required to visit me in office hours some time during the first two weeks, even if just to say "hi". It helps us break the ice. :)

Photographs and recordings are not permitted without my prior approval, and phones are not permitted, except for the purpose of approved photographs and recordings. There are two main reasons for this policy. First, I want our class to be a safe space, where students do not feel that they're on stage. Second, photographing a chalkboard is not as educational as taking notes.

It is important that our course be welcoming to all students, regardless of their identities, backgrounds, and experiences. We all sometimes say and do things that make life worse for others, and we should all strive not to. Please let me know if the class feels hostile to you, because of something that I or someone else has done.

Homework

Although class meetings may seem like the core of the course, homework assignments are actually where you learn the material. As far as your grade is concerned, homework serves primarily as the first step in studying for exams.

On homework, you are encouraged to figure out the problems with other students. However, you should always write/type your solutions individually, in your own words. You may not copy someone else's work or allow them to copy yours. Presenting someone else's work as your own is a violation of Carleton's Academic Integrity standards.

Writing is not just for English and history majors. Communication skills are essential to every academic discipline, and they are highly prized by employers. In this course, your written work is evaluated both for correctness and for presentation. Compose your solutions as if the intended audience is your fellow students. By doing so, you show enough detail that the reader can ascertain whether you yourself understand the material.

Homework is usually due two class meetings after it was assigned. This schedule tries to keep you on track, so that work doesn't pile up. But we all have bad weeks, where we can't get everything done, right? If you need to submit an assignment late, then write "LATE" at the top of the front page and submit it as soon as you can. If the grader hasn't graded the assignment yet, then they can grade your paper with the others for full credit. If the grader has graded the assignment already, then you might not get credit. There are limitations to how much delay and complication a grader can handle.

When handing in an assignment, please staple your pages into a single packet, in the correct order. Is there a stapler in the classroom? Often not, so staple ahead of time. Is a paper clip okay? Please, no.

Depending on time constraints in any given week, perhaps not all of your homework is graded. In order to ensure full credit, do all of the assigned problems.

Exams

We have three exams. Exam A is given in class around Day 11 (Week 4). Exam B is a take-home exam around Day 20 (Week 7). It is cumulative but focused on recent material. Exam C is scheduled for the official final exam period: Monday November 21, 3:30-6:00. It is cumulative but focused on recent material. Self-scheduling is not permitted for Exam C.

Grading

For better or worse, we are required to measure your learning using grades. Your numerical grade is based on the responsibilities above: participation 5%, homework 15%, Exam A 25%, Exam B 25%, Exam C 30%.

Numerical grades are converted to letter grades only at the end of the term. Grades are not curved, so students are not in competition with each other. Grades are also not based on predetermined percentages (90%, 80%, 70%, etc.) or explicit specifications, because CS 254 problems are difficult to tune so precisely. (I could accidentally write a difficult exam and wreck everyone's percentages.) Rather, I assign grades by comparing the students to the course goals. For example:

• A student, who earns an A, is not perfect, but they can speak fluently about nearly all of the course content.
• A student, who earns a B, learns most of the big concepts pretty well, but they are missing some concepts. They lack the depth of understanding needed to appreciate subtleties in proofs or algorithms.
• A student, who earns a C, gets some of the material but has significant gaps in their understanding of major concepts.

Talk to me, if you are concerned about your grade.

Resources

I want all of my students to work hard and learn a lot. I try to give them all of the resources that they need. For starters, let's list some basic documents:

• Introduction to the Theory of Computation, 3rd Ed, by Michael Sipser is our official textbook. Many, but not all, recent sections of CS 254 have used this text.
• Transition to Python is Jeff Ondich's tutorial for people who know other programming languages.
• Getting Started with Python is my quick tutorial for CS 111 students.
• Mounting Network Drives helps you hand in the electronic parts of your assignments on the COURSES file server.

Here are our exams so far, with quartiles (75th, 50th, and 25th percentiles) listed.

• Exam A, Solutions (40/45, 37/45, 32/45)
• Exam B, Solutions (27/28, 25/28, 23/28)
• Exam C, Solutions (36/42, 32/42, 27/42)

Here the exams from my winter 2020 version of this course. They don't exactly line up with our exams — for example, our Exam A might include material that appeared on the old Exam B — but they might help you study anyway.

• Exam A, Solutions (48/51, 40/51, 36/51)
• Exam B, Solutions (41/48, 33/48, 29/48)
• Exam C, Solutions (35/41, 32/41, 24/41)
• Exam D, Solutions (50/52, 45/52, 40/52)

Here are the exams from fall 2018. Even though there are three exams, they still might not line up exactly with our three exams, just because I'm always tweaking the course.

• Exam A, Solutions (49/63, 47/63, 42/63)
• Exam B, Solutions (42/48, 39/48, 31/48)
• Exam C, Solutions (64/72, 60/72, 55/72)

Those documents are okay, but if you're trying to do college without working with others, then you're doing it wrong. Remember that I encourage you to solve problems with classmates (even if the work that you submit must be your own). Olin 310 is staffed with lab assistants during the afternoons and evenings. They can help with Python and maybe even a little CS 254 if you're lucky. The tutors in the Math Skills Center on the second floor of CMC might also be able to help you with logic or what little math we use.

I hold several office hours per week. See below for the schedule. No appointment is needed; just drop in! If you cannot attend office hours, then consult my weekly schedule and e-mail me, listing several times at which we could meet.

Our course prefect, Thomas (), also holds prefecting sessions. Again, just drop in!

If a health condition or other personal matter affects your participation in class, homework, exams, etc., then please let me know as soon as possible. Depending on the situation, we might want to confer with Accessibility Resources, Assistive Technology, Student Health and Counseling, or Sexual Misconduct Prevention and Response. When you ask me to help, I do my best to help. :)

Tentative Schedule

This schedule is tentative. We fill it in as we go along.

To help you decode the schedule, here is an example. Friday September 16 is Day 03 of the course. On that day, we discuss nondeterministic finite automata. Section 1.2 of our textbook covers that material; read it before or after class, to get another treament. You might also want to read my extra notes called "DFA vs. NFA Details". You have homework called "Day 03", which you hand in on Day 05.