2018 November 27,

CS 254: Computability and Complexity

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

Introduction

This course considers two fundamental questions in computer science: First, what can computers do? Second, how much time and space do they require to do it? While addressing these questions we will touch on various fascinating topics in programming languages, information theory, linguistics, philosophy, etc.

Your work will be a mixture of writing proofs, executing algorithms by hand, and writing programs. For example, you will 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 CS 111 (Intro) and either CS 202 (Mathematics of Computer Science) or Math 236. Talk to me if you are concerned about your background.

The 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.
• 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.
• Mounting Network Drives helps you hand in the electronic parts of your assignments on the COURSES file server.
• Here are the exams from this term, with quartiles (75th, 50th, and 25th percentiles) listed.
  • 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)
• To help you study, 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)
• Here are the exams from Fall 2013.
  • Exam A, Solutions (40/48, 34/48, 28/48)
  • Exam B, Solutions (46/52, 40/52, 30/52), Practice
  • Exam C, Solutions (33/36, 28/36, 20/36)
  • Exam D, Solutions (48/64, 41/64, 37/64)

Our class meets in Boliou 104 during period 3A (MonWed 11:10-12:20, Fri 12:00-1:00). My office hours are currently

• Monday 3:10-4:20 (6A),
• Tuesday 10:10-11:00,
• Wednesday 3:10-4:20 (6A),
• Thursday 9:30-10:20, 3:00-3:50.

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.

Responsibilities

Final grades (A, B, etc.) are assigned according to an approximate curving process. By this I mean that there are no predetermined percentages (90%, 80%, etc.) required for specific grades. The advantage of this system is that student grades don't suffer when I write a difficult exam. 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. The following elements contribute to your final grade.

• Participation: You are expected to attend every class meeting promptly, take notes, and participate in discussion and group work. You can make up for a deficiency in class participation by talking with me in office hours or generally demonstrating exceptional effort and interest. Participation is used to make small adjustments to the final course grade. Additionally, a requirement for passing this course is that you visit me in my office at least once during the first two weeks.
• Assignments: Assignments are the core of the course; they are where you learn the material. Altogether they count for 25% of your grade.
• Exam A: The first midterm exam is given in class sometime around the fourth week. It counts for 25% of your course grade.
• Exam B: The second midterm is a take-home exam given sometime around the seventh week. It counts for 25% of your grade.
• Exam C: The final exam is scheduled for Sunday November 18, 3:30PM-6:00PM. It counts for 25% of your course grade. Self-scheduled final exams are not allowed.

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.

Standards for Work

You are encouraged to work with others on all assignments (but not exams). Work together to figure out the problems/programs, but write/type them up separately, 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 an act of Academic Dishonesty. If Carleton College finds you to not to have upheld its Academic Honesty standards in this course, then you will receive an F for this course.

Writing is not just for English and history majors. Written and oral communication skills are essential to every academic discipline, and are highly prized by employers. In this course, your written work is evaluated both for correctness and for presentation. You may find it easier to type your solutions in LaTeX than to edit them by hand.

How much work should you show? Compose your solutions as if the intended audience is your fellow students. By doing so, you show enough detail that your grader can ascertain whether you yourself understand the material. Your solutions should also be self-explanatory. In this course, the required level of rigor in proofs is sometimes unclear. Mimic the book's level of rigor, preferably with explanation and motivation, and with note of any pitfalls in the logic. If a fellow student were to read your solution, she should be convinced that you understand the problem.

Although homework is assigned every day, it is collected only once a week (usually Fridays). When handing in a week's homework, staple your pages into a single packet, in the correct order. 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.

Computer files should be submitted in plain text (.txt), PDF (.pdf), or Python (.py) formats only, unless otherwise specified. In particular, Microsoft Word documents are unacceptable. Fortunately, you can "print" any document to PDF easily.

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

Special Accommodations

During the term, you have one free pass to hand in a week's homework packet late, no questions asked. 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.

If some medical condition affects your participation in class or your taking of exams, let me know in the first week of class. You may need to make official arrangements with the Office of Disability Services.

Advice

Here is some advice from actual students who have taken this course in the past:

• Get started on homework assignments well before they are due.
• Work with others on the assignments.
• Use office hours. The work is hard, but the professor is happy to help.
• Be honest with yourself about whether you truly understand the material. You will be tested.
• Reading the book can actually be helpful.

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 nfaDFA.pdf. You have homework called "Day 03", which you hand in on Day 06.