15-210: Parallel & Sequential Data Structures and Algorithms

Fall 2012

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

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.

30% Midterms

25% Final

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

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

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:

Ligia Nistor

Phil Mansfield

Vincent Siao

Mark Wong

Ryan Goulden

6pm, Vincent Siao, GHC 4126

6pm, Phil Mansfield, GHC 4126

9pm, Ryan Goulden, Near GHC 4307

2pm, Margaret Reid-Miller, GHC 6003

6pm, Ligia Nistor, GHC 6503

6pm, Mark Wong, GHC 4126

2pm, Umut Acar, GHC 8205

2pm, Guy Blelloch, GHC 9211