Course Syllabus

ECS 120: Theory of Computation

Table of Contents

Course staff contact information
Remote interaction during the pandemic
Meeting times
Websites
Course objective
Prerequisites
Office hours
Departmental PTA (permission to add) policy
Textbook
Lecture schedule
Asking questions online
Grading
Late start policy
Regrade policy
Exam preparation
LaTeX/submitting written homework
Late homework policy
Accommodations
Code of Academic Conduct

Course staff contact information

Instructor Dave Doty doty@ucdavis.edu Zoom links: lecture, office hours
TA Mahsa Eftekhari mhseftekhari@ucdavis.edu Zoom link (for office hours)
TA David Haley drhaley@ucdavis.edu Zoom Link (for office hours)

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 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. The Zoom link is the same as for lecture. (See contact information at top.)

Please follow Zoom etiquette rules. I have etiquette requests of my own:

  1. If you have the bandwidth, please turn on video. (But stay muted unless you have a question.) It's much easier to tell if I'm on the right track with an explanation if I can see facial responses of students. Of course, I understand some students may be stuck in a situation where it is not reasonable to turn on video, e.g., there are children running around. But unless you have a good reason to keep it off, please turn on your video. Otherwise it's as though you showed up to a real classroom only to hold your coat in front of your face so I can't see you.
  2. Please only sign into the meeting if you are paying attention and are willing to participate. Attendance is not required, and I will not be checking for attendance or giving out any information not available online. So please do not just sign into the meeting only to walk off somewhere else in your house. I will often put students in breakout rooms for discussion, or otherwise invite participation. It's irritating when I visit a breakout room to check on discussion, only to see a student's video and microphone off, who does not reply when I address them directly.

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.

Lecture format for remote instruction

Normally lecture would be done live in a classroom, but this is not possible during the pandemic.

Unfortunately, from experience, I am not able to 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. Internet connection trouble for some students also disrupts this.

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 (link to lecture schedule on left) for links to these videos.

You should watch these videos on your own 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. Since the discussion on Wednesdays, even during normal quarters, is similarly informal, Eric (the TA) will do both the scheduled lecture time and the discussion on Wednesdays, and it will essentially be one longer discussion.

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.

Meeting times

Lecture:

Mon/Wed/Fri 10:00am-10:50am, Zoom link for lecture for Dave Doty in contact information above

Discussion:

Section A01: Wed. 11:00am-11:50am, Zoom link

Section A02: Fri. 12:10pm-1:00pm, Zoom Link 

Office Hours:

See below for times of office hours.

Dave Doty: see Zoom link for office hours in contact information above

David H: Zoom Link 
Mahsa: 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. (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 the pandemic, the midterm and final exams have been replaced by 4 shorter online take-home quizzes.]

 

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/G95B38D82 (code 7412)

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.

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 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 and other scheduled online meetings

Note that 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://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 in-lecture quizzes and exams. [Note: no in-lecture quizzes or exams during the pandemic] 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 the pandemic, 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 the pandemic, 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 during the pandemic. 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 Canvas and/or 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.

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

  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

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.

After the late deadline, 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. [Normally I would just post solutions on Campuswire, but in Spring 2021, I will also try using Gradescope to release these solutions, to see how well that works. UPDATE: It doesn't work so well, so I'll just post solutions on Campuswire.]

Note about written homework: 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 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

You can earn extra credit for helping other students on Campuswire.

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. Some examples of this:

  • Replying to a question that has already been answered, but offering no new information beyond the existing answers.
  • 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.)

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 [during the pandemic, 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 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. 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 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 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 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 30 minutes prior to the start of lecture. [During the pandemic, 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 [during pandemic, there are no in-lecture quizzes] 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 (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:

late-penalty.png

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. [during the pandemic 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.

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 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."
    • "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 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 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: Campuswire

As explained in Grading policy, students can receive extra credit for helping other students on Campuswire. It is against the Academic Misconduct policy to attempt to obtain undeserved extra credit.

Course Summary:

Date Details Due