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

• 45% Assignments
• 30% Midterms
• 25% Final

## Late Assignments

Homeworks are due at 11:59PM US Eastern Time unless otherwise noted on the assignment.

Each assignment has a late submission deadline, which is typically (but not always) two days after the lab due date. Except in extraordinary circumstances, no late homework will be accepted beyond the late submission deadline.

You are permitted a budget of EIGHT late days per semester at no grade penalty. If you have used up these eight late days, your score will be reduced by 25% off of the total (not your score) per extra late day used. Remember, you may not submit the homework after the listed late submission deadline ("Last day to handin" on Autolab).

We will not be able to grant you any additional late days for any reason other than a medical condition that seriously undermines your ability to do your work, by for example hospitalizing you for more than 5 day. Common cold, flu, etc are not sufficient. In case of a serious medical condition, please ask your academic adviser to email the professors. Please do not email us personally.