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