Parallel and Sequential Data Structures and Algorithms

Announcements

1. DPLab written solutions and code solutions are now available.
2. Practice final exam and solutions are now available.
3. Recitation 15 practice problems solutions are now available.
4. Rangelab written solutions and code solutions are now available.
5. DPLab is now available! It is due Monday, April 29.
6. Exam II solutions are now available.
7. RangeLab is now available! It is due Monday, April 15.

Overview

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.

The following concepts are covered:

• Problem vs. Algorithm

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.

• Asymptotic Analysis

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.

• Techniques in Algorithm Design

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.