Syllabus

Course Information

Course: CS 139: Theory of Computation
Term: Spring 2020
Room: 101 Science Connector Building
Time: TR 11:00am–12:15pm

Overview

Welcome to the Spring 2020 semester of CS 139. This course is an introduction to three important branches of computer science, namely,

1. complexity theory,
2. computability theory, and
3. automata theory.

Complexity theory is the branch of computer science that studies the difficulty of computational problems. Some problems can be solved efficiently by a clever algorithm, while others have no efficient solution. Identifying the complexity of a problem before attempting to design an efficient algorithm can save countless hours of work.

Computability theory is the study of the nature of computation and its limitations. In particular, it aims to determine which problems are computable and which cannot be solved by any algorithm. What do we mean by “algorithm” and “computable”? We will formally define these in this course, and explore the interesting class of uncomputable problems.

Automata theory includes weaker notions of computation such as finite state machines and context-free grammars. These are used in string parsing algorithms, compilers, and artificial intelligence.

After taking this course, students will be able to

• understand the properties of computational problems and the nature of their difficulty,
• distinguish between the hardness of computational problems,
• reason abstractly about algorithms and mathematical objects and treat them interchangeably, and
• carefully examine solutions to problems and present arguments logically and rigorously.

Textbook

The required textbook we are using is

• Introduction to the Theory of Computation
  Michael Sipser

We will be referencing this book regularly, so it is important that every student has access to a copy.

Edition: Both the 2nd and 3rd editions are acceptable. The new chapters included in the 3rd edition will only be mentioned in passing, and you will not be tested over it. Some errors were corrected in the 3rd edition, but a list of errata is maintained by Sipser.

Reserve Copy: A physical copy of the 3rd edition has been put on reserve and is accessible from the Cowles Library.

Course Activities

Attendance

Please come to class and engage with the material! Some concepts are unintuitive at first, and class activities might be more helpful than the textbook readings alone. If you have a question, others are likely to be wondering the same thing. Please speak up and ask questions anytime.

Readings

Readings from the textbook and other sources can be found on the Schedule. You must complete the readings before coming to the corresponding class as well as write a reading journal. Many students find reviewing the readings after class to also be useful.

Assignments

Assignments will be assigned (approximately) weekly and must be turned in electronically using Gradescope. Problems are due before class on the corresponding due date and will usually have Tuesday deadlines. Some problems will be relatively straight-forward and others will challenge you. You can find the due dates on the Assignments page and the Schedule page.

Problems will be graded on a four-point scale:
(4) quality deserving of being a solution set;
(3) correct with minor errors or flaws of presentation;
(2) essentially correct idea but with significant technical or presentation errors;
(1) some good ideas but fundamentally flawed solution;
(0) no genuine attempt.

NOTE: You should receive an invitation to set up your Gradescope account on the first day of class. If you did not receive this email, contact the instructor to help you set up your account.

NOTE: Your homework submissions may be handwritten or typed; however, you must submit your solutions electronically. Therefore, if you choose to handwrite your solutions, you must scan your solutions into a PDF format before submitting.

Exams

There will be two midterm exams and one final exam. All of the exams are in-class, individual, closed-note, closed-textbook, etc. The midterm exams are listed on the Schedule, and the final exam will be during our normal final examination slot.

Reading Journals

Most class days have an associated reading from the textbook on the Schedule. Students are required to submit a summary of the reading to the instructor by 8:00 AM the morning of the corresponding class day.

These journals are to be emailed to the instructor with the subject [CS 139] Reading Journal: READING. For example, the first journal for the course is due Thursday, January 30th at 8:00 AM and should have subject:

[CS 139] Reading Journal: Sipser 0.1-0.2

The writeups must include a 1-2 paragraph summary of the reading. You are also encouraged to include one or two questions or comments that you have about the reading. Your questions and comments will be taken into account in the corresponding class activities.

The reading journals will be graded on a binary scale: 1 point for a well-written summary of the reading or thoughtful questions; 0 points for a missing, late, or poorly written summary.

Extra Credit: There are 20+ readings this semester, but the reading journals are graded out of 15 points. All additional points are extra credit for this part of your grade. For example, if you complete 18 readings, you will get the full 5% plus 1% extra credit to your final grade.

Grading

Your grade is calculated using the following weights:

Assignments	30%
Midterm Exams	20% (each)
Final Exam	25%
Reading Journals	5%

No standard percentage will be associated with a particular letter grade in this course. Instead, I will decide final letter grades by comparing a student’s overall score to that I would expect from a student who had an understanding of the material at an A level, B level, etc. This means that I explicitly take into account factors such as the difficulty of an exam or the homework when assigning final grades. If you want to know how you are doing at any given point in the class, please reach out to me. That being said, I do expect a percentage above 93 will always receive an A, a percentage above 90 will receive at least an A-, etc., but I reserve the right to modify this scale in your favor.

Course Policies

Deadlines

Deadlines in this course are firm. Please plan your week accordingly and start your assignments early!

NOTE: I do recognize that there are exceptional circumstances due to family emergencies, etc. I am certainly willing to work with you through these situations, so do not hesitate to reach out.

Accommodations for Students with Disabilities

Drake University is committed to providing equitable access to learning opportunities for all students. The Disability Services office (107 Old Main) collaborates with students who have disabilities to provide and/or arrange reasonable accommodations. If you have, or think you may have, a disability (e.g., mental health, attentional, learning, autism spectrum disorders, chronic health, traumatic brain injury and concussions, vision, hearing, mobility, or speech impairments), please contact

• Michelle Laughlin
  Student Disability Services Coordinator (x1835)
  michelle.laughlin@drake.edu

to arrange a confidential discussion regarding equitable access and reasonable accommodations.

Academic Integrity

Drake University has high standards for academic integrity, and you are expected to read the Academic Dishonesty Policy from the College of Liberal Arts and Sciences.

Below is a particularly relevant excerpt from the statement:

Academic dishonesty is an all encompassing term involving any activity that seeks to gain credit for work one has not done or to deliberately damage or destroy the work of others. Academic dishonesty includes, but is not limited to, plagiarism, cheating, fabrication, and knowingly helping another to commit an act of academic dishonesty.

Nevertheless, you are also encouraged to collaborate with one another in this course given that you adhere to the following policy.

Collaboration Policy

You may collaborate on the homework assignments to the extent of formulating ideas as a group, but you may not collaborate in the actual writing of solutions. In particular, you may not work from notes taken during collaborative sessions. You must cite all sources, including websites and classmates from whom you obtained ideas. You may not consult any materials from any previous offerings of this course or from any other similar course offered elsewhere.

You are required to completely understand any solution that you submit, and, in case of any doubt, you must be prepared to orally explain your solution to me. If you have submitted a solution that you cannot verbally explain to me, then you have violated this policy.

Of course, there is to be no collaboration whatsoever on any exams, unless otherwise specified. Policies for what constitutes acceptable reference material, if any, will be specified in detail when the exam is distributed.