CS 121 Syllabus

This syllabus is still work in progress.

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.

How to succeed in this course

This is not an easy course, but it is definitely manageable. If you put in consistent effort week after week, and follow the steps below, you should be able not just to survive but even to thrive in this course, and not only get a good grade but come out with an understanding and if not love, then at least appreciation for theoretical computer science.

Specifically, to succeed in this course you should:

  1. Before the first lecture (or at least no later than the end of shopping week): do homework zero and read the chapters on “mathematical background” and (optionally but recommended) “introduction”.

  2. You should read fully and deeply the relevant chapter 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. You should make sure to allow for sufficient time to work on the problem sets. Theoretical works require thinking and take time, so don’t wait till the last minute. And if you collaborate, work on all problems together, do not split the questions between you. You will be doing yourself a disservice for understanding the material, and consequently, for your performance in the mideterms and finals.

  4. Don’t worry about getting psets and quiz answers perfectly - problems have varying levels of difficulty and are not designed so students can get all of them right - that’s why we have bonus points.

  5. Use the resources available to you: come to lectures, sections and office hours, ask questions, both in person and on the Piazza. Read the text and you can also look up other texts and online resources, both for help understand the material as well as to follow your curiosity and explore related topics.

Grading policy and grade components

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 grade components for this course are the following:

  • Weekly problem sets: 30%

  • Twice a week online multiple choice quizzes: 10% (as long as you do the reading you should be fine with those: you only need to answer half the questions correctly to get a perfect grade).

  • Two midterms: 10% each. If you miss one of the midterms due to a medical or family emergency, then the other midterm will count for 15% and your final grade will count for extra 5% points. If you miss both midterms then your final grade will count for 60% of the grade.

  • Final: 40% of the grade.

  • Participation: I reserve the right to “bump up” the grades of students that distinguished themselves in participation in the lectures, sections, or on the Piazza board. (Anonymous postings don’t count for the latter! even though it’s possible to get statistics of them, we judge quality, not quantity.)

Bonus points: Most assignments in this course, including the psets, midterms and finals, will have points that sum up to more than 100. At the end of the course, your score in each component will be obtained by taking the average score and capping it at 100. Thus, if your average pset score is 100 or 120, both will be considered “perfect pset grades” and will have the same effect on your final score. In practice these “bonus” points mean the following:

  • You don’t have to worry about making a silly mistake or not getting all questions.

  • It is much better for your grade to solve 80% of the pset questions on your own, than to solve 100% of them based on someone else’s help. The final grade will be the same in both cases, but in the first case you will be in much better shape for the midterm and final.

“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. We might also occasionally have an additional 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.

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.

Problem set fine print:

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.

Pset collaboration policy: You can work and on the problem set with one partner that you declare in advance. In addition, every pair can collaborate with at most one other pair (which you will need to list when submitting). If you are “stuck”, please use Piazza or office hours to talk to us. Also, note that because of the generous bonuses you don’t have to succeed on all problems to get a perfect grade in the problem set component of your grade.

Regrade requests: All regrade requests should be made via Gradescope no later than midnight on Sunday after the pset is returned. 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.

Collaboration 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!

Lecture attendance (college students only)

Attendance in lectures: I generally encourage, expect and measure attendance, but understand that different people learn in different ways. If you are one of the people that does not learn as well from lectures and prefer not attend them regularly, you can “opt out” by sending me a private Piazza message to the instructors with the subject CS 121 attendance exception request detailing the reason, and how you plan to make up for missed lectures by increasing 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 the text. You will of course have to attend the midterms.

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.

Student well being:

Your physical and mental 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 Harvard services such as Counseling and Mental Health Services (phone: 617-495-2042, see also Let’s Talk), and the confidential peer counselling program Room 13 (phone: 617-495-4969).

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.

Extension school version

The extension school version of the course is largely run identically to the college version, with the following differences:

That said, I realize that extension students have other obligations and constraints that college students do not. Towards that end, we will have the following policies specifically for extension students:

  1. Extension students can use a total of 9 late days, as opposed to 6 late days for college students.

  2. We will drop the lowest graded problem set from the extension students calculation of the problem set score.

  3. The midterms and final will be taken online, and you will have a window of at least 12 hours to do them to accomodate for people’s different schedules and time zones.

Every problem set and exam will consist of extra “bonus” material that is sometimes more advanced. For the graduate credit version of the course, students will need to do some of this more advanced material, and hence the requirement for a “perfect grade” will be 110 instead of 100.

Accessibility: The Extension School is committed to providing an accessible academic community. The Accessibility Office offers a variety of accommodations and services to students with documented disabilities. Please visit https://www.extension.harvard.edu/resources-policies/resources/disability-servicesaccessibility for more information.