2020 March 25,

CS 254: Computability and Complexity

Carleton College, Winter 2020, Joshua R. Davis, , CMC 324, x4095

Introduction

This course considers the 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 to the theory of 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.

The official prerequisites for this course are Introduction to Computer Science (CS 111) 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.

Logistics

Our class meets in CMC 301 during period 5A (MonWed 1:50-3:00, Fri 2:20-3:20). Some course materials are:

• Introduction to the Theory of Computation, 3rd Ed, by Michael Sipser. This text has been used in other recent sections of CS 254.
• Mounting Network Drives helps you hand in the electronic parts of your assignments on the COURSES file server. (This system might not be accessible from off campus.)
• Transition to Python is Jeff Ondich's tutorials for people who know other programming languages.
• Getting Started with Python is my Python tutorial for CS 111 students.
• Here are our exams, with quartiles (75th, 50th, and 25th percentiles) listed.
  • 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.
  • 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)
• Here are the exams from spring 2014.
  • Exam A, Solutions (41/48, 37/48, 32/48)
  • Exam B, Solutions (30/36, 25/36, 21/36)
  • Exam C, Solutions (85/108, 73/108, 60/108)
• My Schedule includes office hours. No appointment is needed during office hours; just drop in. If you can't make office hours, then consult my schedule and e-mail me a couple of possible meeting times.

The following elements contribute to your course grade.

• Work in the classroom (5%): See below for more detail. You can make up for a deficiency in class participation by attending office hours. In a sense, office hours are extra class time. Office hours are optional, except that you are required to visit me in my office at least once during the first two weeks.
• Work outside the classroom (10%): See below for more detail. 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.
• Exam A (20%): The first exam is given in class around Day 8 (Week 3).
• Exam B (20%): The second exam is taken outside class around Day 14 (Week 5). It is cumulative but focused on recent material.
• Exam C (20%): The third exam is given in class around Day 22 (Week 8). It is cumulative but focused on recent material.
• Exam D (25%): The fourth exam is scheduled for the official final exam period: Saturday 2020 March 14, 3:30-6:00. It is cumulative but focused on recent material. Self-scheduled exams are not allowed.

Course grades are assigned according to an approximate curving process. There are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades (A, B, C, etc.). Rather, I assign grades by comparing the students to each other, to earlier students, and most importantly to the course goals. An advantage of this system is that student grades don't suffer when I write a difficult exam, for example. The disadvantage is that you cannot compute your own grade. Visit me in my office, if you want me to estimate your current grade for you.

If some medical condition affects your performance in this course, then let me know in the first week of class (or as soon as it arises). You may need to make official arrangements with the Disability Services.

Work in the Classroom

You are expected to arrive to class slightly early, so that you are ready to participate as soon as class begins. Do not sit alone. You are often expected to work out problems with your neighbor. My ideal class meeting is more of a discussion than a lecture. Discussions are not just for English and history classes. Communication skills are essential to every academic discipline, and they are highly prized by employers.

You are expected to take notes, even if your learning style is primarily aural. Because the material involves many diagrams, you should take notes on paper or on an electronic device that supports rapid drawing. Typing on a laptop is not adequate.

Photographs and recordings are not permitted without my prior approval. Phones are not permitted, except for the purpose of approved photographs and recordings.

Work Outside the Classroom

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.

Although homework is assigned every day, it is collected only once a week. When handing in a week's homework, staple your pages into a single packet, in the correct order. Multi-sheet packets that are not stapled are unacceptable. I will not accept packets that are not stapled. Is there a stapler in the classroom? Often not, so staple ahead of time. Is a paper clip okay? No.

During the term, you have one free pass to hand in a week's homework packet late. You do not have to justify your lateness. In fact, this policy exists so that I don't have to agonize over the relative merits of varying excuses. When using your late pass, simply hand in your late packet when the next packet is due, writing "Late Pass Used" prominently at the top of the late packet. Once you have used your late pass, no late assignments are accepted, except in extreme circumstances that typically involve interventions by physicians or deans.

You are expected to spend about 10 hours per week on this course outside class. Some students need to spend more than 10 hours. If you find yourself spending more than 15 hours, then talk to me.

Schedule

To help you decode the schedule, here is an example. On Day 03 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 06.