# 1 Course 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 learning goals include the following.

**Problem vs. Algorithm**

A *problem* defines the desired outcomes for a specific set of conditions, i.e., it defines an interface. An *algorithm* defines a particular solution to the problem. For example, quicksort is an algorithm that solves the sorting problem. Being able to formulate a problem is key to essentially all of computer science. **Learning goal:** learn to distinguish between problems and their solutions and to define and present problems and their solutions.

**Asymptotic Analysis**

A key property of nearly any algorithm is its resource consumption, including, time, space, and energy. **Learning goal:** learn to analyze the resource consumption of algorithms in terms of work, span, and space using asymptotic analysis. To this end, the course covers a variety of analysis techniques including solving recurrences, randomized analysis, and various combinatorial arguments.

**Techniques in Algorithm Design**

When solving a problem, computer scientists typically employ a variety of design techniques and use a number of well established techniques. **Learning goal:** learn algorithm design techniques and how to apply them to solve a variety of problems. The course covers 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.

**Fundamental Algorithms and Data Structures**

Nearly all computer and software systems today ranging from small experimental ones to large scale systems utilize a number of fundamental algorithms. **Learning goal:** learn the fundamental algorithms and data structures that computer and software systems are based on. The course covers a whole variety of algorithms ranging from algorithms for a variety of data organized as sequences, sets, and graphs.