CS 121 / CSCI-E 121 - Introduction to Theoretical Computer Science

Syllabus - Fall 2017

Instructor: Boaz Barak

Tentative version - subject to change!

Physarum polycephalum

Physarum polycephalum slime mould computing the shortest path in a maze.

TL;DR: This course is going to involve a lot of reading. For starters, you should read the whole syllabus.

Overview

Computation has been with us since ancient times, but the last decades have seen a dramatic expansion in the reach of computation, as well as of our notion of what computing or algorithms are. Quantum computing is reshaping what we think of as the computational abilities of the physical world. Increasingly, we also use computation as a way to understand physical systems ranging from the flocking of birds to the forming of crystals. We have learned that there are many ways to judge algorithms beyond their time and space complexity. The interactions between algorithms and society, in contexts as varied as deciding credit scores, analyzing census results, or cryptocurrencies, raise many questions including incentive-compatibility, privacy, fairness, and governance. The role of randomness in computation has significantly increased, both in using randomness to solve classical problems, as well as modeling average case and learning problems.

This course provides a broad introduction to computation in many of these contexts. We will study the fundamental capabilities and limitations of computation, including the phenomenon of universality and the duality of code and data. Some of the questions we will touch upon include: Are there functions that cannot be computed? Are there true mathematical statements that can’t be proven? Are there encryption schemes that can’t be broken? Is randomness ever useful for computing? Can we use the quirks of quantum mechanics to speed up computation?

While many students have experience with executing algorithms (whether on a computer or pen-and-paper algorithms such as solving equations, integrals etc..), studying questions such as whether a certain algorithm exists requires a different type of thinking than you might have encountered so far. Learning a different way of thinking can be extremely rewarding in its own right, but it is of course not a trivial task, and many students may find this course difficult, especially in the beginning. This is completely normal - I found this material difficult when I first encountered it - and with time and hard work it becomes easier. As a student in CS 121, you will have ample resources to help you in this journey, including the lecture notes, lectures themselves, sections, office hours, and online forums.
The teaching stuff is dedicated to helping you succeed in this course. If you work hard from day one and make sure to stay on top of the material, then you should do very well.

Specifically, to succeed in this course you need to do the following:

  1. Before the first lecture (or at least no later than the end of shopping week): do homework zero and read the notes for the mathematical background and introduction lectures.

  2. You should read fully and deeply the lecture notes before each lecture. This is absolutely essential, as I will not repeat in the lecture all the notes’ content. Rather, I will focus on the key conceptual notions and the points which students found most confusing, so please come prepared with questions!

  3. Every week you will need to do via canvas two online multiple-question quizzes on the lecture notes for next week (accounting for 15% of total grade), as well as a more significant problem set (“pset” for short a.k.a “homeworks”) on the current week’s material (accounting for 30% of the total grade). The problem set will be given out on Thursdays and due the next Wednesday at 11:59pm. You can work in pairs on the problem set, but you do the quiz on your own, see below for all the policies, etc…

  4. Even though you can work in pairs on problem sets, you should work together on all problems. Don’t simply split the problems between both partners. Working on the problems yourself is essential to follow this course. Besides, the midterm and the final will include questions that are highly similar to problem sets. (One or two of the problem sets during the term might be a “solo” pset, where you are not allowed to collaborate.)

  5. There will also be a midterm (accounting for 15% of the total grade), and a final (accounting for 30% of the total grade).

  6. Though not graded, we will also ask you to feel out short surveys on a regular basis throughout the term, so we get feedback on how students are doing with the course. These should not take more than 2-5 minutes of your time.

  7. Attendance in the lectures is required: students who miss more than 3 lectures will get a reduced participation grade. However, we will have a flexible exception policy (see below). Attending sections is not required but is highly encouraged, and can have huge impact on your success in this course. 10% of your grade will be based on participation in lectures, sections, and the online forums, so if you miss one of those components, we expect you make up for it in the others.

Weekly schedule

A typical Thursday-to-Thursday schedule for a CS 121 student will look as follows: (see below for links to all the websites mentioned)

A typical week

In the next week

The previous pset’s grades will be released no later than Wednesday night. During the week you will have your choice of which section to attend and of course office hours are available to you as well. All announcements will be made on Piazza which you should sign up for right away. Every week we will also distribute a short anonymous survey to help us gauge how students are doing, and which materials need more reinforcements.

Resources

We will use the following websites in this course:

THE FINE PRINT

Planned topics

Depending on time, we will discuss the following subjects: Models of computation, representing code as data and universality, uncomputability, modeling efficient computation, exponential vs. polynomial time, NP and NP completeness, randomized algorithms and derandomization, cryptography, algorithms and society: incentives, fairness, privacy, cryptocurrencies, proofs and algorithms, entropy, compression, communication, space bounded computation, finite automata and regular languages, data structures upper and lower bounds, quantum computing.

Prerequisites and mathematical background:

Formally, the prerequisites for this course are “experience in formal mathematics at the level of CS 20”. See this page to understand what this means and how to prepare yourself for the course.

Communication:

All students must sign up for the Piazza board, and are responsible for following the board, including any notifications that are posted there. Contact information and office hours for all staff members are posted on the course website.

If you have any question that is not of a personal nature, we encourage you to post it on Piazza so that other students can also benefit from the answer. Please make sure not to reveal pset answers in your question.

Piazza etiquette

If you have a question of a general technical nature related to the material of this course, please make it a public question on Piazza, so others can benefit from the answer. If you are worried it might be silly, then you can post it anonymously. However, I encourage you to post it under your name: all of us - staff included - sometimes misunderstand things and get confused. Not hesitating to ask questions is crucial to learning. Also, part of your participation grade relies on your activity on Piazza. If you post anonymously, you can’t get credit for it.

If you have a pset related question that might reveal some of your thought process on working on it, then please post it privately first. If the staff thinks it’s appropriate we might ask you to make it public later. If you’re not sure whether a pset-related question should be public or private, then make it private and ask us.

In Piazza, as in any other interaction in this class, we expect all students and staff to be respectful and friendly, as is fit for a community that has a shared goal of learning. Keep Piazza questions technical and don’t use it to post anonymous complaints (e.g., “the course is too hard” or “Boaz’s good looks are distracting me from learning”). We will have weekly anonymous surveys to raise non-technical issues.

Student assignments:

Students should read each week the lecture notes for the next week. You should read the lecture notes fully and deeply. Feel free to discuss any points you find confusing with other students and staff, including on the Piazza board.

Every week will have two online multiple choice quizzes via Canvas on the lecture notes for the upcoming lectures. The quiz on Tuesday’s lecture will be due 9am on Tuesday and the quiz on Thursday’s lecture will be due 9am on Thursday. There will be no late days for the quizzes, but we will have either bonus points or drop the lowest grades.

Every week a problem set will be due on 11:59pm on Wednesday night (unless announced otherwise). Students can work either alone or in pairs on the problem set and each pair will submit one copy of the pset on Gradescope. The pairs can change between psets, but they must be declared on a web form we will provide no later than five days before the exercise is due.

All problem sets must be submitted as typed PDF files through Gradescope. We recommend that the PDF is produced by Markdown, though other ways (such as LaTeX) to produce a similarly formatted PDF are also fine. We will provide markdown sources of the psets to make it easier.

A problem set is considered late by 1 day if it is submitted between one minute to 24 hours late. It is considered late by 2 days if it is submitted between 24 hours and one minute to 48 hours late. A problem set will not be accepted if it is submitted more than 48 hours late. Every student can use a total of 6 late days over the term for problem sets.
You are responsible for keeping track of your late days. Whenever submitting a pset late you should add a line on the top of the first page stating the form “Submitting X days late. After this pset, A has Y late days remaining and B has Z late days remaining” where A and B are the two people in the pair. A late pset counts against the late days of both pair members, and if one of the pair members runs out of late days then neither can submit it late. Understating your late days will be an honor code violation.

Attendance in lectures is generally required, and missing more than three lectures will cause a reduction in your participation grade. If you want to request an exception, send an email to Boaz with CS 121 attendance exception request detailing the reason, and how you plan to make up for missed lectures by increase your participation in other ways (e.g., Piazza / sections or others). Note that you are responsible for keeping up with all material contained in either the lectures or lecture notes.

Falling behind:

If a student significantly falls behind in submitting assignments or quizzes, they may (after a warning) be excluded from the course. If you are starting to have difficulties in this course it is imperative that you come talk to us before you are so far behind that it is impossible to catch up. We want you to succeed in this course and are here to help you do so.

Grading policy:

I believe that grading is not an end in itself but rather a tool to encourage learning and self reflection. We hope that you will do your best to engage with the material, and take the feedback in that spirit, rather than focusing on the numerical grades.

In this vein, all the assignments will have extra “bonus” points. Thus you don’t need to worry if you have not been able to complete all the questions, or lost some points for a silly mistake, as you will have ways to make up for those. The problem sets comprise 30% of the final grade, the quizzes 15%, the midterm 15%, the final 30%, and another 10% will be based on participation in sections, online forum, or other means. While we will not drop any grades, every problem set, as well as the final and midterm, will contain some “bonus” questions that can make up for lost points. The bonus points of one pset can offset lost points in the others, but bonus points in one component of the grade do not generally help in others (e.g., bonus pset points do not help for final grade and vice versa). That said, if people have significant “surplus” of bonus points in a certain component, we might take this into account in determining their final letter grade. Throughout the term we might also offer other opportunities for students to improve their grades, including submitting a revised version of an assignment. Bonus points are truly bonus: I will not be grading on a curve, and you will not need to do perfectly on all questions to get an A in this course.

Mathematical writing is a special case of writing, and so we will grade answers for clarity and not only correctness. Graders are not required to guess your intention or to “decrypt” highly obtuse solutions. If you do not know the answer to a question, we encourage you to simply write “I don’t know”, and you will receive 15% of the credit for this question.

Regrade requests:

All regrade requests should be made via Gradescope no later than midnight on Sunday after the pset is returned (which will be no later than Wednesday). Handling regrade requests takes a lot of time from the teaching staff, time that could be spent on answering student questions, preparing course material, etc.. I encourage you to be judicious in such requests, and only reserve it for the case of clear mistakes by the grader (which can happen - we’re not perfect!). Needless to say, a regrade request triggers re-examining the problem set, which may result in a lower grade as well. Also, we will not accept a regrade request of the form “Johnny made a similar mistake and got fewer points deducted” unless Johnny is willing to have us regrade his problem set as well.

“CS 121.5”

While this course should have enough content and work to satisfy most students, some students might be interested in deeper explorations of theoretical computer science, and to learn more on advanced topics such as proof systems, derandomization, quantum computing, circuit complexity, algorithms for learning and online optimization, and more. For these students we will hold an “advanced section” (“CS 121.5” if you will), whose goal would not be to review material taught in class but rather to explore every week an advanced topic related to this week’s lectures. This section will be given by the TF (Thomas Orton), and sometimes also by guest lecturers. There will also be a short problem set (of 1 or 2 problems) on this advanced material. While completing the advanced problem sets will give a modest bonus in the course grade, the main benefit of the advanced section is to satisfy your intellectual curiosity. The advanced problem set comes in addition to (and hence does not replace any of) the work in CS 121, and students should only attend it and attempt the advanced problem sets if they are very comfortable with all the rest of the CS 121 content and workload. The advanced problem set is entirely optional and bonus, and your score in it can only help (and definitely cannot hurt) your overall CS 121 grade.

Collaboration policy and academic integrity:

Collaboration is highly encouraged in this course. We welcome you to form study groups, read the lecture notes together, share relevant resources you found online, and talk about the concepts in this course. However, in addition there is a kind of learning that is only achieved through the process of thinking deeply on a problem and (figuratively!) “banging your head against the wall”. So, for the problem sets themselves, you should work alone or with at most one partner, and even if you work with a partner, you should make sure you work on the questions together rather than “divvying them up”. If you get stuck on a problem set question, come to office hours, and TFs will help you get “unstuck”. They will not give you hints, but rather review material from lecture and work through more examples until you are in a better place to continue your explorations. However, keep in mind that we do not expect you to solve every single pset question, and as long as you give it a good try, you will learn from the process, which is ultimately the most important thing.

Now for actual policies.. the problem sets can be submitted in by one or two students. The pairings can change between one problem set to another but you need to decide on your pair and post it on the web tool by Saturday night before the problem set is due. Beyond these pairs, you can discuss the pset with one more pair (as long as you disclose their names on your submission). You can discuss general course material with any other student or staff in the class, but you should not talk about problem set questions or solutions.

We expect all students to adhere to the Harvard honor code. Some examples of activities that violate academic integrity include:

  1. Copying another student’s answer in a quiz, problem set, midterm, or final.

  2. Discussing a solution to a problem set question with a student other than your partner for this pset. High level discussions on material taught in class are fine, asking for or giving solution ideas is not.

  3. Not citing a person or resource that helped you in the problem set.

  4. Posting problem set questions or answers online, or sharing them with students that are not currently enrolled in this course.

  5. Searching online for answers for particular problem set questions. It is completely fine to find and use general resources online on the course material. You should however cite any resource you used in your answer.

  6. Searching online for answers for the online quizzes. You should only attempt the quiz after you have read the lecture notes fully, and the lecture notes themselves contain all information you need to answer it.

  7. Understating the amount of late days you used in the problem set declaration.

Note that if we suspect an honor code violation, it could take us time to investigate and verify it, and so you may only find out about the issue very late in the term, or even after it ends. If you are worried that you might have inadvertently violated the honor code, it’s always best to come to us and discuss this.

If you are not sure if something is an honor code violation or not, please ask us!

Student well being:

Your well being is very important to us. If you have any concerns or issues in this course, please reach out to me (Boaz), the teaching fellows, your resident dean, or the Harvard counselling services. If you have a serious medical or other emergency, please have your resident dean contact the course instructor. We will try to accommodate you as much as possible. For extension students, please contact the instructor and/or the extension TFs directly.