2024 April 26,

CS 254: Computability and Complexity

Carleton College, Spring 2024, Dr. 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 a data structures course (CS 200 or 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 5A (MonWed 1:50-3:00, Fri 2:20-3:20). You are expected to attend every class meeting, take notes on paper or a tablet, 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.

Laptops, phones, photos, and recordings are prohibited (except by special arrangement). Why? This course's material can't be typed easily on a keyboard. Using a laptop or phone measurably distracts the students around you. Photographing a chalkboard is not as educational as taking notes. I want our class to be a safe space, where students do not feel that they're on stage.

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 just as good? Sorry, 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 about one third of the way through the course. Exam B is a take-home exam given about two thirds of the way through the course. It is cumulative but focused on recent material. Exam C is scheduled for the official final exam period: Saturday June 1, 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. They exceed expectations.
• 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 edition, 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.

Here are the exams from this term, with quartiles (75th, 50th, and 25th percentiles) listed.

• Exam A, Solutions (47/48, 38/48, 30/48)

Here are the exams from when I taught the course in fall 2022, with quartiles (75th, 50th, and 25th percentiles) listed. Our exams might cover slightly different material, but these old exams are still good sources of practice problems.

• 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. There are four of them, because that's how I did things that term. Every term is a bit different.

• 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)

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, Lily (e-mail haasl), also holds prefecting sessions. Again, just drop in or e-mail for a special appointment.

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. :)

Schedule

To help you decode the schedule, here is an example. Wednesday March 27 is Day 02 of the course. On that day, we discuss deterministic finite automata. You have homework called "Day 02". Attempt it immediately, but hand it in at the start of class on Day 04. Read Section 1.1 to get another treatment of the material.