15-251 Great Theoretical Ideas in Computer Science

Welcome to 15-251! This course will take a philosophical and historical perspective on the development of theoretical computer science. From using a pile of stones to represent and manipulate numbers, humans have progressively developed an abstract vocabulary with which to mathematically represent their world. The ancients, especially the Greeks, realized that they could consistently reason about their representations in a step-by-step manner. In other words, by computing in abstract models, they could describe and predict patterns in the world around them.

In this course, we will revisit the development of mathematics from a computational point of view. Conversely, we will mathematically study the nature of computation itself. What is computation? What is computable, in principle? What is especially easy, or especially hard to compute? To what extent does the inherent nature of computation shape how we learn and think about the world?

Prerequisites: 15-112 and 21-127

Organization

Lectures will be held every Tuesday and Thursday from 3:00pm to 4:20pm at DH 2210. There will be weekly recitation sections held on Fridays. Recitations will be used to supplement lecture material and practice working on problems in small groups. Please try to attend the recitation session that you signed up for. We will take attendance in most lectures and recitations. This will factor into your participation grade at the end of the semester (see the Grading section below).

In addition, Wednesdays from 6:30pm to 7:50pm will be used for "Homework Writing Sessions". More information about these sessions can be found under the Homework System section below.

Resources

There is no required text for the course. The material is fairly diverse, and no standard text contains it. The lectures will be recorded and the links to the video recordings as well as the slides will be provided on the course website. We may provide lecture notes for some of the lectures. If you want to look at books which contain part 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

Communication with the Course Staff

Every student is required to signup for the course's Piazza page! Course related announcements will be made using Piazza, so you must check Piazza every day.

If you have a question about a lecture concept or wording on a homework problem, there's a good chance that other students in the class have the same question. Thus, we strongly recommend posting your question to Piazza. Please keep the discussion polite and be careful not to give out information about the homework solutions. If you have a question that is specific to you personally, please email your TA. If you would like to make a regrading request, please contact the TA who has graded that question directly.

Everyone on the course staff will have weekly office hours - times and locations are posted on the course website. You are strongly encouraged to attend office hours. In fact, the homeworks are prepared with the assumption that you'll get support during office hours.

Grading

Your grade will depend on the following factors.

Homeworks. There will be 11 homework assignments. The lowest score will be dropped.

Midterm Exams. There will be 2 Midterm exams (Oct 14, Nov 18, from 6:30pm to 9:30pm). Your lower Midterm score will be half-weighted.

Final Exam. There will be a Final exam at the end of the semester.

Quizzes. There will be 12 quizzes at the beginning of recitations. The lowest score will be dropped.

Class Participation. This will be mostly based on attendance. Other factors include asking and answering questions in class, in recitations, and on the discussion board.

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

Course Component	Weight
Homework	30%
Midterm (higher score)	20%
Midterm (lower score)	10%
Final	25%
Quizzes	10%
Participation	5%

Homework System

Homework is the heart and soul of this course. Solving the problems is the only way to gain mastery of 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.

Searching the internet for general concepts is allowed. Googling for specific keywords that happen to appear in one of 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 at least half an hour 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, don't hesitate to contact the course staff.

Types of Questions: There will be 3 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. Other than the general rules stated above, there are no additional rules for this type of question.

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. In this session we will randomly pick a subset of the homework questions, 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.

For each question, 20% of the credit will be reserved for the quality of the presentation, 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 earn more points doing so rather than writing a wrong argument). Do not try to sell a wrong or incomplete proof!

Quizzes

There will be a 9-minute long quiz right at the beginning of recitations. To get the full 9 minutes, you must be seated by the start time of the recitation. These quizzes are not meant to be hard. We just want to make sure that you review that week's lectures in a timely manner.

Cheating

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 in the homework 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 accomodate students that require extended time approved by Larry Powell's office. 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 do not qualify as an excused absence. Keep in mind that your lowest homework and quiz scores are dropped. You should save up your 'dropped homework' and 'dropped quiz' for when you really need it, e.g., when your computer crashes.