This syllabus is still work in progress.
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.
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.
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:
Read fully and deeply the relevant chapters of the book every week. This is absolutely essential, as lecture will not contain all the contents of the text book. Rather, I will focus on the key conceptual notions, and try to illustrate them with examples.
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, make sure that you own your solution!. If you just grab hints from others without true understanding, you will be doing yourself a disservice in your grasp of the material, and consequently, for your performance in the mideterms and finals.
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.
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.
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%
Weekly online low-stakes multiple choice quiz: 10%. The quiz will cover the contents of both lecture and the reading (including material not covered in lectures.)
Two midterms: 10% each. There will be no medical or other makeups for the midterms. If you miss one of them to a medical or other 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. In fall 2019, the midterms will likely be held in evenings as to allow for a longer time slot and less time pressure.
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 that you don’t have to worry about making a silly mistake or not getting all question and that 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.
New in Fall 2019: Optional course project: Starting Fall 2019, CS 121 will have a course project as well. This course project will be optional and doing it can only help your grade. More details will be supplied later.
While this course has 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, commmuniation complexity, error correcting codes, 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.
The extension school version of the course is largely run identically to the college version. 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:
Extension students can use a total of 9 late days, as opposed to 6 late days for college students.
We will drop the lowest graded problem set from the extension students calculation of the problem set score.
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.
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.
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.
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.
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 run occasional anonymous surveys to raise non-technical issues.
Every week a problem set will be due on 11:59pm on Wednesday night (unless announced otherwise). 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 are allowed to work with other students currently taking the course in discussing and brainstorming the solutions, but when you are done talking, you must write up your solutions independently and may not check them against each other. There may be no passing of homework papers between collaborators; nor is it permissible for one person simply to tell another the answer. You should list the names of all the students you collaborated with in the first page. 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 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, there is a certain component 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 follow the collaboration policy closely and make sure you “own your solutions”. If you get stuck on a problem set question, ask questions on Piazza or 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.
We expect all students to adhere to the Harvard honor code. Some examples of activities that violate academic integrity include:
Copying another student’s answer or sharing your answers for a quiz, problem set, midterm, or final. Brainstorming on problem set questions with other students is OK, sharing written solutions is not.
Discussing problem sets with anyone except a current student in the course or a member of the teaching team.
Not citing a person or resource that helped you in the problem set.
Posting problem set questions or answers online, or sharing them with students that are not currently enrolled in this course.
Using problem set solutions from previous offerings of this course.
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.
Searching online for answers for the online quizzes. You should only attempt the quiz after you have read the text fully, and the text itself contain all information you need to answer it.
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!
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.
If you are starting to have difficulties in this course it is imperative that you come talk to us (the instructor or the TF’s) 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!
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 (on business hours), 617-495-5711 (all other times), see also Let’s Talk), the confidential peer counselling program Room 13 (phone: 617-495-4969), and the Beuro of Study Council (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.
If you have a health condition that affects your learning or classroom experience, please let me know as soon as possible. Please also share with me any letter you have from the AEO so we can provide the appropriate accomodations.
My goal is to create a learning environment that supports a diversity of thoughts, perspectives and experiences, and honors your identities (including race, gender, class, sexuality, socioeconomic status, religion, and ability). I (like many people) am still in the process of learning about diverse perspectives and identities. If something was said in class (by me or anyone else) that made you feel uncomfortable, please talk to me about it. If you feel like your performance in the class is being impacted by your experiences outside of class, please don’t hesitate to come and talk with me. As a participant in offline and online course discussions, you should also strive to honor the diverse perspectives of your classmates and teaching staff. (Statement extracted from one by Dr. Monica Linden at Brown University.)