CS 121 Syllabus
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.
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:
Before the first lecture (or at least no later than the end of first week): do homework zero and read the chapters on “mathematical background” and “introduction”.
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 textbook. Rather, I will focus on the key conceptual notions, and try to illustrate them with examples. The reading for each week will be posted on the Perusall platform, and also available on introtcs.org
You should make sure to allow for sufficient time to work on the problem sets. Theoretical psets 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 midterms and finals.
Don’t worry about getting psets 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 discussion board. 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.
Assignments and exams
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. We will also have an opportunity to submit reflections on the problem sets for extra points.
The main components for this course are the following
Problem sets: There will be about 10 problem sets in this course that will count for 30% of your total grade.
Two midterms: The midterms will be in the evenings (see schedule). If you cannot attend the midterm for an unavoidable valid reason, contact the teaching team in advance and as soon as you know of it. We will try to find a suitable time for a makeup. Each midterm will count for 15% of your final grade. If you cannot attend neither midterm nor its makeup for a valid medical or other reason, then the other midterm will count an extra 5% and the final will count an extra 10%. (If you miss the midterm for an unapproved reason, your grade will be zero.) If you miss both midterms then all their weight will be moved to the final exam.
Final: The final date is set by the registrar and will be announced. The final exam will count for 30% of the grade.
Participation: 10% of the grade will be “participation”. People can participate in the course in many different ways, including regular attendance of lectures, participating in section, in the Ed forum, making comments on Perusall, and more. By the end of the term, you will write a paragraph on how you participated in the course. The requirements to get the full 10% contribution will not be too onerous. For example attending lectures regularly, plus occasional participation in Ed and Perusall, will be enough.
Bumping up: I reserve the right to “bump up” the grades of students that particularly distinguished themselves in the lectures, sections, or on the discussion board. (Anonymous postings don’t count for the latter! even though it’s possible to get statistics of them, we judge quality, not quantity.) In addition, I might “bump up” the grade of students that have shown significant upward trajectory in their grades throughout the term.
Bonus points: Many 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 course 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 both your learning and 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 homework component in your course grade will be the same in both cases, but in the first case you will be in much better shape for the midterms and final.
Reflections: For some problem sets there will be opportunity to submit “reflections” on your solutions, using the posted solutions to reflect on your submission, seeing what concepts you need to work on more. We will post more information about this later.
Websites
We will use the following resources:
This webpage - for the course schedule, syllabus, and links to the readings. The textbook is available freely online on introtcs.org
Gradescope - for submitting problem sets and seeing exam grades.
Canvas - We won’t use canvas for much but the lecture videos will be available there. We don’t use canvas for communication.
Perusall - for the reading and lecture notes
Ed discussion platform. We will use Ed as our discussion platform. Ed is FERPA compliant and does not sell your data to other companies, see their privacy policy and terms of service ( https://us.edstem.org/privacy , https://us.edstem.org/terms ).
“CS 121.5”
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.
Extension school version
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 accommodate people’s different schedules and time zones.
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.
Participation and simultaneous enrollment
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 discussion board 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., discussion board / sections or others).
CS 121 allows simultaneous enrollment. Students taking this option are required to attend section and office hours in person on a regular basis.
Note that you are responsible for keeping up with all material contained in either the lectures or the text.
Joining the course late
CS 121 will move fast, and if you are planning to take this course, we encourage you to do attend it and do the work (including problem sets and reading) from the first lecture. Students who enroll in CS 121 after the first day of class are responsible for making up all missed work (readings, watching lecture recordings on Canvas, reviewing section material, and submitting problem sets). Catching up may take a significant time investment, depending on your level of preparation and how many classes you’ve missed. We want you to get caught up as quickly as possible so that missed content doesn’t accumulate and make it even harder to catch up. To that end, we require that you submit any missed problem sets by the next problem set deadline that occurs after you enroll in the course. For example, if you join the course after the pset 0 deadline, then you should submit both psets 0 and 1 by the pset 1 deadline. If solutions have already been posted for a particular problem set, you are bound by the honor code to not look at the course solution until after you have submitted your own solution to gradescope. For students who joined the course late, the “make up” problem sets will count for 50% of the weight as they would normally.
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, theory of machine learning, 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 follow the discussion 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 the discussion board so that other students can also benefit from the answer. Please make sure not to reveal pset answers in your question.
Discussion board etiquette
If you have a question of a general technical nature related to the material of this course, please make it a public question, so others can benefit from the answer. If you are worried it might be silly, then you can post it anonymously to the other students. 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.
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 the discussion board, 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 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.
Problem set fine print:
The problem set is due at 11:59pm on the due date posted on the schedule. All problem sets must be submitted as typed PDF files through Gradescope. You should use LaTeX for producing the answer, and we will provide the source 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 and should write it in the appropriate place in the problem set.
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 the discussion board 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 two days 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, 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 the discussion board 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.
Using large language models such as ChatGPT to solve homework problems.
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!
Falling behind:
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!
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), Kitty, the teaching fellows, your resident dean, or Harvard services such as Counseling and Mental Health Services (phone: 617-495-2042, see also TimelyCare ), the confidential peer counseling program Room 13 (phone: 617-366-7375), and the Academic Resource Center (which has CS 121 tutors) (Extension students: ARC referral form).
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 us any letter you have from the DAO so we can provide the appropriate accomodations.
Diversity, inclusion and belonging
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. (Credit: based on the statement of Dr. Monica Linden at Brown University.)