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.
Starting with ancient algorithms for arithmetic, 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 and 21-127.
Lectures will be held every Tuesday and Thursday at 3:00-4:20. We strongly recommend that you attend every lecture; there will be a short quiz every week as a sanity check and class participation will factor into your final grade.
In addition, weekly recitation sections will be held on Mondays. Recitations will be used to supplement lecture material and practice working on problems in small groups. Attendance is MANDATORY.
The course website is located at http://www.andrew.cmu.edu/course/15-251. Everything you could possibly want to know about the course is located here.
References. There is no required text for the course. The material is fairly diverse, and no standard text contains it. Copies of the slides used in the lectures will be handed out or made available on the web. If you want to look at books which contain part of the course material, I recommend the following:
Getting Help. 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 recommend posting to the class discussion board: Piazza. Please keep discussion polite and be careful not to give out information about the homework solutions. If you have a more specific question, we recommend emailing your TA (contact information is located on the website.)
Additionally, everyone on the course staff will have weekly office hours - times and locations are posted on the course website.
Your grade will depend on the following factors.
Homeworks. There will be 11 (eleven) homework assignments. We will drop the lowest grade homework assignment.
Exams and Final. There will be two midterm exams, and a final.
Grade. Your numerical grade will be calculated according to this table
Coursework Grading Scale
Grades for the course will be determined by a curve. First, we will compute a weighted total of each student's scores on assignments and exams. These will be plotted as a histogram, and then approximate cutoff points for the different letter grades will be determined. Very roughly, we expect to give you
an A, if your score is one deviation or more above the class averageAt the same time we will honor a fixed grading scale. We guarantee you
an A, if your score is above 90%Individual cases, especially those near the cutoff points may then be adjusted upward or downward based on factors such as extra credit and participation in recitation discussions (TA discretion). Homework
Homework is the heart and soul of this course. Solving the problems is the only way to gain mastery of the material. Plus, putting the effort in now will alleviate suffering when you get to higher-level theory courses :).
Typesetting. You must typeset your answers to the homework sets. Almost all technical and scientific publications are produced using a typesetting system called LaTeX and you must use it: once you get past the initial learning curve, itís the most painless way to type up your homework.
Submission. Homeworks should be submitted electronically via the submission site of the course.
Late Work. In order to accomodate circumstances that may prevent you from getting a homework in on time, we grant you 8 late days, but you cannot use more than 2 late days per homework. No credit for homework submitted more than 2 days after the due date.Extensions on homeworks will generally only be granted for compelling reasons e.g. an illness (with a doctor's note) or personal or family emergency. In particular, being busy or having a bunch of assignments due at the same time are not reasons for which extensions are granted.
If you have a good excuse (such as being very sick), you should contact the professors. For compelling reasons (that extend beyond the fact that you have a lot of work lately and didnít plan ahead), we will excuse you from the lateness penalty.
Collaboration. Discussing ideas and problems with others is an excellent way of learning, and we encourage you to work together in small groups of up to four people. Also, you should think about each problem by yourself for at least 30 minutes before starting any collaboration. Remember that when working on homework problems, however, you need to solve and write up the actual solutions alone. Itís acceptable to discuss possible approaches with others, but you should fill in details and write up your solutions independently. At the top of your homework sheet, please list all the people with whom you discussed any problem. Crediting help from other classmates will not take away any credit from you, and will prevent us from assuming cheating if your answers look similar to theirs. Assigning proper credit is the required practice in all of academia.
Collaboration not only helps get the job done, it teaches you how to explain your ideas to others. This is why we permit discussion of the problems between students. Be careful not to let other people do all the work. If you misuse the opportunity for collaboration in this manner, you will fail the exams and do poorly in the course.
For clarity, here is a partial list of things that would be considered cheating rather than collaboration:
Cheating is bad. All of you are intelligent people and should know what is acceptable and what is not. There are two special points that weíd like to make here, though.
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. Hence the reason why we have a separate document for you to read, sign and return.