This course 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. The course, however, 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 significant more depth on algorithmic issues.
The concepts covered by this course include:
Homeworks are due at 11:59PM US Eastern Time unless otherwise noted on the assignment.
Your homework will be considered 1 day late if it is handed in within 24 hours after it is due and 2 days late if handed in within 48 hours after it is due. You are permitted a budget of FOUR (4) late days per semester at no grade penalty (e.g. you might use 2 on 1 assignment, and 1 each on two other assignments). At most TWO (2) late days may be used per assignment. If you have used up these four late days, your score will be reduced by 25% off of the total (not your score) per late day. Except in extraordinary circumstances, no late homework will be accepted beyond the late date.
As research on learning shows, unexpected noises and movement automatically divert and capture people's attention, which means you are affecting everyone's learning experience if your cell phone, pager, laptop, etc. makes noise or is visually distracting during class.
For this reason, we ask you
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 or what is written on the board, and you must allow four 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.
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.
This is the third incarnation of the class. You can find the notes from previous editions at: