15-210 aims to teach methods for designing, analyzing, and programming sequential and parallel algorithms and data structures. The emphasis is on teaching fundamental concepts applicable across a wide variety of problem domains, and transferable across a reasonably broad set of programming languages and computer architectures. This course also includes a significant programming component in which students will program concrete examples from domains such as engineering, scientific computing, graphics, data mining, and information retrieval (web search).
Unlike a traditional introduction to algorithms and data structures, this course puts an emphasis on parallel thinking — i.e., thinking about how algorithms can do multiple things at once instead of one at a time. The course follows up on material learned in 15-122 and 15-150 but goes into significantly more depth on algorithmic issues. Concepts covered in this class include:
A problem defines an interface while an algorithm defines a particular method to solve the problem. For example, quicksort is an algorithm to solve the sorting problem. Being able to cleanly define a problem is key in the process of putting together large programs and in reusing their components.
In this class, we analyze performance in terms of work, span, and space using big-O analysis. We cover a variety of techniques for analyzing asymptotic performance including solving recurrences, randomized analysis, and various counting arguments.
We cover techniques that play a key role in the design of most algorithms and data structures, including: collections (sets, sequences, priority queues, ...), divide-and-conquer, contraction, the greedy method, balanced trees, hashing, sparse matrices, and dynamic programming.
The professors for the course are developing a textbook. You can find the current version here. We will also post "chapters" on the schedule, which will be updated during the semester. Comments are welcome and you can send them directly by email to Professor Blelloch.
There will be weekly assignments (10 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 handed out, tested, and turned in via autolab. For each test we will have a suite of public tests that will help you in doing the assignment and a suite of private tests that will help us grade.
Homeworks are due at 11:59PM US Eastern Time unless otherwise noted on the assignment.
Each assignment has a late submission deadline, which is typically (but not always) two days after the lab due date. Except in extraordinary circumstances, no late homework will be accepted beyond the late submission deadline.
You are permitted a budget of EIGHT late days per semester at no grade penalty. If you have used up these eight late days, your score will be reduced by 25% off of the total (not your score) per extra late day used. Remember, you may not submit the homework after the listed late submission deadline ("Last day to handin" on Autolab).
We will not be able to grant you any additional late days 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 day. 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 us personally.
Handed in code will be graded for style 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: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 your fixed code to Autolab. All submissions after the deadline are considered late.
If you believe that something was graded incorrectly or unfairly, or if you failed style grading and wish to restore your grade, then you must speak with a TA or instructor within two weeks of when the assignment was returned. Refer to Autolab to see regrade deadlines for specific assignments.
When you need help from the course staff, please consider using piazza first (see piazza usage etiquette below). If piazza is not appropriate then you can email us at firstname.lastname@example.org. Please refrain 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.
We will post announcements, clarifications, corrections, hints, etc. on the course web site 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. 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 as much as possible. This does not apply to certain questions. For example, a bug in the homework distribution that you just discovered.
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., you found a bug in the code distribution), 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.
You will likely find this course to be difficult. There are several reasons for 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.
We would recommend: 1) taking notes (the physical action of taking notes will help you learn), 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. Finally, if you are not used to doing these, I would recommend that you start working on them and being patient.
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.
We may sometimes 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.