Syllabus

Please familiarize yourself with the information on this page. Not following the policies described on this page can cost you points; they are part of the "cost model."

Course Textbook

The professors for the course are developing a textbook. You can find the current version here. We will also post "chapters" on the schedule but these chapters are being deprecated and will not be updated--they are kept purely for convenience. Updated notes will be made available on Diderot.

Lectures

We would love to see you in class. So please come, sit close to the front, and interact. Interacting with the course staff is fun and a great way to learn. However, please do not talk with your neighbors unless it is a specific time specified by the instructor for interacting. Because of the acoustics of the room, even very quite conversations are clearly audible to the instructor, which can be very distracting.

Wednesday Lectures

Regular lectures will generally not occur on Monday though we might have make-up lectures. These will be announced in class.

Grading Policy

The exams are graded on a curve, and the assignments are graded on a bucket system described below. Also to get a C or better in the class you need at least a C average or better on the assignments, and a C average or better on the three exams.

The grading policy is designed with two goals in mind: 1) reduce unnecessary stress by providing students with flexibility in managing their deadlines and giving them multiple chances, 2) minimize administrative load of the teaching staff so that they can spend their time on more productive endeavors such as creating teaching materials. Please read the policies below carefully.

Our philosophy is to use grading only as a tool to encourage clarity of explanation, introspection, and self-learning. We hope that both instructors and students can think about grades in as relaxed a manner as possible. We don't want you to stress out about grades, because we don't think they matter as much as what they are made up to be. In return, we expect you to be relaxed about grading! This means that you should not sweat the few points that you might have lost in an exam or a homework because: 1) they don't matter, and 2) we provide ways for you to make up for your mistakes.

There will be weekly assignments (12 total), 2 exams during the semester, and a final. The due dates and exam dates will all be posted on the course schedule. The assignments will be distributed via Autolab. Each assignment will have a coding section, a written section, or both. Coding tasks will be submitted and graded on Autolab. Written tasks will be in submitted and graded on Diderot.

Each assignment will have a total score usually between 100 and 200 points (some less). The total score for all the assignments will be around 1500 points. As usual, you earn points on each graded assignment. Perhaps, somewhat unusually, you don't have to earn all the points to get full credit. Instead all you have to do is reach 75% of the total available points for full credit. You can earn points in however way you like. For example, you can score 75% on all the assignments, or you can score 100% in most of the assignments and not even attempt a few of them. We would encourage you to do all of the assignments, because this is the best way to learn the material. This advice is based on the feedback from more that thousand students who have taken this course so far. Indeed, having been developed and refined over many years with many hours of hard work, the assignments are good! Don't miss the opportunity to do them and to learn from them.

Participation in recitation (i.e., showing up) will contribute .4 percentage to your grade for each recitation for up to 4 percentage across the semeter. That is to say, if you show up to 10 recitations across the semester then you get full credit. Of course we hope you show up to all of them.

That said, we understand this course might not be your thing or you may be interested in different topics. Please don't feel bad about that. It is to your and to society's best interest that you find what you are good at *and* what you enjoy.

In grading, we will reward not only correctness but also clarity and simplicity. If we don't understand your argument or solution in a reasonable amount of time, we will not give you points (because we naturally have to limit the amount of time we spend grading). We recommend that your think of your score as being inversely proportional to the amount of time it took for us to understand it. We will not argue about points taken off for hard-to-understand solutions. In order to avoid losing points for this reason, you should make sure your code is either self-explanatory or contains good comments; bad comments make your code harder to read. If you find that you score less than expected, this is probably because your solutions are not simple. In that case, take this as an opportunity to improve your skills in coming up with simple solutions and explaining them simply. You will likely be grateful that you were challenged in this way, i.e., to increase the clarity of your thinking and the simplicity of your explanations. This might be one of the most important things that you learn in your life!

Grading your assignments is lot of work for your TA's, especially determining the cost bounds for your code. For each coding assignment, you can help us by providing a statement of what you think your cost bound is and a short description of why you think that this bound holds. Think of this as a safety mechanism to help you avoid losing points; just as we may take off points for unclear code, we may take off points if we don't understand the costs associated with your solution. Thus you want your comments to be helpful! See the 210 style guide for an example.

As we give you some slack regarding homework, we may also choose to not grade certain questions or certain parts of each assignment (although we will grade the majority of your work). In such cases, everyone will receive a full score for the ungraded parts.

Late Assignments

Homeworks are due at 5:00 PM US Eastern Time unless otherwise indicated on the assignment or on Piazza (remember to check your email). You may submit up to two days late on Autolab and/or Gradescope, with a 20% score penalty for each day (for example, if you turn in one day late and score 85 points then you would be deducted 17 points).

In terms of grading, the coding and written portions of each assignment are considered separate; you could, for example, submit the coding one day late at a 20% penalty and the written two days late at a 40% penalty.

Except in extraordinary circumstances (severe sickness with a doctor's note, etc), no late homework will be accepted beyond two days past the deadline.

We will not be able to grant you any extensions for any reason other than a medical condition that seriously undermines your ability to do your work, by for example hospitalizing you for more than 5 days. Common cold, flu, etc are not sufficient. In case of a serious medical condition, please ask your academic adviser to email the professors. Please do not email the course staff personally.

Style Grading

Handed in code will be graded for style and clarity on a pass/fail basis. You should refer to the style guide for general guidelines.

If your coding style on a particular homework assignment is sufficiently poor, then you will receive a score of 0 for the programming portion of that assignment. In order to restore your grade, you must:

  1. review the comments given on Autolab (which will detail why you failed style grading),
  2. rewrite your code for the lab (do not resubmit), making sure to address every comment, and
  3. show your new code to a TA (preferably at office hours) before the regrade deadline and explain your fixes.

If your new code is acceptable, the TA will change your style grade for the assignment to a "pass". Your original Autograded score will then be restored. It is very important that you do not attempt to resubmit any fixed code to Autolab. All submissions after the deadline are considered late, and will be graded with a penalty.

2 Week Cut-off

All issues regarding a given assignment or exam must be resolved within two weeks of the grades being released and announced (on Piazza). After the two week deadline, we will throw away unclaimed written feedback, and set the grades in stone. This means that if you need to contest a grade, fix a failed style grade, or have any other problems regarding an assignment, you must come to the course staff within two weeks!

To resolve any grading issues, you should talk directly to the TAs assigned to your recitation section. You may speak with them in recitation, at their office hours, or by email. Please do not send an email to the entire 15210 staff mailing list.

Exams

For special accommodations on exams (or otherwise) students should submit an accomodations letter to one of the intructors. For extra time on exams we then ask that you arrange it to be proctored through the disability services office (assuming you have given us the form). We will work with them to get them a copy of the exam. For other issues please contact the instructor.

No make up exams are given, except for medical reasons. To schedule a make-up exam, ask your academic advisor to contact the instructors. Please do not email the course staff personally. You will need to provide medical documentation that shows that you cannot take the exam.

Communication: E-mail, Diderot, Piazza, This Website

When you need help from the course staff, please consider using Diderot and piazza first (see piazza usage etiquette below). If piazza is not appropriate then you can email us at 15210-s18-staff@lists.andrew.cmu.edu. Please refrain from emailing professors or individual TA's, except in cases that require privacy. Of course you are always welcome to office hours, or to ask the TAs or professor questions after class, time permitting.

When not to email staff. Please remember that this is a large class and refrain from unnecessarily emailing course staff. Here is an incomplete list of subjects that are included in the definition of unnecessary emails. This list is not definitive, it is your responsibility to familiarize yourself with the policies (as outlined in this document) and follow them. If you don't follow them, you may lose points.

  1. Waitlists. In the beginning of the semester, there will likely be a waitlist and we will make a decision about how many students to let in. We will then let the department administrators know about this decision and they will enroll waitlisted students. We cannot and do not honor individual requests. Thus, please do not email us about waitlists issues. If you did not get into the class and you were on the waitlist, the best person to talk to is probably your academic advisor and other relevant department's administrators.
  2. Deadline extensions, make-up exams, etc. See policies above.
  3. Grades, exam scores etc. Now that you are in college, we expect you to develop a value system that centers around your contribution to the science and society, not your grades. We value you much more than your grade or the score you get on an exam. So please do not email us matters about your scores and grades. Instead focus your energy on orienting your value system towards things that matter. Grades are not part of that.
  4. Questions. Questions regarding assignments and lecture material. Please use Diderot and piazza.

We will post announcements, clarifications, corrections, hints, etc. on the course web site, Diderot, and Piazza---please check them on a regular basis. When using Piazza we ask that you follow the following guidelines:

When to ask a question. Urgent and important questions such as bug in the homework distribution that you just discovered, should be posted on Piazza as soon as possible. For all other questions see the next paragraph.

When to ask a question. Piazza is a great tool but it can create a temptation to ask every question that you may have, especially when you know that you will get a quick response. Resist that temptation as it is not good for your learning. To learn well and to learn how to think like a creative computer scientist, it is important that you give your mind the time it needs to learn. That means thinking about the questions by yourself on your own and doing the needed research on your own before seeking an answer. So in summary resist that temptation to ask immediately. But do ask after you think and reflect on the question yourself and still have not found an answer. To organize your thinking, use Diderot's reflections. Remember that you can share Diderot reflections on Piazza and they will remain to be visible only to the instructors and TA's. Diderot reflections are essentially private.

Private versus public questions. It is important that you make your questions public rather than private because otherwise the course staff have to respond to the same question many times (private questions cannot be seen by your classsmates). Thus except in special circumstances (e.g. your post contains a hint to the solution of a homework problem), avoid using private questions. As a rule of thumb, if you don't feel comfortable making your question public, then it might not be an appropriate question for Piazza at all. For example, in general, posting a piece of code that you wrote and asking the TA's to correct it for you is not an appropriate question for Piazza.

Use of Standard ML

While the lecture notes and the book use a pseudo-code language to specify the algorithms, the labs in the course nearly all involve programming in the Standard ML (SML) language. If you are a CMU undergraduate, then you should have little or no difficulty with SML. If you are not an undergraduate student or if you don't know SML or another functional language, then you might have significant difficulties in the course. Many graduate students without prior functional-programming experience have tried this course, but except for very few, have given up, primarily because the pace is too fast for learning a new language.

There are several reasons for why we use SML. The primary reason is that the course is based on the idea of designing algorithms with a clear distinction between specification and implementation, and using cost models to bridge the gap. Within the domain of functional programming, this leaves only a few languages, namely the ML family, including SML and OCAML, and a language such as Scala. We choose the ML family, because they are smaller languages and more suitable for teaching. From within the ML family, we use SML because we have developed a compiler for this language that can generate parallel executables.

The course material can in principle be taught in a non-functional lower-level language such as C/C++. But with such a language, it would be difficult (probably impossible) to cover the material covered by our labs in this course. As the students will likely experience in their last lab using C++ (PASLlab), writing correct parallel programs in imperative languages can be very tedious, e.g., even a simple bug can require many hours of low-level debugging. It can also be rewarding, however, because it is sometimes possible to write faster programs, for example, by controlling memory layout. We encourage the students to learn about these techniques in more focused courses, also taught at Carnegie Mellon.

Using a strict functional programming language such as ML can lead to some loss of performance, let say, out of generosity towards non-functional languages, 10-fold, but this usually comes with a big reduction in time needed to write correct parallel codes, let's say 5-fold. In an algorithms course, we don't worry about 10x slowdown in performance; it is absorbed by the asymptotic notation. But, a 5-fold increase in programming effort is untenable. Functional programming shields us from the complexities of concurrency and the realities of hardware, allowing us to focus our efforts on algorithmic concerns, which is the topic of this course.

How to Learn Well

The best way to learn is to push yourself to learn the material and enjoy the struggle! If for example, you are able to come up with the answers quickly, this is not because you are super smart, but because you have had the relevant experience. Sorry but we don't believe in genius. If you are not able to come up with answers quickly, this just means that you have not had the experience and thus you need to build it. So that is all that there is to it. Don't be harsh on yourself in you are not doing as well as you expected. Simply do your work to the best that you can and enjoy the process of failing and learning. If you find that the material easy and you enjoy it, that is great. You are lucky! If you don't enjoy it, then you should probably move on to the next step on your path, so see about doing that. We would recommend: 1) taking notes (the physical action of taking notes often aids learning), 2) as you read the course notes, write down a list of questions and try to solve them, 3) develop a habit of formulating variants of exercises and homeworks that you are given and solving them and coming up with new questions, 4) think about and research the questions that you may have by yourself and try to find the answers on your own (for example for 24 hours), before talking to your friends and course staff. Of course, everyone learns in a different way, but if you feel that you are having trouble learning in this course, we will point you here first.

Word of Caution

You will likely find this course to be difficult. There are several reasons why. First, the material covered in the course, with emphasis on parallelism, will be new to many of you. Second, the way we design our algorithms and implement them, with emphasis on higher-order programming (where functions are first-class values), can be difficult to grasp quickly, though over time you will likely not be able to imagine thinking without them. Third, this course will require generating your own algorithms in addition to understanding existing algorithms. If you don't know Standard ML, then there will also be the additional overhead of learning a new programming language, and you should start learning it immediately. There are many online resources for doing so.

It is thus important for you to mentally prepare yourself for a difficult course. If you do your work, we are confident that you will finish this class with a satisfactory grade. As you will discover throughout the semester, we have an excellent set of teaching assistants that can help great assistance. That said, you should keep in mind three things 1) there is no substitute for doing your own work, and 2) there is no substitute for doing your own work and 3) the first two things.

Academic Integrity

All students are expected to be familiar with, and to comply with, the University Policy on Cheating and Plagiarism.

Any work submitted as a homework assignment or examination must be entirely your own and may not be derived from the work of others, whether a published or unpublished source, the worldwide web, another student, other textbooks, materials from another course (including prior semesters of this course), or any other person or program. You may not copy, examine, or alter anyone else's homework assignment or computer program, or use a computer program to transcribe or otherwise modify or copy anyone else's files.

To facilitate cooperative learning, it is permissible to discuss a homework assignment with other students, provided that the following whiteboard policy is respected. A discussion may take place at the whiteboard (or using scrap paper, etc.), but no one is allowed to take notes or record the discussion of what is written on the board, and you must allow two hours to lapse after any discussion before working on the assignment. The fact that you can recreate the solution from memory is taken as proof that you actually understood it.

It is not acceptable to share your solutions or give hints to your friends for a lab after you have already discovered the correct idea. You are not helping your friends by doing so. The right thing to do is to not talk about the lab after you have a solution, and anyone struggling with the homework should visit office hours to talk to an instructor or TA. This shows the respect deserved by your friends as well as the people who have put a lot of effort into creating the labs.

In order to deter cheating we also run automatic code comparison programs (such as MOSS). These programs are very good at detecting similarity between code, even code that has been purposefully obfuscated. Such programs can compare a submitted assignment against all other submitted assignments, against all known previous solutions of a problem, etc. The signal-to-noise ratio of such comparisons is usually very distinctive, making it very clear what code is a student's original creative work and what code is merely transcribed from some other source. Often in previous semesters, however, we have discovered cheating due to the simple fact that the TAs are familiar with many different versions of the solution. Cheating is simply not worth the risk.

One final note: receiving credit for an assignment or exam is not an indication that we did not catch you cheating. Because dealing with cheating cases is a lot of work for the TA's and the instructors, we often delay enforcement until well into the second half of the semester and take action all at once, after we identified a number of cases. This usually leads to unfavorable outcomes for the students involved. Consequences for cheating may be as severe as failing this course and being reported to the Office of the Dean of Student Affairs.