Course Syllabus

(PDF version)

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-100/111 and 21-127.

Organization

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 two weeks 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.

Resources

The course website is located at http://www.cs.cmu.edu/~15251. Everything you could possibly want to know about the course is located here.

References. Historically, this course has not had a physical textbook: we cover a diverse amount of material and no single book contains it all. However, you’ll notice that part of the course website is a wiki. This is a new experiment for this year: we’ll post basic notes for most of the lectures online, but feel free to modify or improve on them (indeed, you are strongly encouraged to do so).

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: cyrus.academic.cs.15-251. 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.

Grading

Your grade will depend on the following factors.

Homework. There will be twelve weekly homework assignments, which may include some programming assignments. They count for 40% of your final grade and we will drop your lowest homework grade. More information about homework is located below.

Exams and Final. There will be three exams, in total counting 30% of your grade, and a final counting 25%. Your lowest exam (out of 3) grade only counts for half (6%).

Quizzes. There will be a quiz every other Thursday in lecture as a sanity check. In total, these count for 5% of your grade. We will drop your lowest quiz grade.

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 we strongly recommend it: once you get past the initial learning curve, it’s the most painless way to type up your homework. However, any software that can typeset equations is fine (e.g. Microsoft Word, Adobe Framemaker.)

Submission. Homeworks should be submitted electronically. We will only accept files in PDF format. To submit homework N, copy your homework file to the following directory:

• /afs/andrew/scs/cs/15251/student/assignmentN/handin/userid

You can find more information about converting files to PDF here.

Late Work. The good news is that you can submit a homework assignment up to 3 days late. The bad news is that you will lose 10 points for each day it is late. Late work makes a class much harder to administer. It also hurts you. Please try to avoid it.

Programming assignments may be resubmitted any number of times throughout the 3-day grading period. Each night at midnight, starting on the night the assignment is due, our scripts will automatically collect all the new handins and grade them, taking into account the ten-point-per-day lateness penalty. We will then use your best current grade for the assignment.

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

• Showing a draft of a written solution to another student.
• Showing your code to another student.
• Getting help from someone whom you do not acknowledge on your solution.
• Copying a program from someone else.
• Looking at someone else’s work on AFS, even if the file permissions allow it.

Cheating

Cheating is bad. In fact, we have a separate sheet entirely devoted to this, which you are required to sign and return. All of you are fairly 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.

• Googling for solutions is cheating. Search engines have become much more prevalent and comprehensive since we started teaching this course, and it’s incredibly easy to type related keywords into a search box. If there’s a concept you aren’t sure of or something you don’t understand, ask us or email us. We can help you or point you to information that’s guaranteed to be high quality.
• Please do not look up previous years’ solutions or consult with people who have taken this course before. Some course material will be the same as in previous years. This is not because we are lazy. It takes years to develop good problems. The only reason to change them is to make cheating more difficult. It is far better for you to work on the most excellent problems that we have been able to find in over a decade of teaching. We appeal to your sense of honor because this is what is optimal from a pedagogical point of view.

---

Cheating Document

(PDF version)

This is an online version of the cheating document you are required to sign and return. 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.

• You may verbally collaborate on homework problems and the programming assignments. On each problem and program that you hand in, you must include the names of the students with whom you have had discussions concerning your solution. Indicate whether you gave help, received help, or worked something out together.
• You may get help from anyone concerning programming issues which are clearly more general than the specific assignment (e.g., what does a particular error message mean?)
• You may not share written work or programs with anyone else.
• You may not receive help from students who have taken the course in previous years.
• You may not review any course materials (or software) from previous years.
• You may not look up the answer to a homework assignment which happens to appear in the published literature or on the web.

Thus, clear examples of cheating include:

• Showing a draft of a written solution to another student.
• Showing your code to another student.
• Getting help from someone whom you do not acknowledge on your solution.
• Googling for specific keywords that happen to appear in the current homework assignment.
• Copying from another student during an exam.
• 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

Our reaction to your cheating will vary according to the situation.

• Confession: If you cheat and you freely admit it, we will take that into consideration. We will either give you a zero on the assignment or fail you in the course.
• Denial: If you do not admit that you have cheated, we will provide our evidence that you have done so. We will at the very least fail you in the class; furthermore, we will take our evidence to the dean and seek more substantial penalties.

All cheating issues are handled in accordance with the University Guidelines on Collaboration and Cheating.