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

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 of what is written on the board, and you must allow two 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.

It is not acceptable to share your solutions or give hints to your friends for a lab after you have already discovered the correct idea. You are not helping your friends by doing so. The right thing to do is to not talk about the lab after you have a solution, and anyone struggling with the homework should visit office hours to talk to an instructor or TA. This shows the respect deserved by your friends as well as the people who have put a lot of effort into creating the labs.

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.