Course Syllabus
ECS 120: Theory of Computation
Course staff contact information
| Instructor | Dave Doty | doty@ucdavis.edu |
office hour Zoom link (office hour times listed under Office Hours below) |
| TA | Mahsa Eftekhari | mhseftekhari@ucdavis.edu | office hour Zoom link |
| TA | Josh Petrack | jgpetrack@ucdavis.edu | office hour Zoom link |
| TA | Aaron Ong | office hour Zoom link |
I do not check Canvas email. Please post questions on Piazza (see Websites below for instructions on how to access it), or for questions of a personal nature, write an email directly to me.
Meeting times
Lecture:
Mon/Wed/Fri 1:10pm-2:00pm, Hunt 100
Discussion:
Section A01: Mon 2:10 PM - 3 PM, Walker Hall 1320 (Josh)
Section A02: Wed 3:10 PM - 4:00 PM, Young Hall 184 (Aaron)
Section A03: Fri 4:10 PM - 5:00 PM, Haring Hall 2016 (Mahsa)
Office Hours:
See below for times of office hours. All office hours are offered over Zoom only, except for Aaron, who will be present on both Zoom and Kemper 53 during his hours.
Dave Doty: see Zoom link for office hours in contact information above
Mahsa: Zoom link
Josh: Zoom link
Aaron: Zoom link
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:
Friday, Dec 10, 6:00pm-8:00pm, Hunt 100 (note: we may do a 50-minute final exam during the last week of instruction instead)
Websites
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 |
https://piazza.com/ucdavis/fall2021/ecs120/home access code: ecs120 |
| Canvas | homework, reading quizzes, storing grades, general course information | this page |
| Automata simulators | testing automata | web.cs.ucdavis.edu/~doty/automata/ |
| Gradescope | auto-graded homework, exam feedback |
click on "Gradescope" on the left menu in Canvas |
Piazza is external to UC-Davis, so you will have to set up accounts if you don't already have them. Use the code above to access the ECS 120 Piazza page. If you are enrolled in the course and have access to the Canvas page, you should also be able to access the Gradescope page. For more general help regarding UC-Davis (not necessarily related to this course), please see UC Davis Student Resources.
Constructive feedback about any aspect of the course is always welcome. Please write me an email at doty@ucdavis.edu.
hackmd.io
hackmd.io is like Google Docs, but uses Markdown/Latex syntax. I sometimes use it for hosting online office hours, since it's a decent way for multiple people to have a "virtual blackboard" they can all type on. Here is a page I put together showing some examples of Markdown/Latex syntax: https://hackmd.io/cmThXieERK2AX_VJDqR3IQ?both
Also, in the pre-recorded lectures for lecture 1c (Friday of the first week), I use hackmd, so you can see some examples of Markdown and Latex.
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 or MAT 108 with a minimum grade of C-. It is also strongly recommended that you have completed ECS 36C (Data Structures; the name was ECS 60 until Fall 2018) or ECS 32B with a minimum grade of C-, or an equivalent course. Click here to see why ECS 36C or 32B is recommended.
Office hours
All office hours this term are virtual. See course staff contact information above for Zoom links; also included in the calendar below.
Departmental PTA (permission to add) policy
The CS department is strict about how PTAs are given out. Please read about the policy here: https://cs.ucdavis.edu/undergraduate/current-majors/policies
Textbook
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.
Recommended 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 many of the same topics discussed in Sipser's book. It is also a good source of problems for practice. However, that textbook is not required.
Other good textbooks on this subject, which are even more comprehensive than the lecture notes or Sipser's textbook (and also more formal and a bit more difficult to understand) are Automata and Computability by Dexter Kozen, and Introduction to Automata Theory, Languages, and Computation , by Hopcroft, Motwani, and Ullman.
Lecture schedule
The lecture schedule contains the reading assignments and can be found in the "Lecture Schedule" link on the left, which also lists dates of 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 pre-planned absence (that you tell me about at least a week in advance) for a legitimate excuse such as a job interview that cannot be rescheduled.
Asking questions online
Please use Piazza (see above for link). 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.
Piazza questions should be related to understanding the course material and logistical questions (e.g., how to use Gradescope). Inappropriate posts will be deleted, including insults, personal requests, complaints, advertisements, etc.
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.
Grading
Weighting of different parts of the course is given on the right, under "Assignments are weighted by group:".
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 |
Grades are based on reading quizzes, homework, take-home quizzes, and exams, each explained below.
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 Monday of week 3, and 4c is Friday 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 (http://web.cs.ucdavis.edu/~doty/automata/). Reading quizzes will be available for at least 24 hours before each lecture, and they are due 40 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.)
Some number of the lowest reading quiz scores will be dropped. (How many varies by term, but hopefully Canvas displays it to you.)
Homework
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.
After the late deadline (see Late homework policy below), solutions for the written homework will be released. These are good to study as examples of what a concise and correct proof looks like, to help study for the quizzes and exams.
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. Written homework is checked for completeness, but not fully for correctness. This does not mean that you don't have to do the homework, and it also does not mean that you can submit anything you want and get credit. Briefly, each submitted solution must represent, in the judgement of the course staff, a serious attempt to solve the problem. Here are a few examples of ways to fail to meet this standard, which would not get credit because they indicate that there was not even an attempt to solve the problem: leaving the problem blank, writing the same solution for several problems, giving a solution not of the form that was asked (e.g., the problem asks for a DFA and you give a regex, or it asks for a counting argument and you give a DFA). See here for a more detailed explanation of this policy and what you are expected to submit.
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.
Nevertheless, all 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.
Autograded homework
Autograded homework can be submitted multiple times. The purpose is not to test what you already know, but to allow you to learn how to do the problem. For this reason, 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.
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) fun, and 2) 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. Read here to find out why.
Take-home quizzes
After each homework (except HW0), there will be an open-book (meaning you can use my lecture notes) "take-home" quiz on Canvas. As discussed above, written homework will be assigned and collected on Gradescope, but it will not be scored for correctness. You are allowed to discuss how to do the written homework with each other on Piazza, including sharing and critiquing each others' solutions. The purpose of the written homework (as with the reading quizzes and auto-graded homework) is to prepare you for the quiz (and subsequent exams), which is why we require you to make a serious attempt at the homework. Without the serious attempt, you will be seriously unprepared for the quizzes and exams that make up most of your course grade.
This take-home quiz is open-"book". This means that you can consult the lecture notes (notes.pdf on the "Lecture notes" page in Canvas), as well as any content put on the Canvas page (such as slides listed on the page "Lecture notes"), or links in the syllabus (for instance, links to guides on using LaTeX syntax for mathematics, or the automata simulator), as well as links given in the quiz. In fact, you are encouraged to use the simulator while taking the quiz to help test any automata you submit.
You may not, however, consult any other sources, including any other people and any other websites besides those discussed above.
The take-home quiz topics are not cumulative. (Although of course I still expect you to be familiar with topics from previously in the course, but the problems will more resemble the homework and reading quizzes from the sections covered in the associated reading assignments.)
Topics: The four take-home quizzes will respectively cover the following parts of the lecture notes (excluding optional sections):
- Chapters 2, 3, 4
- Chapters 5, 6, 7
- Chapters 8, 9, 10.1
- Chapters 10, 11
Time to complete quiz: The take-home quiz will be timed for 30 minutes. You can choose to start it at any time on the date it is due, and it must be completed within 30 minutes, or by 11:59pm, whichever comes first. So if you start at 11:50pm, you would only have 10 minutes to complete it.
Academic conduct policy for take-home quizzes: You are not permitted to access the internet for the purpose of obtaining help with the quiz problems, nor to communicate with other people about it (including other students in the course). Of course, we have no way to enforce this remotely. However, we will check for suspiciously similarity between your solutions and those of other students, websites (we have access to the same internet that you do), and solutions used in previous quarters of this course. The Academic Misconduct rules below apply.
Exams
The midterm and final exams are paper-based, proctored exams given in person.
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 significantly 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 median is 76%, then 4% will be added to each exam score.
If you miss an exam for a legitimate medical reason, you must provide a doctor's note that states you are excused from school for the day of the exam. If it merely mentions that you visited the health center, but does not indicate that you are excused, then it will be treated as though you simply skipped the exam.
No exam scores will be dropped.
Topics: The midterm and final will respectively cover the following parts of the lecture notes (excluding optional sections):
- Chapters 2, 3, 4, 5, 6, 7
- Chapters 8, 9, 10, 11
Leaving problems blank. For written problems (not multiple-choice or true-false), you receive 50% credit for leaving the problem blank. (Or making it clear you intended to skip it, for instance crossing out a first attempt and writing the word SKIP.) The reasoning is that I want to discourage guessing if you don't know how to do a problem. If you really are stumped and have no clue, then it's very unlikely that guessing will get much partial credit, so taking 50% credit is your best bet. This is good practice outside of class as well. If someone wants me to do a task (for example, developing some critical piece of software in a code base, or fixing the brakes on a car, or performing brain surgery), but I don't know how, everyone is better off if I just admit that rather than bluff my way through. I want to officially encourage this sort of honesty: work hard to learn what you can in this course, but don't be afraid to admit if something is just stumping you.
Answering questions during exams. My answers to questions from students during the exam will be in the form of official written clarifications on the board (and maybe a verbal announcement), to avoid giving an unfair advantage to the student who asked the question. If you have a question, raise your hand, and I or a TA will listen. If I decide that some exercise was phrased ambiguously and needs to be clarified, I'll write an official clarification on the board for all students to see, and if I don't write such a clarification, it means I think the question (and the background knowledge expected for the exam) already has all the details needed to answer it.
Piazza participation
Piazza participation is not required, but it is strongly encouraged as a way to seek help in learning the course material. Additionally, you can earn extra credit for significantly helping other students on Piazza.
The precise scheme for translating 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. It has something to do with how many helpful responses a student gives to other students. (And even how many useful questions a student asks, e.g., if these help the instructor to find real errors in the lecture notes or quizzes.)
The reason there's no automated algorithm is that I only want to offer extra credit to students who really are helping others. Unfortunately, every year one or two students get the impression that the extra credit is some automatically calculated thing that will give them more points if they can only answer a lot of questions and somehow get other students to upvote the replies.
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. It is your responsibility to alert the course staff if you cannot access something due to adding the course late.
Regrade policy
If there is a mistake in grading a problem on an exam, 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, but sometimes less, particular at the end of the quarter.
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 dismissed 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 more points or partial credit be given, without actually explaining how the rubric items were applied mistakenly (the rubric explains the reasons for the point deductions).
If we make a mistake in grading, it is random, not malicious. Thus it is possible that we made a mistake that helped your score. 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 in the UC-Davis Code of Academic Conduct. See Academic Conduct below for details.
Please note that re-grades only apply to exams 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.
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.
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. (However, this doesn't mean you don't need to know any automata theory on the final: there are interesting questions about computability and complexity that involve automata. It's just that there won't be any questions only about automata. At that point it is like prerequisite material, just as you need to know discrete math concepts even though this isn't a discrete math course.)
I will sometimes post an exam from a previous term to give a sense of the 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/homework/reading quiz".
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. Furthermore, even if we covered a topic, the exam that quarter may simply have omitted a question on the topic, since having a question on every single covered topic would make the exam too long. 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.
Here's an example of how writing too much can hurt: If there are multiple answers written, then the rubric will be applied to deduct points from each. For example, if answer A matches a 5-point rubric item, then 5 points are deducted even if answer B does not match that rubric item. If answer B matches a 3-point rubric item that does not match answer A, then 3 additional points will be deducted.
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 they then transcribe 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 problems: 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 and written homework contain examples of every type of problem you will have to do, along with solutions. Additional examples of problems (without matching solutions) are readily available in the optional textbook and online.
However, after you have seen a few 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 on Gradescope. While plain text is sufficient for most of what you will need to write, occasionally it will be useful to use LaTeX commands for mathematics.
Here is a page I put together showing some examples of Markdown/LaTeX syntax, which shows how to type mathematics nicely on hackmd.io https://hackmd.io/cmThXieERK2AX_VJDqR3IQ?both (which I sometimes use for online office hours) and for Gradescope: https://hackmd.io/cmThXieERK2AX_VJDqR3IQ?both#Gradescope-MarkdownLatex, which has a slightly different syntax, the same as that for Piazza, essentially requiring double dollar signs, such as $$x^2$$ for x2 (instead of hackmd's use of single dollar signs, such as $x^2$ for x2).
For several decades a full LaTeX installation was the only serious way to produce mathematical text, 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://stackedit.io/, https://www.madoko.net/, https://upmath.me/, Dropbox Paper. The latter are much easier to learn than full LaTeX, because the "source code" mostly just looks like normal text. For example, typing *emphasis* will render as emphasis, or **strong emphasis** for strong emphasis.
Gradescope supports embedded Latex in its written answers, and they will support Markdown in the future. I made many of the Spring-2020-specific parts of this syllabus when Markdown was supported by Gradescope, but they disabled it while they work on higher-priority things. However, because raw un-rendered Markdown text is readable, it's still a good way to type with plain text even if it is not rendered by a Markdown engine.
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. Even if Gradescope did not render LaTeX, it would still make sense to write text such as n^2.
The ECS 120 page on LaTeX has advice on how to set up a complete LaTeX installation, but it will not be needed for this course, since all submissions will be plain-text typing on Gradescope.
Late homework policy
This late policy applies only to homework submissions. The online reading quizzes have an absolute due time of 40 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.
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:
- 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.
- 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 a take-home 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.
Accommodations
If you have a documented disability and anticipate needing accommodations in this course, please meet with your instructor as soon as possible, before the end of the first week of lecture. Request that the Student Disability Center staff send the proper form (https://sdc.ucdavis.edu/) 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 the Office of Student Support and Judicial Affairs, and anyone found responsible for academic misconduct will receive an automatic F in the course.
Academic misconduct: Following course policies
Like much of the academic misconduct policy, this message is not aimed at most students. 99% of all students in every class are completely reasonable, and they do not attempt to emotionally manipulate course staff into boosting their grades. They would already follow these guidelines without being told. Unfortunately, these 99% of students may find the following guidance intimidating, which is not my intention. I hope it does not discourage students from speaking with me about legitimate concerns they have about the course.
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.
With regard specifically to your grade: There is one reason and one reason only to contact the instructor or TAs about grades: the course staff made an objective error in calculating or recording your grade. In this case, you may point out the specific error. Examples of valid discussion of grades to have with instructor/TA/grader:
- “The grader stated that my solution doesn’t handle checking for repeated nodes in the path, but the 3 lines at the bottom do check for repeated nodes in the path.”
- “My grade is listed as 90 on Gradescope but it shows up as 80 in Canvas.”
- “The rubric item says my DFA rejects the string 010, but that string will take it to state q2, which is an accepting state.”
These are permitted because they all point out a specific mistake, as opposed to expressing your general disagreement with a low grade.
The most direct way to violate this policy is to make an explicit request to change your final grade.
However, there are many other ways to pressure course staff about grades, all of which are forbidden. Pressure also includes:
- Mentioning that you "need a [some grade] in the course" or "need to pass" for some reason (because you want to graduate by a certain date, because you have a job/internship, etc.). 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 promise that your solution will get full credit.
- Especially on an exam or quiz, asking whether your solution is correct is not permitted; if you understand the course material, you will know how to tell whether it is correct.
- [Note for ECS 120 students: Since we don't check non-autograded written homework for complete correctness, this section is less relevant for ECS 120, but I leave it here as good advice to follow in other courses. Part of the reason we don't score written homework for complete correctness is to encourage you to think of the goal of written homework, not to get points, but to develop an understanding of what a good solution to a problem looks like.] For homework, we are happy to help you understand how to solve a problem, how to tell if a solution is correct, and to point out obvious problems that we see in your solution. But ultimately it is up to you to produce a solution and make a convincing argument that it 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 this and just trying to understand how to solve a problem or understand what format of answer is expected (which are allowed, for instance you might ask, “Is it enough to draw transition arrows, or should we also define δ explicitly?”). 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 that you appear to be trying to get us to tell you what you should write to get full credit, this is against policy.
- Repeated regrade requests that do not conform to the format described in the Regrade requests section. In particular, requesting more points or partial credit 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 invalid regrade requests:
- "I need a [some grade] in this course."
- "I think this is too many points to deduct and I should get more partial credit." (without pointing out specifically how the rubric items associated with the point deductions were mistakenly applied)
- "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 better than you do what your numerical score will be; it depends on what scores you get. You can figure out the range of possible scores by calculating what your score will be if you get all 0's on all remaining coursework, and if you get all 100%'s on all remaining coursework. All we know is that your grade will land somewhere between those two. 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 exactly 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, or if letter grades will be bumped for scores close to a letter grade cutoff. The grading scale for the whole course, and the potential adjustments to exam scores, are both stated clearly in the syllabus. 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. However, since written homework is not scored directly, you may share potential solutions with classmates and discuss them (in person or on Piazza). However, you should still write up your own solution. (See below.) This is also true of randomized autograded problems (see below). However, do not share potential solutions to non-randomized autograded problems with each other prior to the late deadline.
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 produce 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 produce a homework that you submit without access to the person/website 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 or book and to get ideas for how to do the homework, you must indicate precisely which website/book it was. Furthermore, even if you cite a source, it is dishonest (and pointless for your education) simply to copy it; even with a citation, copying text remains misconduct, since you are misrepresenting their words as you 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, 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 (as well as the written homework, which is not scored directly), 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 autograded 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, videos, 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. It is against the Academic Misconduct policy to attempt to obtain undeserved extra credit. Some examples of this:
- Replying to a question that has already been answered, but offering no new information beyond the existing answers.
- Editing another student's answer without offering new relevant information.
- Replying to a question long after it has been asked, when the answer cannot any longer be helpful. (e.g., when the question is about a quiz that has already passed)
- A group of students all asking questions and upvoting each others' answers. (This happened once.)
Course Summary:
| Date | Details | Due |
|---|---|---|