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.

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

Resources

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:

1. Applied Combinatorics, by A. Tucker, published by Wiley & Sons.
2. Concrete Mathematics: A Foundation for Computer Science, by R. Graham, D. Knuth, and O. Patashnik, published by Addison-Wesley.
3. Discrete Mathematics and its Applications, by K. H. Rosen, published by McGraw- Hill.
4. Cryptography: Theory and Practice, by D.R. Stinson, published by CRC Press.
5. How To Solve It: A New Aspect of Mathematical Method, by G. Polya, published by Princeton University Press.
6. Conceptual Blockbusting: A Guide to Better Ideas, by J. L. Adams, published by W. W. Norton & Company.
7. The Heritage Of Thales, by W.S. Anglin and J. Lambek, published by Springer- Verlag.
8. The Book Of Numbers, by John H. Conway and Richard K. Guy, published by Springer-Verlag.
9. Aha! Gotcha (Paradoxes to puzzle and delight.), by Martin Gardner, published by Freeman Publishers.
10. Proofs From The Book, by Martin Aigner and Gunter Ziegler, published by Springer- Verlag.

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.

Grading

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

Course Assignments	Weights
Final test	30%
2 Midterms	30%
HWs	40%

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 average
a B, if your score is within one deviation above the class average
a C, if your score is within one deviation below the class average
a D, if your score is two deviations below the class average.

an A, if your score is above 90%
at least a B, if your score is within 80%-90%
at least a C, if your score is within 70%-80%
at least a D, if your score is within 60%-70%

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.

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:

• 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. 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.

• 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: the rules and penalties

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.

• 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

• 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.