ECS 220: Theory of Computation, Winter 2019

Course staff

Instructor	Dave Doty	doty@ucdavis.edu
TA	Mahsa Eftekhari	mhseftekhari@ucdavis.edu
TA	David Haley	drhaley@ucdavis.edu

Websites

We will use different websites for different purposes. Students are responsible for checking Piazza and Canvas regularly for announcements and homework postings.

site	purpose	link
Piazza	course announcements, questions/discussion	piazza.com/ucdavis/winter2019/ecs220
Canvas	homework, storing grades, general course information	https://canvas.ucdavis.edu/courses/299448
Gradescope	auto-graded homework	https://www.gradescope.com/courses/35169 entry code: MYD6XX

Piazza and Gradescope are external to UC-Davis, so you will have to set up accounts if you don't already have them.

In Gradescope, once you have an account, log in, click on "Enroll in course" on the bottom-right, and use the entry code above. Note that Gradescope does not have separate first and last names. Be sure to enter your Full Name, both first and last, in that order. Please also enter your UC-Davis student ID number when you register for Gradescope (even though it says "optional" in Gradescope).

Constructive feedback about any aspect of the course is always welcome. Please write me an email at doty@ucdavis.edu, or if you prefer to remain anonymous, you can use https://sayat.me/DavidDoty

For more general help regarding UC-Davis (not necessarily related to this course), please see UC Davis Student Resources.

Course objective

To study the fundamental abilities and limits of computation, in a mathematically rigorous way.

A major objective is also philosophical: to treat computer science not merely as a tool for automating computation to aid in other endeavors, but as a fundamental natural science itself. P=NP, or it doesn't. Matrix multiplication can be computed in O(n²) time, or it can't. These are questions about our universe whose answers we don't currently know. The answers, whatever they are, promise to be every bit as profound as Maxwell's equations or the principle of relativity.

Prerequisites

ECS 120 and ECS 122a, or equivalent.

Textbook

The Nature of Computation
Cristopher Moore and Stephan Mertens
Publish date: 2011
Textbook Homepage

Chapters 1-3 are essentially a brief review of algorithms at about the level of ECS 122a. We will go through that fairly quickly and then get to the meat of the course, computational complexity theory, starting in chapter 4.

We will cover chapters 1-7.

If we had a second term, I would love to get into space-bounded complexity in chapter 8, randomized computation in chapter 10, and the connections between complexity/computability and physics in chapters 12-15, but 10 weeks will not be enough time for this. So the rough syllabus is:

week	chapter	topics
1	1-3	algorithms, introductory computational complexity theory, the class P
2	4	the class NP, problems in NP, reductions between problems in NP
3	4/5	formal definition of NP, NP-completeness, how to design reductions
4	5/6	circuits and formulas, Cook-Levin theorem: SAT is NP-complete, completeness as a surprise, consequences of P=NP, the polynomial hierarchy
5	6	diagonalization, time hierarchy theorem, relativizing proofs, Ladner's theorem: existence of NP-intermediate problems
6	7	computability theory, history of computability
7	7	history of logic, alternative universal models of computation
8	7/8	alternative universal models of computation, space-bounded computation
9	8	space-bounded computation
10		???

Slides/lecture notes

I will use mostly overhead slides, improvising on the blackboard as necessary. I will attempt to post these slides online before lecture, to encourage students to use their class time to listen, think, and speak up, which I believe is more beneficial than the orthopedic workout of transcribing every word that materializes on the front wall. Just to make sure I'm being clear: I advise you not to try writing down everything on the slides.

The slides should be thought of more as a visual aid to our discussion than an official record of what we have learned. We will follow the textbook closely, and I guarantee that the textbook's exposition of concepts is far more complete, understandable, and self-contained what I write on the board or project on the wall.

Moreover, the slides will usually leave out details of a proof that we verbally discuss. So the slides should not be used as an example of what a good proof looks like. Use the textbook as an example of what constitutes a complete proof (though the textbook often relegates details of proofs to exercises).

I use a lot of color in my slides. If you are colorblind and have difficulty seeing the difference between two different colors, please let me know so I can choose better colors.

Lecture

MWF 2:10pm-3:00pm, Olson 205

Discussion

W 3:00pm-4:00pm, Olson 205

The discussion is supposed to be interactive; go with questions.

General contact

You may post questions to the Piazza discussion board, where it will be seen by the instructor, the TA, and the entire class. This is a good forum for asking for homework clarification or LaTeX help, for instance. If I spot that a student has already given what I think is a good answer to the question, I may mark it as a good answer instead of answering it myself, so look at both the "student answer" and "instructor answer" (and the followup discussions are often useful as well).

Please write an email to the instructor or TAs or attend office hours if the subject is of a personal nature, for instance, a question about how your homework was graded. Note: If you ask a non-personal question about homework or course policies over email, the instructor/TA may post it (after removing your contact information) to Piazza along with an answer for everyone's benefit.

Canvas has some sort of email/messaging feature, but we don't check it, so please use Piazza/email to contact the course staff instead.

Office hours

Homework assignments

Homework must be submitted as a PDF file to Canvas.

Collaboration: You are allowed to work in groups of size 1, 2, or 3 on the homework, and to submit a single homework submission from the whole group. You can change the groups for different homeworks if you like. If you discuss the problem with anyone else, including students from other groups, students not enrolled in the course, or anyone else besides the course staff, then you must indicate this in the homework submission. Please see the academic dishonesty policy below for more details.

Furthermore, do not put your name(s) in the PDF. We will do anonymous peer review, which requires that the PDF not identify who you are.

[sigh... and this already-huge syllabus grows ever larger. In response to a student's defense that they are not responsible for submitting a plagiarized solution because they didn't even attempt to do that problem, having instead allowed one of their fellow group members to commit plagiarism on their behalf, the paragraph below has been revised after Winter 2019 to make it clear, as though it weren't already clear, that all group members are responsible for all submitted solutions.]

Although I have no way of enforcing this, my strong recommendation is It is required that all members of the group work on all problems. Do not simply split them up among the group members. The point of collaboration to help everyone understand the problems through discussion. Splitting it up guarantees that you won't understand a problem if you didn't work on it. If you haven't contributed to solving all the problems, then things are going to go poorly if a subsequent homework relies on understanding a previous problem (this happens), or if one group member stops pulling their weight and you need to do all the problems yourself (this also happens). If any of the solutions violate the UC-Davis Code of Academic Conduct (for instance if a solution is plagiarized), then all group members will be held responsible.

LaTeX

You are required to use LaTeX to produce the PDF files for homework submissions. It is the most widespread program for producing mathematical text. For several decades it was the only serious way to do so, although now there are alternatives, such as Patoline, and some "hybrids" like certain Markdown engines that allow embedded LaTeX math, e.g., https://hackmd.io/, https://www.madoko.net/, https://upmath.me/. Nevertheless, LaTeX is an important skill for computer scientists to develop. In particular, it is useful to be fluent in LaTeX's mathematical shorthand (e.g., n^2 for n² or \infty for ∞), since this is a de facto standard for communicating mathematics through text.

If you haven't used LaTeX before, see the ECS 120 page on LaTeX for some guidance on how to get started.

Grading

Grading is based on class participation, homeworks, and peer review. There will about about 25 total problems assigned (other than HW0, which is more a prerequisite test). Your lowest 4 problem scores (outside of HW0) will be dropped. The number of points on an assignment is not an indication of how much the assignment is worth; the percentages will simply be averaged together for the problems, with problems except HW0 weighted equally.

Final scores will not be rounded. The grading scale will be

A+	97 ≤ score
A	93 ≤ score < 97
A-	90 ≤ score < 93
B+	87 ≤ score < 90
B	83 ≤ score < 87
B-	80 ≤ score < 83
C+	77 ≤ score < 80
C	73 ≤ score < 77
C-	70 ≤ score < 73
D+	67 ≤ score < 70
D	63 ≤ score < 67
D-	60 ≤ score < 63
F	score < 60

Peer review

Students will review homework submissions of other students (anonymously). A small portion of your homework grade will be based on the quality of these reviews. The reviews don't have to be perfect, but if a submission has an obvious huge gaping flaw, and your review says "looks good A+++", then you may not get full credit for the review.

Also important: be respectful in your reviews. It can be frustrating to read something that you think is poorly written. However, part of what we are practicing is restraint, because it can be easy for the anonymity of reviews to bring out the worst in us. For each review you write, think about how you would feel if you read the same thing about your work. If it would offend you, phrase it differently. You can point out errors, omissions, and even poor writing without insulting the writer.

Reviews are due one week after the homework deadline.

My reasoning for both the group homework and peer review is discussed here.

Here are some brief guidelines for writing a good review. For each problem, address the following:

Late homework

Briefly, the policy is that homework will be accepted up to two days after the deadline, but a late penalty will be applied, which grows larger as the day goes on.

There is a function p(h), where h represents the number of hours that the homework is late (the submission time is recorded to the nearest microsecond, so p(h) is defined on fractional hours as well), and p(h) represents the percentage of the original score remaining after the late penalty is applied. So, if the original, un-penalized score on the homework is s, then the penalized score is s·(p(h)/100). At first, p(h) decreases rather slowly with h, but it decreases more rapidly as time passes until 48 hours after the deadline, when homework is no longer accepted since the score would be 0 no matter what.

Formally, p(h) = 100 · (1 - (h/48)⁴), capped above and below at 100 and 0, respectively:

For example, suppose that a student/group received 100 points on a homework. Then here are the penalized scores for various submission times:

• on time: 100
• 1 hour late: 99.99998
• 12 hours late: 99.6
• 24 hours late: 93.8
• 36 hours late: 68.4
• 47 hours late 8.1
• 48 hours late: 0

This policy has several purposes:

1. The homework needs to be turned in on time if peer review is to be possible. To see why the late penalty takes the form it does...
2. Some students have every intention of getting homework done on time, but maybe something gets in the way the day it's due, or it just takes longer than anticipated. Hopefully the ticking clock starting at the deadline is an incentive to start the homework early enough to finish it on time. But if you make a mistake with time management and don't quite get it done, it won't cost your grade that much to get it in a few hours late.
3. It is a drain of mental energy and time (hurting every other aspect of the course) to deal with requests to give a full grade to a late homework because it was "only a little late". Under this late penalty policy, if it is only a little late, there is only a little penalty, so there is little incentive to make such requests.

Disabilities

If you have a documented disability and anticipate needing accommodations in this course, please meet with your instructor as soon as possible. Request that the Student Disability Center staff send the proper form (https://sdc.ucdavis.edu/forms.html) verifying your disability and specifying the accommodations that you require.

Code of Academic Conduct

The UC-Davis Code of Academic Conduct outlines what is considered academic misconduct. Note in particular some recent changes here: https://academicsenate.ucdavis.edu/bylaws-regulations/revisions

Anyone violating the policies in the Code will be reported to Student Judicial Affairs, and anyone found guilty of academic misconduct will receive an automatic F in the course.

Academic misconduct: Pressuring course staff

There is one reason and one reason only to contact the instructor or TAs about grades: the grader stated something specific about your submitted solution that is untrue. In this case, you may point out the specific error.

The Code of Academic Conduct specifically forbids "Pressuring an instructor or teaching assistant to regrade work, change a final grade, or obtain an exception such as changing the date of an exam, extending a deadline, or granting an incomplete grade." An explicit request to change the final grade is one way to violate this policy. However, there are many other ways to pressure course staff about grades, all of which are forbidden. Pressure also includes (but is not limited to)

• Stating that you "need an A- in the course" for some reason (such as being a Ph.D. student), or stating that you "need" or want any particular grade. I interpret a statement like this, even without referencing your current grade directly, as an attempt at emotional manipulation.
• For a graded exercise on a homework, quiz, or exam, prior to the submission, trying to get course staff to tell you a solution or to confirm that your solution is correct. If you don't understand a solution well enough to tell for yourself whether it is correct, then it doesn't make sense for you to get credit for it. There can be a fine line between asking for confirmation of solution correctness (which is forbidden) and just trying to understand how to solve a problem or understand what format of answer is expected (which are allowed). However, if course staff senses that you are no longer asking questions for the sake of understanding, but instead want us to make a commitment that you will receive full credit if you hand in a particular solution, or appear to be trying to get us to tell you what you should write to get full credit, this is against policy.
• Requesting more points for any other reason than a specific erroneous statement made by the grader. In fact, requesting more points is inappropriate, whatever the reason. If the grader made a mistake, point out the mistake, and we'll figure out whether that means you should get more points. Examples of common invalid reasons for a regrade request are
  • "I need an A- in this course since I'm a Ph.D. student."
  • "I think this is too many points to deduct and I should get more partial credit."
  • "I discussed it with the instructor/TA and they said it was fine." This is not only against policy, but it indicates that you already violated the policy by asking course staff to confirm a solution is correct before submission, and it confirms that the discussion was not intended to aid your understanding, but instead was a set-up to pressure the course staff after the work is graded.
• Asking what your course grade will be. If coursework is not all graded, then we don't know any more than you do what your numerical score will be. If coursework is all graded, you can see your numerical score, and the syllabus states how to convert numerical scores to letter grades. Canvas also does this conversion and shows a letter grade. If you ask me what your grade will be, then because you already know the answer as well as I do, I will interpret that "question" instead as a statement, "I want my grade to be higher, and I'm warning you that I'll be upset if it isn't."
• Asking whether the grading scale for the course will be adjusted or if a curve will be applied. The default answer is no. If I decide to adjust the grading scale that maps numerical scores to letter grades, I will do it alone and with time to think carefully about what is fair. I interpret questions or statements about that grading scale to be an attempt to pressure me to change it.
• Telling me that your score is close to a letter grade cutoff (e.g., an A- is 90% or above, and you have an 89.9%). I know what everyone's scores are, and what cutoffs are set for letter grades, so there's no reason to tell me other than to imply that you want me to bump up your grade to the next letter.

Academic misconduct: Homework

Each assignment is to be the product of your own intellectual effort. We will check for cheating in this course.

Since group submissions are permitted on most homeworks, each group member may of course discuss their solution with the other members of the same group to whatever extent they wish. The rules below apply to collaboration/discussion between different groups.

Each assignment is to be the product of your own intellectual effort. Students are allowed to work in groups for homeworks, but each group should produce an assignment submission independently of the other groups.

Here are just a few disallowed examples of excessive collaboration between groups, and excessive copying of other sources:

• Allow another group to plagiarize your work.
• Type in one homework together and turn in two copies.
• Write one homework together on paper and turn in two copies after you each type it in.
• Each write part of a proof (for example, 2 lemmas each), combine them, and turn in two copies.
• Look up answers from a previous term of the course that used the same question.
• Look up an answer on the Internet and hand it in.
• Look up an answer on the Internet, modify it, and then hand it in.
• Give (paper, email, shared network folder, posting on a public machine, letting someone else look at your screen, reading homework out loud while someone types it in, dead drop, etc.) another group a copy of your solution, or of any part of your solution, even if the other group does not copy from your solution. (See below for examples of situations in which it is okay to let another student/group look at your solution.)
• Receive another group's solution, or part of it, as described in the previous example.

This is a non-exhaustive list that does not enumerate all possible situations that constitute cheating. The general principle to follow is that whatever sort of help you receive to figure out how to do the homework, after receiving this help, you should be able to reproduce the homework on your own, without requiring anyone else's help. That is, help from a website/tutor/classmate is allowed as long as it is help in learning how to do the homework, but that help should not be required to actually do the homework once you have learned how. If you are unable to reproduce a homework that you submit without the person/group who helped you, then it is not a product of your own intellect, and it means you are misrepresenting someone else's work as your own.

Similarly, if you are helping someone else, be wary of letting them simply write down what you say as their answer. If you have truly helped them, then they should be able to do it on their own once you leave the room. If you show your homework to a friend to "help" them, eventually your friend, or a friend of your friend, will turn in part of your homework, and you will be held responsible for their cheating. This is known as tendering of information, and it is just as serious of an offense as copying someone else's work.

Things you may do when working with another student/group:

• Talk about and write down ideas about how to solve the problem, at a high level. Note, however, that sharing ideas specific enough for each student's solution to be identical (except for minor cosmetic changes in variable names, etc.) in terms of having the same statements in the same order, is too much. No two computer scientists will produce the exact same proof of a theorem, so if you are sharing enough "help" with another student for them to be able to re-produce your proof, or almost exactly your proof, you are sharing too much.
• Share content that was done as a formal exercise, or that was presented in class or the textbook.
• Share your homework solutions after the last day to turn in an assignment.

In general, it is acceptable to discuss how to do the homework with other students/groups, but when it is time to sit down and write your homework, you must be able to produce the entire homework without help from anyone else. And if you do consult outside sources (meaning besides the course staff or the textbook) to learn how to do the assignment, you must cite these sources. For example, if you look at a proof on a website and to get ideas for how to do the homework, and you indicate precisely which website it was, you will not be accused of academic dishonesty. (Although if you merely copy its text you may receive no credit.) However, if you get help from anywhere besides the textbook, instructors, and TAs, you must cite it. Anything else is misrepresenting someone else's work as your own. It would be a good idea to cite help from instructors and TAs anyway, in order to train yourself always (including outside of this class and this university) to think about who helped you with some work, so that they may be acknowledged. Similarly, if you discuss homework with another student/group, state this explicitly in your homework submission.

Academic (and legal) misconduct: Course materials

Finally, the slides, lecture notes, homeworks, and other documents I share are not to be redistributed without my permission. This means in particular that you should not post them to sites such as CourseHero. These are copyrighted, either by me or by the textbook authors, and you could actually get in legal trouble by sharing course materials improperly.