Teaching team: Harvard CS 121: Introduction to Theoretical Computer Science (Fall 2020):

• Instructors:
  • Madhu Sudan. madhu@cs.harvard.edu
  • Adam Hesterberg. ahesterberg@g.harvard.edu

We’re very excited to have an amazing cohort of TFs and Patel Fellows associated with the course!

• Head TF: William Burke. wburke@g.harvard.edu
• Extension school TF: Amy Wang.
• Patel Fellows:
  • Serena Davis. serenadavis@college.harvard.edu.
  • Nari Johnson. njohnson@college.harvard.edu.
• TFs:
  • Joanna Boyland. jboyland@college.harvard.edu.
  • Diego Gutierrez. diegogutierrez@college.harvard.edu.
  • Ife Omidiran. omidiran@college.harvard.edu.
  • Zuzanna Skoczylas. zuzanna_skoczylas@college.harvard.edu.
  • Noah Singer. noahsinger@college.harvard.edu
  • Sahana Srinivasan. sahanasrinivasan@college.harvard.edu
  • Alec Sun. suna@college.harvard.edu
  • Richard Xu. raxu@college.harvard.edu.

Grades will be based on the following

1. Exams: 65% (Midterm 1 – 15%, Midterm 2 – 20%, Final – 30%).
2. 6 Problem Sets. (30%)
3. Class Participation. (5%)

Expectations

1. Attendance in lecture is strongly recommended but not required. Students unable to attend lecture are expected to watch the videos within 24 hours of posting, and follow up on this in sections and office hours.
2. Attending one section per week is also strongly recommended.
3. Office hours are available for students to engage further in the material and to get help on material. It will also be another avenue for getting more “live” interaction in a remote semester.
4. The class discussion board is another way to participate. Please use the forum not only to ask questions, but also answer others’ questions! Course announcements will be made on Piazza, which students are expected to check.
5. Participation points can be earned through any of the above. What we seek in “participation” is evidence of effort to learn or teach the material, and not evidence of mastery of the material. So do not hesitate to ask what may seem like a dumb question to you in any setting where you are able to participate.
6. Problem sets: There are detailed instructions on problem sets on what collaboration is allowed and what is not. In a nutshell, you are encouraged to collaborate when thinking about solutions. But no collaboration is allowed when writing solutions up!

Websites and Materials

• The course website has information about the course.
• Assignments and exams will be submitted on Gradescope.
• Some course materials will be on Canvas.
• Course discussion and some announcements will be on Piazza.
• The course uses Barak’s free textbook. Some students also use Sipser’s book, which isn’t required. We strongly recommend that you read at least one.
• On the course calendar we list the topics of each lecture and sections of the former and, where applicable, the latter book corresponding to each lecture.
• Lectures, Sections, and Office Hours use Zoom, and have components that use shared whiteboards.
• An internet connection good enough to access the above is required. A tablet and stylus is required for maximally effective participation in both sections and office hours.

We’re committed to supporting diversity, inclusion and belonging, and accessibility. The University Disability Office and Extension School Accessibility Office offer a variety of accommodations and services to college and extension school students, respectively, with documented disabilities. We seek to create a learning environment that supports a diversity of thoughts, perspectives and experiences: if you feel uncomfortable sharing your thoughts with the class, please tell us. We include and support students and staff of many identities (including race, gender, class, sexuality, socioeconomic status, religion, and ability), and ask that you similarly support your fellow students. If something was said in class (by us or anyone else) that made you feel uncomfortable, please talk to us 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 us. (Credit: based on the statements of Professor Boaz Barak and Dr. Monica Linden at Brown University.).

Prerequisites and mathematical background

Formally, the prerequisites for this course are “experience in formal mathematics at the level of CS 20”. Read chapter 0 of Barak’s textbook and see this page to understand what this means and how to prepare yourself for the course. Homework 0 (tex, pdf), which is due on the first day of class (but not part of your problem set grade) is intended to help you diagnose your mathematical background; we’ll grade it and talk with you about it if appropriate.

Problem sets

Theoretical problem sets require thinking and take substantial and unpredictable amounts of time, so you should make sure to allow for sufficient time to work on them.

Problem sets are due at 11:59pm ET on the due date posted on the course calendar. All problem sets must be submitted as PDF files through Gradescope. We recommend that the PDF be produced by LaTeX or Markdown. You may extend your deadline for a problem set by one day up to eight times, at most twice per problem set, by submitting late; problem sets late beyond this will not earn credit. You are responsible for keeping track of your own late days.

You are allowed to collaborate with other students currently taking the course, individually or by the discussion board, 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.

Each problem set has some “bonus problems” which don’t count for your pset grade, although we might use them when recommending departmental honors and writing letters of recommendation.

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.

Midterms: The two midterms will be in two of the normal lecture time slots: you’ll download them at the start of lecture, spend lecture time working on them, and submit your solutions at the end. They’re unproctored; we’ll have you sign an honor statement that you didn’t use unallowed resources (extra time, other humans, computers, or the internet). Even if you don’t regularly attend lecture, you’ll need to attend those to take them. If you cannot attend the midterm for a valid reason, contact us and we will schedule a makeup. The midterms account for 15% and 20%, respectively, of your final grade.

Final: You can take the final in any three-hour block from 12-10 1:21pm to 12-12 1:21pm, by downloading it and sending us your answers 3 hours later. In the first four hours of that block we guarantee that we’ll be monitoring Piazza for questions and trying to respond in real time; you’re welcome to take it outside that time, but responses to any questions you have for staff about the exam may be too slow to be useful. The final exam will count for 30% of the grade.

Participation: Each student is expected to participate in at least two of lectures, sections, office hours, and the class discussion board; participation is worth 5% of your grade. (Anonymous or private postings don’t count for class discussion board participation credit. We encourage public posting for the benefit of other students who share your questions but posts containing your solutions to assignments should be private. You’re welcome to post anonymously, not for participation credit, if you’d like.)

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, communication complexity, error correcting codes, algorithms for learning and online optimization, and more. For these students we will hold an “advanced section” (“CS 121.5”), 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.

Collaboration and academic integrity

Collaboration is highly encouraged in this course. We welcome you to form study groups, share relevant resources you found online, and talk about the concepts in this course. Several parts of the course are designed to help you form study groups: the second and fourth fifteen-minute blocks of each lecture, group work in sections, office hours, and the class discussion board.

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:

1. 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.
2. Discussing problem sets with anyone except a current student in the course or a member of the teaching team.
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. Using problem set solutions from previous offerings of this course.
6. 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.
7. 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.
8. 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 we recommend 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! We recommend that students also reach out to the Patel Fellows associated with CS 121 for help.

Patel Fellows

Nari Johnson and Serena Davis will be the Patel Fellows for CS121. The aim of the Patel fellowship is to provide extra help for Harvard College students who are having trouble in the class, typically as evidenced by performance below the class average. If you think that you are someone who would benefit from engaging with a Patel fellow (typically in the form of 1-on-1 or small group tutoring), you should reach out to the Patel fellows using this form. Please feel free to direct any additional questions to Nari and Serena at cs121.fall2020.patel.fellows@gmail.com. Please be aware that our Patel Fellows have limited capacity and are only able to work 12 hours per week, and so we will determine eligibility by helping students who are struggling the most.  We also encourage anyone who would like additional tutoring support to sign up for tutoring at the Academic Resource Center.

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 us (Madhu and Adam), 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 accommodations.