ECS 220: Theory of Computation, Winter 2017

Instructor

Dave Doty
doty@ucdavis.edu
office: 3041 Kemper
office hours: T 1:30pm-3pm, R 10am-12pm

Teaching assistant

Amanda Belleville
acbelleville@ucdavis.edu
office: 3106 Kemper
office hours: TW 3:30-5:00pm

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
3	4/5	reductions between problems in NP, formal definition of NP, NP-completeness, how to design reductions
4	5	circuits and formulas, Cook-Levin theorem: SAT is NP-complete
5	5/6	completeness as a surprise, consequences of P=NP, the polynomial hierarchy
6	6	diagonalization, time hierarchy theorem
7	6	relativizing proofs, Ladner's theorem: existence of NP-intermediate problems
8	7	computability theory, history of computability
9	7	history of logic, alternative universal models of computation
10	7	alternative universal models of computation, applications to nanotechnology research

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 5:10pm-6:00pm, Olson 146

Discussion

W 6:00pm-7:00pm, Olson 146

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

Canvas/Piazza/Gradescope

We will be using Piazza for announcements/questions/discussion, Gradescope for HW0, and Canvas for other homeworks and everything else. Please make sure you have access to all of them. You should automatically see this course in Canvas if you are enrolled. Gradescope and Piazza 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 "Add a course", and use entry code M66JDM.

To sign up for the course on Piazza, go to this link.

Students are responsible for checking Piazza and Canvas regularly for announcements and homework information. It is your responsibility to know how to login, submit homework, etc.

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.

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.

Although I have no way of enforcing this, my strong recommendation is 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, not to guarantee that you don't understand a problem because 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).

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 and on homeworks. There will about about 25 total problems assigned (other than HW0, which is more a prerequisite test). Your lowest 5 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.

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.

Late homework

The late penalty works as follows. 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. For the first two days, p(h) decreases rather slowly with h, and in the third day it decreases much faster. p(h) is defined as follows:

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

• on time: 80 points (80*100%)
• 5 minutes late: 79.986111 points (80*99.9826388%)
• 1 hour late: 79.833 points (80*99.79166%)
• 24 hours late: 76 points (80*95%)
• 48 hours late: 72 points (80*90%)
• 60 hours late: 36 points (80*45%)
• 71 hours late: 3 points (80*3.75%)
• 72 hours late: 0 points (80*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 care very much about getting homework done, but simply cannot bring themselves to work on it several days in advance. This is nothing to be ashamed of. (I don't advise procrastination, but neither do I think it impugns a person's character in any way.) I have very successful colleagues who are essentially incapable of preparing slides for a talk until they are sitting on an airplane on the way to the conference. So for students who operate this way, 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, or even a full day late.
3. Finally, I want to put a lot of time and effort into this class to make it as useful as possible for the students. My ability to do this is compromised by devoting time and energy to 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 should be little incentive to make such requests. Also, everyone's lowest homework score will be dropped, so if there is some once-in-a-lifetime event that prevents a student from getting the homework done, then this will be that student's dropped homework, and it won't hurt their grade.

Academic misconduct policy

Academic misconduct: Homework

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. We will check for cheating in this course. Anyone caught cheating will receive an automatic F. Additionally, we will adhere to university policies regarding academic dishonesty, which means that you may receive any of the penalties described in the UC-Davis Code of Academic Conduct: http://sja.ucdavis.edu/cac.html

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 misconduct: Exams

Naturally, cheating on exams will be held to the same standard, and anyone caught cheating (for example, reading the exam before it starts, writing after it ends, looking at notes or a book or a cell phone or any other information source on a closed-note exam, looking at another student's exam, communicating with another student during the exam, etc.) will be dealt with just as with cheating on the homework.

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.

Disabilities

If you have a documented disability and anticipate needing accommodations in this course, please meet with your instructor as soon as possible, and no later than one week prior to an exam. 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.

Some of the course policies may seem excessively legalistic and draconian. To understand why they are the way they are, see here.