Welcome to 15-251, Great Ideas in Theoretical Computer Science! This course is about the rigorous study of computation, which is a fundamental component of our universe, the societies we live in, the new technologies we discover, as well as the minds we use to understand these things. Therefore, having the right language and tools to study computation is important. In this course, we explore some of the central results and questions regarding the nature of computation.
If you are taking the course, we are excited to have you on board! We hope that this will be a great educational experience for you and the whole course staff will do their best to make that happen.
In this chapter you will find various logistical details about the course. If you do not find what you are looking for, don’t hesitate to contact us with your question.
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. Furthermore, it is highly recommended that students have knowledge of basic discrete probability theory.
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 logical, analytic and abstract thinking skills as these are crucial for forming deep conceptual understandings, creating new knowledge, and pushing the boundaries of science and technology.
Second, the course intends to help 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 and find inspiration from them.
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 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 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 others in order to solve challenging and rigorous problems related to the study of computer science.
Even though all 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.
Here is a rough division of topics:
Green (Weeks 1-5): Formalizing computation and computability theory
Yellow (Weeks 6-10): Computational complexity: theory and applications
Blue (Weeks 11-14): Highlights of theoretical computer science
Below you’ll find the tentative schedule.
The course uses Piazza to distribute some of the course content, make announcements, and host online course discussions. It is important that you check Piazza and/or your email notifications on a daily basis.
Most of the course material is going to be published at https://s23.cs251.com.
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.
You will all be assigned a mentor TA who will most likely be one of your recitation TAs. Your mentor will keep track of your progress and do their best to help you do well in the course. Don’t hesitate to contact your mentor TA about anything related to the course. For instance, you can set up meetings with them to review course material, go over homeworks or exams, or chat about studying strategies.
Throughout the semester, feel free to reach out to anyone on the course staff about anything! Seriously! We are here to help you!
First, we would like to explicitly point out that as the course staff, our number one priority is for you to enjoy the course and learn a lot! It is not about ranking students and assigning grades. However, we are required to assign a letter grade to all students. At the end of the course, you will get one of the letter grades A/B/C/D/R.
Your grade will depend on the following factors.
Homework: There are about 10 or 11 homework assignments.
Exams: There will be two midterm exams, tentatively set for Feb 22nd and Apr 5th (7:00pm - 10:00pm). And there will be a final exam at the end of the semester during the finals week. All exams are 3 hours long.
Attendance: This is based on attendance in lectures and recitations. Whether attendance is part of your final grade is up to you. We describe the details further down.
Your numerical grade will be calculated according to the following table.
\[\begin{aligned} & \textbf{Course Component} & & \textbf{Weight} \\ & \text{Homework} & & 25\% \\ & \text{Lower Midterm Exam} & & 14\% \\ & \text{Higher Midterm Exam} & & 28\% \\ & \text{Final Exam} & & 28\% \\ & \text{Recitation Attendance} & & 2\% \\ & \text{Lecture Attendance} & & 3\% \\\end{aligned}\]
If you wish, you can choose to have recitation and lecture attendance not count towards your final grade. In this case your grade will be calculated as follows.
\[\begin{aligned} & \textbf{Course Component} & & \textbf{Weight} \\ & \text{Homework} & & 25\% \\ & \text{Lower Midterm Exam} & & 14\% \\ & \text{Higher Midterm Exam} & & 28\% \\ & \text{Final Exam} & & 33\% \\\end{aligned}\]
However, you need to make the decision about how your grade will be calculated at the beginning of the semester (before the second week ends), and your choice will be binding.
In order to track attendance, 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 check whether your answers are correct. 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 please let the instructor know right after lecture so that your presence can be noted.
Your letter grades will be calculated as follows: \[\begin{aligned} & \text{A}: 87.5-100\% \\ & \text{B}: 75-87.5\% \\ & \text{C}: 67.5-75\% \\ & \text{D}: 55-67.5\% \\ & \text{R}: 00-55\% \\\end{aligned}\]
Homework is the most 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.
Every course has different rules for collaboration. Below you’ll find some general rules that apply to all the problems in the homework. Note that the rules are in place in order to respect the learning objectives of the course and maximize your learning outcomes.
You cannot share written material with anyone.
You cannot discuss the problems with anyone who is not taking the course and who is not a course staff member.
You cannot solicit answers to the homework problems, i.e., you cannot ask anyone to provide you the solution to a problem, before the homework is due.
Searching the internet for general concepts is allowed. Googling for specific keywords that happen to appear in one of the homework problems is not allowed.
You must cite your sources including the people you have worked with.
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.
There are various types of problems/questions in the homework, as outlined below.
CYU - Each chapter in the textbook has a “Check Your Understanding” section consisting of short-answer questions. These questions are meant to help you identify gaps in your knowledge/understanding. You will be responsible for the chapters covered for the week. You can discuss these questions with anyone you like from class (i.e., other students currently taking the course and the course staff). You can ask the course staff for the answer to a question as long as you first demonstrate that you have thought about the question and provide some thoughts about the answer.
SOLO - You must work on these problems by yourself. In addition to the rules listed in the previous section above, you are not allowed to discuss these problems with anyone except for the course staff.
GROUP - These problems must be solved in groups of 3 or 4. Working on these problems 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 problems with the course staff.
OPEN COLLABORATION (OPEN) - You can discuss these problems 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 problem. If you wish, you may work on these problems by yourself.
PROGRAMMING - Not all homework assignments will contain a programming problem, but some might. The SOLO rules apply to these types of problems. These kinds of problems will be submitted to Gradescope and will be autograded.
A homework assignment for a particular week will usually contain CYU, SOLO and/or PROGRAMMING type problems covering the current week’s material, plus, GROUP and/or OPEN type problems 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 problems, you will be much better prepared to work on the harder collaborative problems.
The homework comes out on Thursday and will be due the following Wednesday at 7:00pm. However, you will not hand in written up solutions to every question of the homework. Every Wednesday from 7:00pm to 8:20pm at GHC 4401, we will have a homework writing session. We will randomly pick 4 CYU questions and a subset of the SOLO/GROUP/OPEN problems (usually 3 problems are picked). You will be required to write the solutions to those problems individually during this proctored setting.
The writing sessions are not common in other courses, so it is very natural to wonder what the point is. We view writing sessions as a key part of the whole learning process and an important part of giving more accurate feedback. In particular, we want to make sure that you understand your solutions thoroughly enough such that you could explain it to someone else on the fly. And if you struggle with that, or if you feel like you need to memorize your solutions, we want you to take that as feedback that you should be aiming for a deeper level of understanding. It is interesting to think about what “understanding” really means (and we encourage you to think about it yourself). There are at least 2 important components to it: compressibility and well-connectedness of knowledge. By compressibility, we mean reducing a rich collection of knowledge to a few basic and well-motivated principles so that once you know them, a whole bunch can be derived relatively easily and naturally without the need of remembering anything extra. By well-connectedness, we mean the knowledge is not disjointed but relates to your existing body of knowledge (or other new pieces of knowledge) in interesting ways. Without compressibility and well-connectedness, you will probably feel that you need to memorize things. The main role of the writing session is feedback for you, so you can judge more accurately your understanding, and have a chance to modify your studying strategy if needed.
After the homework writing session, you will get back your graded homework the following recitation. Whenever there is a point deduction on your homework, an explanation should be given, but if you do not understand why you lost points, please don’t hesitate to contact us so that we can clarify things for you.
Each CYU question will be worth 2 points. Each SOLO/GROUP/OPEN problem will be graded as follows: \[\begin{aligned} & \checkmark + & & 10\text{pts} \\ & \checkmark & & 8\text{pts} \\ & \checkmark - & & 6\text{pts} \\ & \text{redo} & & 0\text{pts} \end{aligned}\]
Note that the above grading scheme does not mean that you have to write a perfect solution to get a \(\checkmark +\). We generally allow for small mistakes without any point deductions. And even though we do not deduct points for small mistakes, we will give you written feedback about them.
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 assign an initial grade based on the rubric. The second step is that you carefully review your solution and the feedback, and if you believe there has been a grading error, you submit a regrade request. If there was a mistake, we’ll correct it. If you cannot resolve the situation with the TA who graded the problem, email one of the head TAs to get a second opinion. If you are still not satisfied, email the instructor.
Note that your grade can never go down as a result of a regrade request; it can only go up.
The deadline for homework regrade request is Sunday 5pm (4 days after the corresponding homework writing session).
Your lowest 2 homework problem scores (SOLO/GROUP/OPEN/PROGRAMMING) will be dropped when calculating your homework average (please note that this is not saying 2 entire homeworks will be dropped, but lowest 2 problem scores will be dropped).
OPEN problems are typically more challenging compared to the other problems in the homework, and they can take considerable amount of time and effort to solve. Each homework will contain at most one of these problems. If you feel like all the other problems are already taking a lot of time, feel free to skip the OPEN problem. If the OPEN problem is in the homework writing session, there will also be an alternative problem selected from the same homework. You can choose to write the solution to the alternative problem, and in this case, the maximum number of points you can receive will be capped at 8 points (instead of 10 points).
It is important that you learn from your mistakes and correct them. For each homework you are allowed to resubmit up to 2 of the SOLO/GROUP/OPEN problem solutions that received a “redo” (out of the 3 total problems that is graded). You may (and should) either go to the homework solution sessions (see below for details), ask about the solution during office hours, or set up a time to meet with your mentor TA to go over the solution with them. If you turn in a completely correct and well-written solution, you will receive back 4 points for the problem you resubmit. Note that CYU questions cannot be resubmitted.
The deadline for homework solution resubmission is Wednesday 7:00pm (a week after the corresponding homework writing session).
Unfortunately, we will not be publishing written solutions to the homework problems. The main reason is that any homework solution we post kills the problem for future semesters of the course and any other course that might be using a similar problem. Most problems we ask are pedagogically very valuable, and coming up with such problems is hard.
That being said, we don’t keep the solutions a secret either. We hold homework solution sessions twice a week and go over the solutions (on the blackboard) then. We are also always happy to go through the solutions to any problem with you during office hours or one-on-one meetings (don’t hesitate to reach out to your mentor TA).
Note that during the solutions sessions, we will not write the full proof on the blackboard. We expect you to fill in the details yourself.
One of the main advantages of recitations over lectures is that the sections are much smaller. This allows us to give you a more personalized experience.
We will offer 3 kinds of recitations. You will select for yourself which kind your prefer. During the semester if you feel like you would like to switch to another kind, let us know, and we’ll arrange the switch.
Recitation Cantor. In these recitations, we will go over the definitions to make sure everyone understands them fully. Then we will solve the problems together (as many as the time allows).
Recitation Turing. After a quick review of definitions, we’ll solve the problems together. These sections will have a faster pace.
Recitation Gödel. We’ll assume you are comfortable with everything covered in lecture and notes, so we’ll directly dive into the problems. These sections will have the fastest pace.
During the first week of classes, we will be asking your availability on Fridays and your preference of recitation kind. Based on that information, you will be assigned a recitation section.
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 give a solid effort in trying to find the answer. This is an extremely valuable learning experience. Our role is to help you when you are genuinely stuck.
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.
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 an OPEN problem on the homework, we encourage you to have that conversation with your group members first.
Unfortunately we will not be able to read your solution write-up and give you feedback on how many points you would get before the homework is due. 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 is due, we are happy to help you work through any specific concerns about your solution.
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 that platform, and if it is not, consider asking your question during office hours for a more efficient conversation.
Piazza allows you to post your questions anonymously. However, we strongly discourage you from doing so. If you are not comfortable asking questions in front of others, take this as an opportunity to learn this extremely valuable skill! Really! This is a skill that will serve you well for the rest of your life. And it is much more important than any technical content you’ll learn in this or any other course. We hope you take these words to heart.
The use of electronic devices like phones, tablets, and laptops during lectures and recitations is generally prohibited. These devices cause distractions both to you and the people around you. If you would like to use a tablet to take notes, that is fine. We highly encourage taking notes during lecture. Also, when we open up a 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.
This is the most important information for this section: If you ever find yourself in a situation where you are thinking about a potential academic integrity violation, please reach out to us! Tell us why you are in this position. Tell us if you need more time or if you need more help. Together we’ll find a good path for you no matter what the situation is.
As the course staff, we will do our best to make the course fair for everyone. 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 is due with someone who is not a part of the course staff.
Googling for specific keywords that happen to appear in one of the homework problems.
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.
Sharing the course material online (even if the semester is over).
The penalty for cheating usually ranges from a letter grade drop to receiving an R. Furthermore, in most cases, a letter to the Dean of Student Affairs is sent, and further consequences are determined by them. Of course we hope that no one will suffer these consequences; please read the first paragraph of this section again.
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.
If you need an extension due to some medical or family emergency, or some other university approved absence, you and your academic advisor should email the instructors. If a deadline is missed apart from one of the above reasons, we won’t be able to accept the work.
Please make a note of the exam dates and do not schedule events (like interviews) during those times.
If you are not happy about something regarding the course, please reach out to us! The sooner you do this, the better. There is no point in going through an entire semester being unhappy. Really. We want you to enjoy your learning experience, and we’ll do whatever we can to make that happen. So if you are not happy, don’t wait, just let us know.
Here are a couple of avenues you can use to reach us.
You can voice your concerns on the Homework Sources Form that you will be filling out weekly.
You can email one of the TAs or the instructors.
We very much care about your overall well-being and happiness! Be aware that everyone on the course staff is always available to provide counsel or chat.
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.
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/
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/
The Student Academic Success Center has various resources to help you with any academic difficulties that you may have.
Website: https://www.cmu.edu/student-success/
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.
Anıl Ada (Instructor): [email protected]
Anupam Gupta (Instructor): [email protected]
Prashanti Anderson (Head TA): [email protected]
Rajeev Godse (Associate Head TA): [email protected]
Alan Zhu (Associate Head TA): [email protected]