Course Syllabus

ECS 120: Theory of Computation, Spring 2020

Course staff

Instructor	Dave Doty	doty@ucdavis.edu	https://ucdaviscoe.zoom.us/j/559206636
TA	Mahsa Eftekhari	mhseftekhari@ucdavis.edu	https://ucdaviscoe.zoom.us/j/881649078
TA	David Haley	drhaley@ucdavis.edu	https://ucdaviscoe.zoom.us/j/405933575

I do not check Canvas email. Please post questions on Campuswire (see Websites below for instructions on how to access it), or for questions of a personal nature, write an email directly to me.

Remote interaction during the COVID-19 pandemic

Here is an FAQ for students dealing with the changes forced on us by the pandemic: https://ebeler.faculty.ucdavis.edu/resources/faq-student-resources/

See also this website for information about help, including access to computers or Wifi internet if you don't have easy access to these: https://keepteaching.ucdavis.edu/student-resources

We will use a number of tools for remote interaction while the COVID-19 pandemic remains a threat.

Zoom

Zoom will be used for audio and (if necessary) video for interacting remotely.

The free version of Zoom Client for Meetings will suffice for students. The course staff have Zoom Pro licenses, which will be used for online discussions and office hours.

See Google Calendar below for my online office hours. I'll paste a link to a Zoom meeting, which you click on to join the meeting.

Please follow Zoom etiquette rules.

hackmd.io

hackmd.io is like Google Docs, but uses Markdown/Latex syntax. I may 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 1b (Wednesday of the first week), I use hackmd, so you can see some examples of Markdown and Latex.

Meeting times

Lecture:

Mon/Wed/Fri 10:00am-10:50am, https://ucdaviscoe.zoom.us/j/559206636 Wellman 106

Discussion:

Section A01: Tues 8:00am-8:50am, https://ucdaviscoe.zoom.us/j/869996899  Haring 2016 

Section A02: Thurs 12:10pm-1:00pm, https://ucdaviscoe.zoom.us/j/723783604 Haring 1204

Office Hours:

See below for times of office hours.

https://ucdaviscoe.zoom.us/j/881649078 (David H)
https://ucdaviscoe.zoom.us/j/405933575 (Mahsa)

The scheduled lecture rooms are listed above, but due to the COVID-19 pandemic, there are no physical meetings as of the start of the quarter. We don't know how long this will last, but I suggest planning as though it could last the entire quarter. I adapted this syllabus from an earlier term and changed some information to reflect the current situation, but I may have missed some parts, in case you see something that references in-person activities.

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. (Yes, this applies even while all instruction is remote. The point is not the size of the classroom, it's how the TA's attention is divided among students.)

Final exam:

Friday, June 5, 10:30am-12:30pm, location TBD

[During Spring 2020, the midterm and final exams have been replaced by 4 shorter online take-home quizzes.]

Lecture format for remote instruction

Normally lecture would be done live in a classroom, but this is not possible in Spring 2020 due to the COVID-19 pandemic.

Unfortunately, I don't know if there is any way to completely replicate the experience of a live lecture using remote tools, especially in a large class. The way I teach relies heavily on reading nonverbal cues from students to pace the lecture and know when to pause and when to re-explain something. I also worry that in a live internet-based presentation, some small number of students will experience connection trouble and be unable to hear what I'm saying or see what I'm sharing.

So, things will work differently, and I ask you to be patient with me as we try out ideas.

I will pre-record lectures. Instead of a long 50-minute lecture, three times per week, I will partition each 50-minute lesson into smaller chunks, but I'll still group them by lecture day, because that's how I've already organized all the course material. It's harder to sit and watch a video than to sit in a lecture hall and listen (though the latter isn't that easy either!), so this will help you to break it up a bit. See the lecture schedule for links to these videos.

You should watch these lecture videos on your own, and read the associated reading assignment, which covers the same material, before the scheduled lecture time. I will set up a Zoom meeting during each scheduled lecture hour, but it will be more like office hours, where you can ask questions about the lecture. Some students requested that I record these informal meetings. I asked students uncomfortable with that to let me know privately, and no one did. So I will record these informal meetings and post links to them.

I will also still hold office hours at other times. The difference between them is that it is preferable for the scheduled lecture time to involve generic questions about the lecture material, whereas office hours is more appropriate for questions that might not be of interest to all students (e.g., about a specific homework problem). I won't make any rules and will be willing to answer any questions about the course in either setting, but think of the scheduled lecture as being first and foremost for questions about the material presented in the recorded lectures.

Office hours are usually a way to have personal private discussions by closing the door, but that won't work very well this quarter, such discussions should take place over email (preferably) or if necessary, a scheduled online call.

I will also adapt how the course is run based on feedback from students and how it appears to be working. Some things won't work very well, and I ask for your patience as we navigate during this difficult time.

Websites

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

site	purpose	link
Campuswire	course announcements, questions/discussion	https://campuswire.com/p/G214DFB6C (code 8905)
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

Campuswire 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 Campuswire page. I've used Piazza in the past, but I've heard good things about Campuswire, particularly that it has a more stringent privacy policy compared to Piazza.

If you are enrolled in the course and have access to the Canvas page, you should also be able to access the Gradescope page. But this is the first year that Gradescope has been integrated with Canvas. If you have trouble accessing Gradescope, please post on Campuswire and we can try to figure out if students need to do anything extra.

Constructive feedback about any aspect of the course is always welcome. Please write me an email at doty@ucdavis.edu.

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

Course objective

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

A major objective is also philosophical: to treat computer science not merely as a tool for automating computation to aid in other endeavors, but as a fundamental natural science itself. P=NP, or it doesn't. 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-. 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 and other scheduled online meetings

Note that for Spring 2020 during the pandemic, the distinction between the lecture time and office hours is blurry. Since lectures delivering new content are pre-recorded, the scheduled lecture time is less formal, and mostly a chance to ask questions about the lecture content. Office hours can be more for homework questions, although either can be used for either. However, I'd like to prioritize questions about lecture content during the scheduled lecture time.

Departmental PTA (permission to add) policy

The CS department is strict about how PTAs are given out. Please read about the policy here: https://www.cs.ucdavis.edu/blog/pta-policy/

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 here, which also lists dates of in-lecture quizzes and exams. [Note: no in-lecture quizzes or exams during Spring 2020] 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.

During Spring 2020, the lecture schedule contains links to videos of pre-recorded lectures. Please watch those prior to joining the Zoom call during the scheduled lecture time.

Asking questions online

Please use Campuswire (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 Campuswire 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 Campuswire/email to contact the course staff instead.

Campuswire 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 Campuswire, 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 Campuswire, then that is a more reliable source than my memory, and if I didn't write them on Canvas or Campuswire 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

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 30 minutes prior to the start of lecture, after which there is no chance to submit. [During Spring 2020, this is shortened to 5 minutes prior to the scheduled lecture time.] 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.)

Exams

Note: this section is obsolete, since we will not have in-person, timed exams during the COVID-19 pandemic. I am keeping it here for future quarters, but don't pay attention to it.

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.

Exams Take-home quizzes (COVID-19 edition)

Normally this course would have almost 80% of the grade determined by midterm and final exams taken in a classroom, closed-book, as well as four short closed-book, in-lecture quizzes, each related to one of the four homeworks. That isn't possible in Spring 2020. Instead, the grades are distributed differently, with more grading weight put on parts of the course that remain, such as reading quizzes and autograded homeworks.

Instead of four small quizzes and two large exams in a classroom with closed notes, after each homework (except HW0), there will be an open-book (meaning you can use my lecture notes) "take-home" quiz on Gradescope. Written homework will be assigned and collected on Gradescope, but it will not be graded. However, you are required to complete and turn it in. You are allowed to discuss how to do the written homework with each other on Campuswire, 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, which is why we require you to attempt it and turn it in.

The take-home quiz is open-book, i.e., you may have the lecture notes available while taking it. However, it is "closed-internet" and "closed discussion". Questions on the take-home quiz will be similar to questions from the autograded homeworks, written homeworks, and reading quizzes.

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):

1. Chapters 2, 3, 4
2. Chapters 5, 6, 7
3. Chapters 8, 9, 10.1
4. Chapters 10, 11

Time to complete quiz: The first take-home quiz will be timed for one hour. You can choose to start it at any time on the date it is due, and it must be completed within an hour, or by 11:59pm, whichever comes first. So if you start at 11:30pm, you would only have 30 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 both 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.

Homework and take-home quizzes

Homework and take-home quiz solutions 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 scored. Take-home quizzes are scored.

[This paragraph added to clear up confusion after HW1, SQ 2020]: Although written homework is not checked for correctness, 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).

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.

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 or take-home quiz scores will be dropped.

Note: the remainder of this section is obsolete, since we will not have in-person quizzes during the COVID-19 pandemic. I am keeping it here for future quarters, but don't pay attention to the rest of this section.

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. The topics on the quiz will be the same as the written and auto-graded homework.

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.

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. Read here to find out why.

Campuswire participation

[TODO: this was written for Piazza, not sure how Campuswire works yet, since this is the first year I've used it. In particular, I don't know how finely I will be able to track participation on Campuswire. Piazza was able to give very fine-grained data, such as the number of answers a student gave that were endorsed by an instructor. Right now I'm not even sure if Campuswire has the concept of an instructor endorsing an answer. This will be updated as I learn more about Campuswire.]

You can earn extra credit for helping other students on Campuswire 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 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 Campuswire, 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 or in-lecture quiz [in Spring 2020, this section applies to graded take-home quizzes], 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 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.

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. You should be very sure if you request a re-grade that your solution really is correct. 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 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

Note: Portions of this section are obsolete, since we will not have in-person, timed exams during the COVID-19 pandemic. However, I do recommend reading it for advice on how to prepare for take-home quizzes. (Long story short, pay attention to assigned work in the course such as homework and reading quizzes.)

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. (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 terminology even though this isn't a discrete math course.)

I will often 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 1 matches a 2-point rubric item, then 2 points are deducted even if answer 2 does not match that rubric item. If answer 2 matches a 3-point rubric item that does not match answer 1, 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 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 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 Campuswire. 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 and take-home-quizzes

You must submit written homework and take-home quizzes 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 (which I might use for online office hours) and on Gradescope (which has a similar syntax): https://hackmd.io/cmThXieERK2AX_VJDqR3IQ?both

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 n² 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 30 minutes prior to the start of lecture. [During Spring 2020, this is shortened to 5 minutes prior to 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 autograded homeworks, this penalty applies to the score for the homework, and on unscored written 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)⁴), 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. [in Spring 2020 there are no -in-lecture quizzes, but there is a take-home quiz on the same topics]

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.

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.

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

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 grader stated something specific about your submitted solution that is untrue. In this case, you may point out the specific error.

An explicit request to change the final grade is one way to violate the policy of not pressuring course staff. However, there are many other ways to pressure course staff about grades, all of which are forbidden. Pressure also includes things such as

• Mentioning, for any reason whatsoever, 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. We are happy to help you understand how to solve a problem how to tell if a solution is correct, and to point out problems 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). 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 is inappropriate, whatever the reason. If the grader made a mistake, point out the mistake, and we'll figure out whether that means you should get more points. Examples of common invalid reasons for a regrade request are
  • "I need a [some grade] in this course because [some reason]."
  • "I think this is too many points to deduct and I should get more partial credit."
  • "I discussed it with the instructor/TA and they said it was fine." This is not only against policy, but it indicates that you already violated the policy by asking course staff to confirm a solution is correct before submission, and it confirms that the discussion was not intended to aid your understanding, but instead was a set-up to pressure the course staff after the work is graded.
• Asking what your course grade will be. If coursework is not all graded, then we don't know any 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 as well as I do, I will interpret that "question" instead as a statement, "I want my grade to be higher, and I'm warning you that I'll be upset if it isn't."
• Asking whether the grading scale for the course will be adjusted or if a curve will be applied. The 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 Campuswire). This is also true of randomized autograded problems (see below). However, do not share potential solutions to non-randomized autograded problems with each other.

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 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: Campuswire

As explained in Grading policy, students can receive extra credit for helping other students on Campuswire. [TODO: this was written for Piazza, not sure how Campuswire works yet. In particular, I don't know how finely I will be able to track participation on Campuswire. Piazza was able to give very fine-grained data, such as the number of answers a student gave that were endorsed by an instructor.] 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.