ECS 120: Theory of Computation, Spring 2017

Course staff

Instructor	Dave Doty	doty@ucdavis.edu
TA	Amanda Belleville	acbelleville@ucdavis.edu
TA	Thong Le	thmle@ucdavis.edu
Reader	Shaopeng Zhu	spzhu@ucdavis.edu

Websites

We will use different websites for different purposes:

site	link	purpose
Piazza	https://piazza.com/ucdavis/spring2017/ecs120/home	course announcements, questions/discussion
Gradescope	https://gradescope.com/courses/4794	homework submission, exam feedback
Canvas	https://canvas.ucdavis.edu/courses/113660	storing grades, general course information, posting homeworks, reading quizzes

Piazza and Gradescope are external to UC-Davis, so you will have to set up accounts if you don't already have them. To sign up for the course on Piazza, go to this link. In Gradescope, once you have an account, log in, click on "Enroll in course" on the bottom-right, and use entry code M6E2X9.

Students are responsible for checking Piazza and Canvas regularly for announcements and homework/quiz postings.

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 

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. There's a polynomial-time algorithm to factor integers, or there isn'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 20, with a minimum grade of C-.

Meeting times

Lecture:

Tues/Thurs 5:10pm-6:30pm, Haring 2205

Discussion:

Tues 8:00am-8:50am, Hoagland 168, (run by Thong)

Wed 3:10pm-4:00pm, Art 204, (run by Amanda)

The discussion is supposed to be interactive; ask questions. If you find yourself thinking something like "I wish the TAs would do X in the discussion"... then raise your hand in the discussion and ask them to do X!

Office hours:

Dave: Tues 12-3pm, Kemper 3041

Amanda: Wed/Thurs 1:30-3pm, Kemper 55

Thong: Tues 9-10am, Thurs 8-10am, Kemper 55

Final exam:

Thursday, June 15, 3:30-5:30pm, Haring 2205

Textbook

Introduction to the Theory of Computation
Michael Sipser
ISBN-13: 978-1133187790
ISBN-10: 113318779X
Publish date: June 2012
Textbook homepage

Any edition of the textbook should work. When I reference page numbers or sections, it refers to the 3rd edition.

Asking questions

Please use the Piazza discussion board. Non-personal questions should be posted publicly so that all students can benefit from the answer. If the subject is of a personal nature, for instance, a question about how your homework was graded, then please write an email to the instructor or TAs or ask in person during office hours. 

Logistical questions: To ensure that the lecture stays on schedule, I request that questions about course logistics be asked outside of lecture, such as on Piazza, or in person during office hours or after lecture has concluded. This includes questions about what content and types of questions will be on exams, whether partial credit will be given for various types of answers, scheduling of quizzes, etc. Besides, in the middle of lecture I'm not likely to recall these things accurately. If I wrote them on Canvas or Piazza, then that is a more reliable source than my memory, and if I didn't write them on Canvas or Piazza yet, it probably means I haven't decided yet and don't want to suddenly commit to a decision on the spot.

It may also mean I don't want to answer it, period. Many of the questions about exam format and content are answered in the section entitled "Exam preparation" in this syllabus; or rather, a more detailed answer would give away too much information about the exam. So please don't be offended if I simply refer to that section of the syllabus in response to a question about exam details.

Grading

Reading quizzes: 5%

Midterm exam: 35%

Final exam: 35%

Homeworks/in-lecture quizzes: 25%

Exam grades will be curved, if necessary, and only for your benefit. If the mean is below 80%, I will curve the grades to obtain an almost normal distribution with mean 80%.

Reading quizzes are to be completed online on Canvas, starting the second week of the quarter, one for each lecture. They must be completed by 4pm on the day of lecture. These are to be completed on your own at home, but they are open-book, open-note. The topics will be some combination of what was already covered in lecture, and possibly some questions on new material from the reading assignment in the textbook.

The midterm will cover unit 1 (automata), and the final exam will cover units 2 and 3 (computability and complexity). In other words, the final exam is not comprehensive.

The midterm exam, final exam, and at-home reading quizzes are scored in a standard way, but the homeworks and in-lecture quizzes are a bit nonstandard.

Homework must be submitted electronically on Gradescope. There are two types of homework problems: auto-graded and written. Auto-graded problems are submitted as text files to Gradescope and scored immediately. Solutions to the written problems must also be submitted (as a PDF file) to Gradescope, but their score will not depend on whether your written solutions are correct. Instead, the score will come from a closed-notes quiz given in lecture after the homework is due. Important: If you have not submitted a homework PDF with solutions to all problems to Gradescope, you will receive a 0 for your quiz score. So think of the written homework as practice for the in-lecture quiz, but it is not optional practice... you must submit it, and it must be a serious attempt at all problems, to receive any credit for the quiz.

This policy sounds strange, but it has a specific goal: to free you from worrying about what sources you may consult, or how much discussion you are allowed to have with other students. You may discuss all written homework with other students, and you may freely consult online sources to learn how to do the homework. It also means that there is no incentive to copy homework from another person or the internet, or to otherwise write something down that you don't understand with the hope of getting points. There's no points to get.

Nonetheless, all homework submissions must be your own work (see Academic Misconduct Policy below), and you should be able to explain why you believe your solution is correct if asked to do so. If it becomes clear that you do not understand your submitted homework, we reserve the right to subtract points from your homework score, regardless of its correctness.

There will about five total homeworks assigned (including HW0, which is more a test of prerequisite knowledge, and is purely auto-graded problems).

Regrade policy

If there is a mistake in grading a problem on an exam, quiz or homework, please use Gradescope's "Request regrade" button on the problem where the mistake was made. Regrade requests must be made within one week after the grades are published, and they must be made through Gradescope.

This is to be used in case the grader made a mistake in grading a specific problem. In other words, the grader pointed out a flaw in your solution to a problem, but the grader was mistaken because your solution does not actually have that flaw.

Gradescope regrade requests will be ignored if they do not conform to the format described. Examples of this include: requesting a regrade of the entire exam (rather than of a specific problem for a specific reason), or requesting that fewer points be deducted (rather than discussing the reason for the deduction).

If you would like to give constructive feedback about the grading policy/number of points deducted/etc., please use one of the means suggested under the section "Websites" above (email or anonymous feedback).

Please note that there are no absolutely re-grades for auto-graded problems. Most of the time, you may re-submit these indefinitely before the deadline, so if you don't get full credit on the first submission, it is up to you to figure out why and keep re-submitting until you get full credit. This includes the case where a bug is discovered in the auto-grader but fixed before the day of the deadline; in these cases it is your responsibility to re-submit after the bug is corrected, before the deadline.

Exam preparation

Exams are closed book and closed notes, with the exception of one 3x5 inch note-card, front and back, for each exam. Quizzes are completely closed book and closed notes (no notecard).

I will often post exams from previous terms to give a sense of their length and difficulty. However, I suggest that you first study the homework and quizzes done in the current quarter before studying previous exams. The answer to nearly every question of the form "Will we have to do the following type of problem on the exam?" is "potentially yes, provided that we covered it in lecture/homework". (This also holds for quizzes.)

I'm always changing how I teach, trying to learn and improve, and each quarter goes a little differently than the previous, with different topic emphasis and speed. When I am writing an exam, I am trying to make sure that the concepts it covers are the same concepts covered in the homework and quizzes of that quarter. I am not thinking about what questions were used the last time I taught the course. Many will likely be similar, but maybe not all.

Of course, after ensuring that you understand the homework and quiz questions, if you simply want more practice with concepts from the course, any exam from any quarter is good for that. But there's no promise that this quarter's exam will be a mere tweak to one from an earlier quarter. I do promise to set it up so that if you truly understand a concept from the homework and quizzes, then exam questions on that concept should be straightforward. In other words, the format of each exam question will either be identical to the format of a homework/quiz question, or if it is a different format, it is a format that should be easier than a homework question on the same concept, so that it is more feasible to finish in the limited exam time.

Think of the homework as training by running in the mountains, so that running at sea level seems easy by comparison.

LaTeX/submitting written homework

You must submit written homework as a PDF on Gradescope.

The best option is 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.

Alternatively, if you prefer to write out by hand, you can convert it to PDF by using a scanning smartphone app, such as Genius Scan. They do image processing to make the document much easier to read than just taking a picture with the camera app. See the Gradescope guide for students for advice on using these options. (Gradescope recommends Scannable for iPhone, but I think Genius Scan takes much more readable pictures.)

Late homework policy

This late policy applies only to homework submissions. The online reading quizzes have an absolute due time of 4pm the day of lecture. The quiz will be unavailable after that time, with no chance to retake it.

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

On scored homeworks, this penalty applies to the score for the homework, and on unscored homeworks, it applies to the score for the in-lecture quiz.

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 12 hours, p(h) decreases rather slowly with h, and in the next 12 hours it decreases much faster, until 24 hours after the deadline, when homework is no longer accepted on Gradescope.

p(h) is defined as follows:

For example, suppose that a student received a score of 10 points. Then here are the penalized scores for various submission times:

• on time: 10 points (10*100%)
• 5 minutes late: 9.99306 points (10*99.9306%)
• 1 hour late: 9.91667 points (10*99.167%)
• 11 hours late: 9.0833 points (10*90.833%)
• 12 hours late: 9 points (10*90%)
• 13 hours late: 8.25 points (10*82.5%)
• 23 hours late: 0.75 points (10*7.5%)
• 24 hours late: 0 points (10*0%)

This policy has several purposes:

1. Some students care very much about getting homework done on time, but for some reason something else gets in the 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.
2. 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.

Academic misconduct policy

Academic misconduct: Homework

Each assignment is to be the product of your own intellectual effort. 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

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 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.

In general, it is acceptable to discuss how to do the homework with other students, 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. Anything else is misrepresenting someone else's work as your own.

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 referred to SJA. (Although if you merely copy its text you will receive no credit, and it is a dishonest thing to do, regardless of the fact that giving the citation technically stays barely within the bounds of the policy.) 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, 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 may not post them to sites such as CourseHero. These are copyrighted, either by me or by the textbook author, 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.