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)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.
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.
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 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:
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.
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.
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.