15-251 Great Ideas in Theoretical Computer Science

Course Information

Prerequisites

The formal prerequisites for the course are (15-122 or 15-150) and (21-127 or 21-128 or 15-151). In particular, we expect the students to have taken an introductory computer science course that goes beyond basic computer programming and covers algorithmic thinking. On the mathematics side, we expect the students to have experience reasoning abstractly and know how to write formal proofs.

Learning Objectives

Broadly speaking, the course has several goals. First, it provides a rigorous/formal introduction to the foundations of computer science, which is the science that studies computation in all its generality. An important component of this is improving your analytic and abstract thinking skills since nature's language is mathematics. Second, the course intends to prepare you to be innovators in computer science by presenting some of the great ideas that people in the past have contributed to science and humanity. We hope that you will learn from their examples. Third, the course gives you opportunities to improve your social skills by emphasizing cooperation, clarity of thought, and clarity in the expression of thought.

More specifically, some of the main learning objectives are the following.

• Define mathematically the notions of computation, computational problem, and algorithm.
• Express, analyze and compare the computability and computational complexity of problems.
• Use mathematical tools from set theory, combinatorics, graph theory, probability theory, and number theory in the study of computability, computational complexity, and some of the real-world applications of computational concepts.
• State and explain the important and well-known open problems in the theory of computation.
• Write clearly presented proofs that meet rigorous standards of correctness and conventional guidelines on style.
• Identify and critique proofs that are logically flawed and/or do not meet the expected standards of clarity.
• Cooperate with other people in order to solve challenging and rigorous problems related to the study of computer science.

Note that even though all of the topics we discuss in the course have real-world applications, often we will not be explicitly discussing the applications. This is because initially it is better to separate concerns regarding real-world applications from the exploration of fundamental truths and knowledge that shape how we view and understand the world. The quest for truth and understanding, wherever it takes us, eventually do produce applications, some that we hoped to achieve, and some that were beyond our wildest dreams. The focus of the course is on that quest for truth and understanding, which is arguably more important than specific applications.

External Resources

There is no required textbook for the course. The material is fairly diverse, and no standard text contains it. Lecture notes will be provided. Furthermore, the lectures will be recorded and the links to the video recordings as well as the slide handouts will be provided on the course website.

If you want to look at books which contain parts of the course material, we recommend the following:

• Introduction to the Theory of Computation by Michael Sipser,
• The Nature of Computation by Cristopher Moore and Stephan Mertens,
• Introduction to Theoretical Computer Science by Boaz Barak,
• Quantum Computing Since Democritus by Scott Aaronson.

Mentoring System

You will all be assigned a mentor TA at the beginning of the semester. Your mentor will keep track of your progress, grade your homeworks, and help you do well in the course. Don't hesitate to contact your mentor TA about anything related to the course. In the middle of the semester, you will be assigned a new mentor, so during the semester you will have two mentors in total.

Grading

Your grade will depend on the following factors.

Homeworks. There are 11-12 homework assignments.

Midterm Exams. There are 2 Midterm exams (Feb 28, Apr 18, from 6:30pm to 9:30pm). Please mark your calendars.

Final Exam. There is a Final exam at the end of the semester during the finals week.

Class Participation. This is mostly based on attendance in lectures and recitations.

Your numerical grade will be calculated according to the following table.

Course Component	Weight
Homework	25%
Midterm 1	20%
Midterm 2	20%
Final	30%
Participation	5%

At mid-semester, letter grade cut-offs will be announced.

If your letter grade at the end of the semester is below a C, then we will also calculate your grade using the table below and assign the higher grade. The maximum letter grade you can receive with the alternate grading scheme is a C.

Course Component	Weight
Homework	25%
Higher Midterm	30%
Final	40%
Participation	5%

Homework System

Homework is an extremely important component of the course and is the main tool we use to teach you valuable skills, reinforce key concepts, and help you learn the material.

There are some general rules that apply to all the questions in the homework:

• You cannot share written material with anyone.
• You cannot discuss solutions to the problems on Piazza or any other discussion forum. (You are welcome to ask questions on Piazza that do not reveal any solution ideas.)
• You cannot solicit answers to the homework questions, i.e., you cannot ask anyone to provide you the solution to a problem, before the homework writing session.
• Searching the internet for general concepts is allowed. Googling for specific keywords that happen to appear in one of the homework questions is prohibited.
• You must always cite your sources including the people you have worked with.
• For the collaborative portions of the homework, you must think about a problem for 15 minutes before you start discussing it with someone else.
• If you work on a publicly visible whiteboard/blackboard, you must erase all contents when you are done.

If you have any doubts about whether something is within the rules or not, do not hesitate to contact the course staff.

Types of questions: There will be 4 types of questions in the homework and each question will be clearly labeled with its type.

SOLO - You must work on these questions by yourself. In addition to the rules mentioned above, you are not allowed to discuss these questions with anyone except for the course staff.

GROUP - These questions must be solved in groups of 3 or 4. Working on these questions just by yourself is not allowed! You must clearly indicate your group members. You can change your group from week to week, but you can have at most one group per week. Other than your group members, you may discuss these questions with the course staff.

OPEN COLLABORATION - You can discuss these questions with anyone you like from class (i.e., other students currently taking the course and the course staff). Other than the general rules stated above, there are no additional rules for this type of question.

PROGRAMMING - Not all homework assignments will contain a programming question, but some might. The SOLO rules apply to these types of questions. You must submit your programs to Autolab by 6:30pm the day the homework is due.

A homework assignment for a particular week will contain SOLO and/or PROGRAMMING type questions covering the current week's material, plus, GROUP and/or OPEN type questions covering the previous week's material. This has a couple of benefits. First, you'll solve problems on a topic for two weeks rather than one, which helps with retention. Second, after solving the easier solo questions, you will be much better prepared to solve the harder collaborative questions.

Homework writing sessions: You will not hand in written up solutions to every question of the homework. Every Wednesday from 6:30pm to 7:50pm at DH 2210, we will have a homework writing session. We will randomly pick a subset of the homework questions (usually 3 questions are picked), and you will be required to write the solutions to those problems individually during this proctored setting. We expect that you will have already practiced writing down the solution to every question in the homework prior to Wednesday night. Therefore these homework writing sessions should be relatively straightforward and stress-free.

There are also homework resubmission sessions every Friday during the SIO assigned recitation times. More details can be found below.

Homework grading: After the homework writing session, you will get back your graded homework the following recitation. Each question will be graded based on the following scale:

• Satisfactory: No mistakes or minor mistakes.
• Close: The main idea of a correct proof is present, however a non-trivial piece is missing or incorrect (if you have more than one such mistake, your answer goes down to the next category). Or the proof is generally correct, but is presented poorly.
• Needs rewrite: Rest.

It is very important that you learn from your mistakes and correct them. For this reason, if your submission was not satisfactory, you will have the option to resubmit your answers to up to two questions in the homework. If your submission was close, your TA will tell you what you need to fix to make it satisfactory. You can then send those fixes by email to the TA. The deadline for this is Friday 6:30pm (9 days after the corresponding homework writing session). If your submission needs to be rewritten, then you will need to attend a homework resubmission session, 9 days after the corresponding homework writing session, at your SIO assigned recitation time and room. Before you make a resubmission, you will be allowed to go to the homework solution session (see below for details) and/or discuss the solutions with us during office hours.

The point distribution for a question is as follows.

• 10 points: Satisfactory first submission.
• 9 points: Close first submission and fixes are submitted by email to the TA.
• 8 points: Close first submission and errors are not fixed.
• 7 points: Satisfactory resubmission in the resubmission session.
• 6 points: Close in resubmission.
• 0 points: Rest.

Grading proofs is a complicated process. We try our best to be as fair and as consistent as possible. However, mistakes will happen from time to time. Therefore we have a system in place that makes grading a two-step process. The first step is that we read your solutions and determine whether it is satisfactory, close, or needs to be rewritten. If you have any disagreement, your mentor would be happy to meet with you to go over your submission. If there was a misunderstanding, we will correct it. If you cannot resolve the situation with your mentor, email one of the head TAs to get a second opinion. If you are still not satisfied, email one of the instructors.

The deadline for homework regrade request is Friday 6:30pm (9 days after the corresponding homework writing session). Email your request to your mentor.

Dropped Questions: You are allowed to drop 2 homework questions during the semester without penalty. To drop a question, write "Drop" in place of an answer during the homework writing session.

Proof-writing guidelines: The quality of your write-up and presentation matters a lot, so you should make sure your solutions are very clearly explained. If you are not sure of something, or you think there is a gap in your argument, clearly indicate these in your write-up (you will get more credit doing so rather than writing a wrong argument!). Do not try to sell a wrong or incomplete proof!

To help you write correct and clear proofs, we have prepared a document with a list of guideline points. The guideline points will appear as a checklist in each homework. For each proof you write, you will have to tick the checklist items to acknowledge that you are following the guidelines.

Click here to access the document.

Homework solution sessions: Unfortunately, we will not be publishing written solutions to the homework problems. There are a couple of reasons for this.

First, any homework solution we post kills the question for future semesters of the course (and any other course in the world that might be using a similar question). This is because the solutions eventually end up in websites like Course Hero (or someplace else). Most questions we ask are pedagogically very valuable, and coming up with such questions is very hard. So we don't want to kill those questions by publishing solutions.

Second, we would like you to be able to write the correct solutions yourself. We believe that this much more effectively contributes to your learning. And this is why we have our resubmission policies.

We will hold homework solution sessions twice a week and go over (on the blackboard) the main ideas behind the solutions to the problems that appeared in the writing session. We are also always happy to go through the main ideas to any problem with you during office hours. Note that we will not be giving full details of the solutions. In a homework resubmission, if you just repeat what you hear from us, your answer will not be satisfactory.

The times and locations of the homework solution sessions will be announced at the beginning of the semester.

Recitation System

The recitation sections that you have signed up for on SIO will only be used for the first week of the course. Starting week 2, we will transition to a different system.

One of the main advantages of recitations over lectures is that the sections are much smaller in size. However, 30 students in one section is still too many. In order to improve the student-TA ratio and give you more flexibility, we will be asking you the times you are available on Fridays and Saturdays. Based on that information, we will assign you to a recitation slot. And a typical recitation section will have about 12 students.

In addition to the above change, we will offer 3 different spiciness levels for recitations. You will select yourself which level is appropriate for you. During the semester if you feel like you would like to switch to another level, let us know, and we'll arrange the switch.

We will take attendance in recitation and you are required to do the Quiz questions in the course notes (that will appear at the end of each chapter) and bring your answers to recitation.

Piazza

We will use Piazza for several purposes, as listed below. Every student is required to signup for the course's Piazza page!

• Making announcements. Important announcements related to the course will be made on Piazza. You must check Piazza and/or your email on a daily basis to receive the announcements in a timely manner.
• Asking and answering questions. If you have a question about the course that can be easily answered electronically, use Piazza to ask your question rather than emailing the course staff. If you believe that others would benefit from seeing the answer to your question, post your question publicly. Please keep the discussion polite and be careful not to give out information about the homework solutions.
• Finding group members. Piazza has a "Search for teammates" functionality which you can use to find group members to collaborate for the homework.
• Conducting in-class polls. We will be asking poll questions during lectures related to the topics being discussed. We expect everyone to answer all the poll questions. We will not keep track of whether your answers are correct, however, we will use the polls to keep track of attendance. If a lecture contains multiple polls, a random one will be chosen to take attendance. If you experience a technical difficulty that prevents you from participating in a poll, then see the instructor right after lecture so your presence can be noted.

Asking Questions

Even though we are always ready to help and provide support anyway we can, there is a fine balance that we have to respect. Ultimately, we would like you to develop the necessary skills to be self-sufficient problem solvers. You will have many questions throughout the semester. Reflecting on your questions to try to figure out the answers on your own is extremely valuable, and we want to make sure that you are not robbed of this experience. Here are some general guidelines for asking questions.

• The general rule of thumb is the following. Before you ask a question to us, ask yourself whether you can figure out the answer yourself. If the answer is "yes" or "maybe", then you should give a solid effort in trying to find the answer.
• Whenever you ask a question, first tell us what your own thoughts about the question are and what you have tried. If you don't, then we will usually respond to your question with another question asking you what your thoughts are. When you explain your thoughts to us, this allows us to see and fix any misunderstanding and help you more effectively.
• If a homework problem is ambiguous to you, try to figure out all the possible interpretations and evaluate them one by one. Often, you'll find that there is really one interpretation that makes sense.
• For questions related to solving a homework problem, ask a question only when you are stuck. If you are not stuck, and you have room to explore yourself (or with your group), then please do explore.
• Do not turn a conversation with a course staff member into the Twenty Questions game. Though this game is fun to play, it does not maximize your learning outcomes.
• Certain discussions are best suited for your group. For example, if you want to bounce off ideas and get some feedback on your thought process for a GROUP or OPEN problem on the homework, you should have that conversation with your group members.
• Please do not ask us to read your solution write-up and give you feedback on how many points you would get. Solutions can have subtle bugs, and we cannot always spot such bugs after a quick glance. Properly reading and evaluating a solution can take a lot of time. That being said, even though we cannot read your solution in detail before the homework writing session, we are happy to listen to your overall proof strategy and help you try to figure out if there are any logical flaws or gaps.
• Piazza is a good resource for short-answer questions, but can be extremely inefficient for long-answer questions or questions that may require a back and forth conversation. When you want to ask a question on Piazza, consider whether the question is suitable for Piazza, and if it is not, ask your question during office hours.

Use of Electronic Devices

The use of electronic devices like phones, tablets, and laptops during lectures and recitations is prohibited. These devices cause distractions both to you and the people around you. If you would like to use an electronic device to take notes and using paper and pencil is not a good option for you, please contact one of the instructors.

There is an exception to the above rule. When we open up a Piazza poll during a lecture, you are allowed to use your phone to cast your vote. Once the poll is completed, you should put away your phone. If you do not have a smart phone, please contact one of the instructors.

How to Succeed in 251

Download the pdf.

Academic Integrity

We understand that most of you would never consider cheating in any form. There is, however, a small minority of students for whom this is not the case. In the past, when we have caught students cheating they have often insisted that they did not understand the rules and penalties. As a part of the first homework, you will be required to acknowledge that you have read and understood the cheating policies. Please read Carnegie Mellon University Policy on Academic Integrity. The following are some clear examples of cheating:

• Copying from another student during an exam or homework writing session.
• Discussing a SOLO problem before the homework writing session with someone who is not a part of the course staff.
• Googling for specific keywords that happen to appear in one of the homework questions.
• Showing a draft of a written solution to another student.
• Getting help from someone who you do not acknowledge on your solution.
• Receiving exam related information from a student who has already taken the exam.
• Attempting to hack any part of the 15-251 infrastructure.
• Looking at someone else’s work on AFS, even if the file permissions allow it.
• Lying to the course staff.

Consequences: The penalty for cheating can range from a 10% deduction on your overall course average (i.e. a letter grade drop) to directly failing the course. Furthermore, in most cases, a letter to the Dean of Student Affairs is sent and further consequences are determined by them.

Extended-Time and Make-Up Policy

We are happy to provide appropriate accommodations to students who have approval from the Disability Resources Center. Please contact one of the instructors if you are in this situation.

No make-up quizzes, exams, or homework writing sessions will be administered, except in the case of documented medical or family emergencies, or other university approved absences. The common cold or your computer crashing, unfortunately, do not qualify as an excused absence.

Well-Being and Happiness

We very much care about your well-being and happiness! Be aware that everyone on the course staff is always available to provide counsel or chat, and you should attend office hours as often as you want for academic and non-academic conversation.

However, also know that the university provides services that you may want to take advantage of at some point during the semester. If you are ever unsure about them, run into a problem, or want more information, feel free to reach out to the instructors.

For a comprehensive list of CMU’s resources, please click here.

CMU Police Department

Do not hesitate to call CMU police when in an emergency or if you are interested in taking advantage of their services.

• Website: http://www.cmu.edu/police/welcome.html
• Emergency phone number: 412-268-2323
• Non-Emergency phone number: 412-268-6232

Counseling and Psychological Services (CAPS)

CAPS offer therapy, crisis support, etc. and you should reach out to CAPS for counseling if you are struggling, no matter how small you may think your problems are. If CAPS can’t help you appropriately, they also do referrals and basic consultations to help you find what you need.

• Website: http://www.cmu.edu/counseling/
• Hours: Monday through Friday 8:30am-5:00pm
• Phone number: 412-268-2922
• Location: 2nd floor, Morewood Gardens, E-Tower

University Health Services (UHS)

Health services can help you in the same way a doctor does but they also offer comprehensive care management and health promotion services.

• Website: http://www.cmu.edu/health-services/
• Hours: M, Tu, W: 8:30am-7:00pm, Th: 10:00am-7:00pm, F: 8:30am-5:00pm, Sat: 11:00am-3:00pm
• Note: When UHS is closed, call 1(844)881-7176.
• To set up an appointment on HealthConnect, click here.
• Comprehensive Care Manager: Diane Dawson, 412-268-9171

15-251 Wellness Help

If you find yourself struggling in any way or simply would like to discuss how you are feeling about 251 or just chat, reach out to one of the following people or your mentor TA to set up a casual meeting.

• Anil Ada (Instructor): [email protected]
• Klaus Sutner (Instructor): [email protected]
• Apoorva Bhagwat (Head TA): [email protected]
• Calvin Beideman (Head TA): [email protected]