Announcements

• We hope you had an enjoyable semester. Here is a complete set of lecture notes in a single pdf file.

Overview

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:

• Problem vs. Algorithm: A problem defines an interface (e.g., sorting) while an algorithm defines a particular method to solve the problem (e.g., quicksort). Being able to cleanly define a problem is key in the process of putting together large programs and in reusing their components. We cover a variety of fundamental problems (sorting, minimum spanning tree, nearest neighbors, ...) and a variety of algorithms for solving them (quicksort, Dijkstra's algorithm, ...).
• Asymptotic Analysis: Although the so-called big-O analysis is not going to accurately predict wall-clock time, it is critical for getting a rough estimate of the performance of an algorithm and helping guide algorithm design and selection. In the class, we analyze performance in terms of work, span and space. We cover a variety of techniques for analyzing asymptotic performance including solving recurrences, randomized analysis, and various counting arguments.
• Techniques in Algorithm Design: There are just a few techniques that play the key role in the the design of most parallel/sequential algorithms and data structures. In this class, we cover these techniques, including using collections (sets, sequences, priority queues, ...), divide-and-conquer, contraction, the greedy method, balanced trees, hashing, sparse matrices, and dynamic programming.

The assignments use Standard ML (SML). We use Standard ML for several reasons, including: (1) it is safe for parallelism, (2) it properly supports higher-order functions, and (3) its module system does a good job of supporting abstract interfaces without confounding interfaces with state.

Course Information

Textbook:

There is no course textbook. Course notes will be provide instead. As we may not be able to cover all the material during lectures, please read the notes for additional background and further details.

Grading:

45% Assignments
30% Midterms
25% Final

Policy

Late Assignments

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.

Electronic devices during class

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

• to turn off the sound on your electronic devices, and
• to sit in the back row if you plan to use your laptop.

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

Previous Editions

This is the third incarnation of the class. You can find the notes from previous editions at:

• Spring 2012
• Fall 2011