Course Syllabus

ECS 120: Theory of Computation, Winter 2018

Course staff

Instructor Dave Doty
TA John Chan
TA Mahsa Eftekhari
TA Aakash Prabhu
Kodethon support Michael Yen


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

site purpose link
Piazza course announcements, questions/discussion

Canvas homework, reading quizzes, storing grades, general course information
Gradescope exam feedback

entry code: MKYBWR

Kodethon auto-graded homework

password: ecs120W18

Automata simulators testing automata

Piazza, Gradescope, and Kodethon 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 entry code MKYBWR. 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).

Click here to see instructions for using Kodethon. Once you have an account, search for the course "ECS 120 Winter 2018" and use the password ecs120W18 to enroll.

Constructive feedback about any aspect of the course is always welcome. Please write me an email at, or if you prefer to remain anonymous, you can use

Please direct issues and bugs regarding Kodethon to Piazza, or if it involves private information, directly to Michael Yen (

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.


ECS 20 with a minimum grade of C-. It is also strongly recommended that you have completed ECS 60 with a minimum grade of C-, or an equivalent course (data structures). Click here to see why ECS 60 is recommended.

Meeting times


Tues/Thurs 10:30am-11:50am, Wellman 106


Section A01: Tues 6:10pm-7:00pm, Haring 2016

Section A02: Fri 9:00am-9:50am, Hutchinson 115

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!

Please attend your registered discussion section. Part of the point of discussion is to be smaller than lecture for easier interaction, but this is disrupted if more students go to one section than the other.

Final exam:

Mon, March 19, 8:00am - 10:00am, Wellman 106 Young 198 (note this is different from the lecture room)

Office hours


None. We will use my lecture notes. Reading will be assigned from these notes. They are updated throughout the quarter, so always get the latest version on Canvas.

Optional textbook: Introduction to the Theory of Computation, by Michael Sipser. Some of the text from my lecture notes is a bit sparse compared to a traditional textbook. If you prefer a traditional textbook with more in-depth explanation, we use mostly the same topics and terminology discussed in Sipser's book. It is also a good source of problems for practice. However, that textbook is not required.

Lecture schedule

The lecture schedule contains the reading assignments and can be found here, which also lists dates of in-lecture quizzes and exams. It is your responsibility to check the lecture schedule to know the dates of quizzes and exams, and to plan appropriately in advance (for example, leaving home early in case of bad traffic). Make-up exams will not be given, except in the case of a medical emergency or a planned absence for a legitimate excuse such as a job interview that cannot be rescheduled.

Asking questions online

Please use the Piazza discussion board. If the subject is of a personal nature, then please write an email to the instructor or TAs or ask during office hours, but otherwise please use Piazza instead of email, so that all students can benefit from the discussion. 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.

Guidelines for effective questions: There are more and less effective ways to ask for help. Asking effective questions is a hugely important practical skill to develop. Especially when learning new programming languages, software, or frameworks, often the fastest source of help is an online forum such as StackExchange or reddit, but there is no incentive for anyone to answer other than altruism. You need to make people want to help you by making it easy for them to help. Please read here for guidelines on how to ask questions effectively.

No logistical questions during lecture or exam review sessions: I kindly request that questions about course logistics be asked outside of lecture and exam review sessions, such as on Piazza, in order to ensure that the lecture stays on schedule. 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. 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 the question, period. Many of the questions about exam format and content are answered in the section Exam preparation in this syllabus, and 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.


Reading quizzes: 5%

Midterm exam: 30%

Final exam: 30%

Homeworks/in-lecture quizzes: 35%

(optional extra credit) Piazza participation: 2%

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

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

Reading quizzes

Reading quizzes are to be completed online on Canvas on your own time, one for each lecture, starting before the second lecture. Each lecture is named, for example, lecture 3a is Tuesday of week 3, and 4b is Thursday of week 4; each quiz is named for the lecture that it precedes. The topics will be some combination of what was already covered in previous lecture and new material from the reading assignment for the next lecture.

The reading quizzes are open-book, open-note, with no time limit. The intention is not to test what you already know, but to learn and to stay engaged, by thinking about the course material several times per week.

If you don't know the answer to a question, don't guess! It is called a "reading quiz" because you really are intended to simply look up the answers in the lecture notes, with possibly a little bit of thinking about what the definitions mean, or perhaps running one of the simulators ( Reading quizzes will be available for at least 24 hours before each lecture, and they are due 30 minutes prior to the start of lecture, after which there is no chance to submit. If you have the quiz open at that time, Canvas will automatically submit whatever answers you have entered so far.

Although straightforward, some quizzes can have many questions and take some time to do, so I strongly recommend doing the quiz before the day of lecture, just in case it takes longer than you anticipated. You get to submit twice, so you can correct answers that you got wrong on the first submission. (On rare occasions there may be three submission attempts, for especially long quizzes, but the default number of submissions will be two.)

The lowest two reading quiz scores will be dropped.


The midterm exam will cover topics from the first part of the course, and the final exam will cover only the remaining topics. In other words, the final exam is not comprehensive. Please see the section Exam preparation for more details and for advice on how to prepare for the exams. The dates of the midterm and final are listed on the lecture schedule.

Exam grades may be adjusted, but only to increase scores, never to decrease them. If the median is below 80%, I will adjust the grades to obtain a median of 80%. Unless there is some statistical anomoly, such an adjustment will simply add a fixed number of points to each exam score; e.g., if the mean is 76%, then 4% will be added to each exam score.

No exam scores will be dropped.


Homework must be submitted electronically on either Kodethon or Canvas (which depends on the type of problem). There are two types of homework problems: auto-graded and written. Auto-graded problems are submitted as text files to Kodethon and scored immediately.

Solutions to the written problems are submitted (as a PDF file) to Canvas, but their score will not depend on whether your written solutions are correct. Instead, the written homework score will come from a short (10 minute) 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 Canvas, you may 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 credit for the quiz.

This policy sounds strange, but it has a specific goal: to encourage you to think of the homework as the best way to learn the course material, rather than some bizarre dance done in the hope of getting points. You don't have to worry 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 any online sources to learn how to do the homework. There is no incentive to copy homework from another person or the internet, or to otherwise write something down that you don't understand, hoping to get points. There's no points to get.

Nonetheless, all homework submissions must be your own work (see Academic Misconduct Policy), 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).

No homework scores will be dropped.

Homework optional challenge problems

Occasionally I put "optional challenge problems" on homework. They are not extra credit and are worth no points. What you potentially get out of solving such problems is 1) skill, 2) fun, and 3) admiration from me. The last may seem unimportant. However, for each course I teach, I get at least one request for a letter of recommendation for graduate school/internships/fellowships, or a request to do an undergraduate research project. Sometimes these requests come over a year after the course is done. If you think there's a chance you might eventually make such a request, it's best to regard these problems as not optional.

Piazza participation

You can earn extra credit for helping other students on Piazza if your answers are endorsed by an instructor unsolicited. If you ask for an endorsement, then no matter the quality of your answer, you will not receive any extra credit.

The precise scheme for translating Piazza participation to extra credit points is not specified and will remain that way for the whole quarter. I'll decide something that seems fair at the time final grades are assigned.

Attempted abuse of the system to get extra credit without actually helping someone is against the Academic Misconduct Policy.

Late start policy

If you were unable to enroll or add yourself to the waitlist in the course at the start of the term, and you can produce evidence that you were not able to enroll or waitlist, attend lecture, or access Canvas, please contact me as soon as you are enrolled or waitlisted in the course, and we can arrange to have you make up homework/quizzes whose deadlines preceded your enrollment/waitlisting.

However, this does not apply in the case that you enrolled or waitlisted but thought that you would drop the course (for instance, hoping to be admitted to another course). Once enrolled or waitlisted, you are responsible for attending lecture, checking Canvas and Piazza, and completing assignments/quizzes/exams, just the same as any other student in the course.

Regrade policy

If there is a mistake in grading a problem on an exam or in-lecture quiz, please use Gradescope's "Request regrade" button on the problem where the mistake was made. You will have no more than one week after the grades are published to make a request.

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.

Regrade requests will be ignored if they do not conform to the format described above. Examples of inappropriate requests: requesting a regrade of the entire exam (rather than of a specific problem for a specific reason), or requesting that fewer points be deducted without referencing the rubric, which explains the reasons for the point deductions.

When we make mistakes grading, it is random, not malicious. Thus it is possible that we made a mistake that helped your score. You should be very sure if you request a re-grade that your solution really does qualify for more points according to the posted rubric. If you request a regrade, then it has the potential to lower your score if you were accidentally awarded too many points the first time. So don't think "It can't hurt to try." It can hurt.

Repeated requests to re-grade the same problem, after the original request has been denied, which are not pointing out new information but merely arguing, may be considered "Pressuring an instructor or teaching assistant to regrade work" as the the UC-Davis Code of Academic Conduct. See below for details.

Please note that re-grades only apply to exams and in-lecture quizzes that are graded on Gradescope. There are no re-grades of Canvas reading quizzes, and there are no re-grades for auto-graded homework problems. Typically you may submit solutions to auto-graded problems several times** 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.

**In the past we allowed unlimited submissions. Unfortunately, this had an unintended consequence: based on submission logs, some students would submit repeatedly and frequently without carefully reading the autograder feedback and re-reading the instructions. (One student had 60 submissions over the course of an hour, most of which were identical.) For your own sake, to encourage thoughtful consideration of the instructions and feedback, each problem has a submission limit (for most problems, around 50 attempts). This is so high that you should not reach it under any normal circumstances, but low enough to discourage guessing.

Exam preparation

The midterm and final exam are closed book and closed notes, with the exception of one 3x5 inch handwritten notecard, front and back, for each exam. In-lecture quizzes are completely closed book and closed notes (no notecard). 

The midterm exam will cover topics from the first part of the course, and the final exam will cover only the remaining topics. In other words, the final exam is not comprehensive. Unless announced otherwise during the quarter, the midterm will cover Automata Theory, and the final exam will cover Turing machines, Computational Complexity Theory, and Computability Theory.

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 the question "Will we have to do the following type of problem on the exam/quiz?" is, "Potentially yes, provided that we covered it in lecture or homework".

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. If a previous quarter covered different topics for an exam, then the exam from that quarter may have questions on topics not covered in the current quarter, and it may lack questions on topics that are covered in the current quarter. So you should rely primarily on homework and quizzes from the current quarter for preparation, not on previous exams.

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 difficult homework problems as training by running in the mountains, so that running at sea level (the exam) seems easy by comparison.

In general, it is best to answer an exam or quiz question with the least amount of text that answers the question. It is not a good strategy to simply write lots of text hoping that some of it matches the correct answer. Extra text beyond a fully or partially correct answer can be considered evidence of a lack of understanding of the answer that was written.

If there are multiple answers written, then the maximum credit that will be given is for the answer that gets the fewest points, and possibly 0 points even if every answer on its own would get partial credit. 

Note about the purpose of the notecard: It is unclear to me whether the notecard helps or hurts students. The reason I allow it, but only a small notecard, is that I hope it forces you to organize your thoughts about the material by thinking, "if I could only have a bit of help during the exam, what would I want help with?" Unfortunately, every quarter there are students who clearly use the notecard to transcribe verbatim solutions from previous exams, which are then transcribed onto the current exam, which are then given 0 points because the questions on the exams are different and a correct solution to one is not even a partially correct solution to the other. The way to use the notecard is this: practice doing the written homework, or problems from previous exams, or problems from lecture notes (meaning practice solving them on your own without looking at the solutions), and whatever mistakes you most commonly make, jot down reminders about that on the notecard.

Note about instructor-provided solutions to problem: It can be instructive to see 2 or 3 examples of a particular type of problem, along with a solution to it, before you do it yourself. It is not instructive to see dozens of examples of solutions without trying to solve the problem yourself. The lecture notes contain examples of every type of problem you will have to do, along with solutions. The written homework has more, and we will post solutions for those. I will usually post an exam from a previous term and may or may not post solutions for it if available. Additional examples of problems (without matching solutions) are readily available in the optional textbook and online.

However, after you have 2 or 3 examples of solutions to a specific type of problem, you will not learn how to solve such problems by seeing dozens more problem/solution pairs. You will learn by trying to solve such problems yourself, without seeing a solution. If you get confused, you should ask for help on Piazza. There's more than enough collective knowledge among your peers to figure out solutions without needing to be handed solutions. Students working together to solve a problem, and pointing out flaws that they see in each others' attempts, will learn much more than students who try to collect a giant pile of problem/solution pairs to memorize or transcribe onto the notecard. 

LaTeX/submitting written homework

You must submit written homework as a PDF on Canvas.

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.,,, Dropbox Paper is another recent development that allows embeded LaTeX math.

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 n2 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. Although this is to be turned in on Canvas, I recommend Gradescope's guide for students for advice on using these options. (Gradescope recommends Scannable for iPhone, but I think Genius Scan takes much more readable pictures.)

Some students use a word processing program. I don't recommend this, since it is very tedious to make decent-looking mathematics, but there's no rule against it.

Late homework policy

This late policy applies only to homework submissions. The online reading quizzes have an absolute due time of 30 minutes prior to the start 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). At first, p(h) decreases rather slowly with h, but it decreases more rapidly as time passes until 24 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/24)4), capped above and below at 100 and 0, respectively:


For example, here are the penalized scores for various submission times:

  • on time: 100%
  • 10 minutes late: 99.99999977%
  • 1 hour late: 99.99969859%
  • 6 hours late: 99.609375%
  • 12 hours late: 93.75%
  • 18 hours late: 68.359375%
  • 23 hours late: 15.65363378%
  • 24 hours late: 0%

This policy has several purposes:

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

If you're wondering why it's so important to get homework in on time: Homework is how you learn. I prefer not to put a difficult, problem-solving exercise on an exam unless you have done homework covering that topic. (Although I'll happily put a simple, knowledge-testing exercise on an exam as long as we've covered it in lecture, regardless of whether it's been on a homework.) Imagine taking a programming exam after studying a programming textbook, but without having ever written, compiled, run, and tested programs yourself. It would be a train wreck. This course is no different.

That means there is an order of events with a tight schedule: I assign reading on topic A, you read about topic A and maybe take a reading quiz on it, I lecture on topic A, I assign homework designed to learn topic A, I want you to have at least a week or close to it between covering topic A in lecture and the homework deadline**, you submit that homework, we release homework solutions, I want you to have at least a day to study the solutions, and we finally have an in-lecture quiz on topic A.

So, it's crucial to get homework in on time to avoid disrupting this pipeline.

**To avoid stretching this out too much, and acknowledging that historically, most students start the homework within a few days of the deadline rather than two weeks before the deadline, I'll usually consider any one topic fair game for the homework if it is covered in lecture at least a couple of days prior to the deadline, as long as most of the homework topics are covered close to a week before the deadline.


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 ( verifying your disability and specifying the accommodations that you require.

Academic misconduct policy

The UC-Davis Code of Academic Conduct outlines what is considered academic misconduct.

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.

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 lecture notes) 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.

In all cases, the boundary between "getting ideas" from a website/classmate and "copying" may seem arbitrary, but the foolproof way to make sure you are within the bounds of the policy is follow the advice above: after consulting these sources, but before writing up the homework, put all the sources away and write up the homework without looking at them. If you really learned how to do it on your own, you'll be able to, and if you find yourself tempted to look again while writing the homework, then you didn't really "get ideas"; probably the reason you are tempted to look it up again is to copy. Don't do it.

Special exception for randomized problems: some auto-graded homework problems will be specially marked as "randomized". For these problems only, it is acceptable to show your solutions to other students prior to the deadline. This is because every student is randomly assigned a different problem, so the correct solution for one student would not be the correct solution for another student. However, for problems not specially marked as "randomized", the normal rules apply, and you should not show your solutions to other students prior to the late deadline.

Academic misconduct: Exams

Naturally, cheating on exams will be held to the same standard, and anyone caught cheating will be dealt with just as with cheating on the homework.

Academic (and legal) misconduct: Course materials

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.

Academic misconduct: Piazza

As explained in Grading policy, students can receive extra credit for helping other students on Piazza. Piazza unfortunately allows students to modify one another's answers, potentially making it difficult to clearly assign credit to an answer. It is against the Academic Misconduct policy to attempt to obtain undeserved extra credit.

Academic misconduct: Following course policies

The following sentence appears in the UC-Davis Code of Academic Conduct: "misconduct includes... 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." The policies in this syllabus have been developed and tested over many years and have proven to be reasonable and appropriate for hundreds of past students, so there is little reason to change them now or to grant exceptions. If you request an exception or a change to a course policy that is clearly stated in this syllabus, unless there is a truly exceptional reason to grant it (such as a medical emergency or another professional commitment that cannot be changed), the request will likely be politely ignored. Repeated requests, however, will be considered "pressure" as in the UC-Davis Code of Academic Conduct.

Course Summary:

Date Details Due