15-251 Great Theoretical Ideas in Computer Science

Course Description and Policies

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-122 or 15-150) and (21-127 or 21-128 or 15-151)

Organization

Lectures will be held every Tuesday and Thursday from 9:00am to 10:20am at GHC 4401. 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 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 provide lecture notes for most 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 or one of the instructors. 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 12 homework assignments.

    Midterm Exams. There will be 2 Midterm exams (Mar 1, Apr 19, from 6:30pm to 9:30pm). Please mark your calendars.

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

    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 1 20%
    Midterm 2 20%
    Final 25%
    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 following table and assign the higher grade. The maximum letter grade you can receive with the alternate grading scheme is a C.

    Course Component Weight
    Homework 30% (lowest 4 homeworks half-weighted)
    Higher Midterm 30%
    Final 35%
    Participation 5%

    Homework System

    Homework is arguably the most important component 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, before the homework writing session.
  • 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 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, don't 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. 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.

    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.

    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 earn more points doing so rather than writing a wrong argument!!). Do not try to sell a wrong or incomplete proof! If you leave a question completely blank, you will earn 20% of the credit for that question.

    It is very important that you learn from your mistakes and correct them. For this reason, after you get your graded homework back, you will be allowed to resubmit solutions that you have gotten wrong (deadline to be announced). If you turn in a completely correct and well-written solution, you will receive back 25% of the lost credit for that question.

    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 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 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, 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 health services, 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 has a more limited staff during the summer but is still available for you to use. They 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.
  • Hours: Monday through Friday 8:30am-5:00pm
  • Phone number: 412-268-2922
  • Location: 2nd floor, Morewood Gardens, E-Tower
  • University Health Services

    Health services can help you in the same way a doctor does but they also offer comprehensive care management and health promotion 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 TA to set up a casual meeting.

  • Anil Ada (Instructor): [email protected]
  • Bernhard Haeupler (Instructor): [email protected]
  • Anna Tan (Head CA): [email protected]
  • Chris Liu (Head CA): [email protected]


  • Valid CSS! Valid XHTML 1.0 Strict