# Parallel and Sequential Data Structures and Algorithms

## 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. Concepts covered in this class include:

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