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.