Fast Fourier transform

Memory hierarchy

Matrix Multiplication

Shared Memory Parallelism

Roofline and Performance Modeling

Sources of Parallelism and Locality

Communication-avoiding matrix multiplication

Data Parallel Algorithms

CUDA (Compute Unified Device Architecture)

Graphics Processor (GPU)

Distributed Memory Machines and Programming

Advanced MPI

Collective Communication Algorithms

UPC++: Partitioned Global Address Space Languages

Domain Specific Languages (Halide)

Distributed Data Structures (BCL)

Parallel Matrix Multiply

Dense Linear Algebra

Sparse-Matrix-Vector-Multiplication

Iterative Solvers

Structured Grids

Machine learning

Supervised learning

Deep learning

Unsupervised learning

Graph Partitioning

Graph Algorithms

Cloud Computing

Big Data Processing

High Performance Computing (HPC)

Dynamic Load Balancing

Hierarchical Methods for the N-Body Problem

Sorting algorithm

Search algorithm

Computational Biology

Quantum Computing

CS 267: Applications of Parallel Computers UC Berkeley Spring 2020 The course addresses programming parallel computers to solve complex scientific and engineering problems. It covers an array of parallelization strategies for numerical simulation, data analysis, and machine learning, and provides experience with popular parallel programming tools. CS267 was originally designed to teach students how to program parallel computers to efficiently solve challenging problems in science and engineering, where very fast computers are required either to perform complex simulations or to analyze enormous datasets. CS267 is intended to be useful for students from many departments and with different backgrounds, although we will assume reasonable programming skills in a conventional (non-parallel) language, as well as enough mathematical skills to understand the problems and algorithmic solutions presented. CS267 satisfies part of the course requirements for the Designated Emphasis ("graduate minor") in [Computational Science and Engineering](http://www.google.com/url?q=http%3A%2F%2Fcitris-uc.org%2Finitiatives%2Fdecse%2F&sa=D&sntz=1&usg=AOvVaw1fRFGvIaIYhkwE3kp4J1nf).

While this general outline remains, a large change in the computing world started in the mid 2000's: not only are the [fastest computers](http://www.google.com/url?q=http%3A%2F%2Fwww.top500.org%2F&sa=D&sntz=1&usg=AOvVaw1SiByfUjOpTR6ctURAV2Ef) parallel, but nearly all computers are becoming parallel, because the physics of semiconductor manufacturing will no longer let conventional sequential processors get faster year after year, as they have for so long (roughly doubling in speed every 18 months for many years). So all programs that need to run faster will have to become parallel programs. (It is considered very unlikely that compilers will be able to automatically find enough parallelism in most sequential programs to solve this problem.) For background on this trend toward parallelism, click [here](http://www.google.com/url?q=http%3A%2F%2Fwww.eecs.berkeley.edu%2FPubs%2FTechRpts%2F2006%2FEECS-2006-183.html&sa=D&sntz=1&usg=AOvVaw2XoPTheTzKVlyjp1G_YcM5).

Students in CS267 will get an overview of the parallel architecture space, gain experience using some of the most popular parallel programming tools, and be exposed to a number of open research questions. The lectures will also cover a broad set of parallelization strategies for applications covering numerical simulation and data analysis to machine learning.   

CS 267: Applications of Parallel Computers

Parallelism and Distributed Systems

Linear-time Selection

Recursion Trees

Concrete models

Tight upper/lower bounds

Amortized Analysis

Splay Trees

Hashing

Streaming Algorithms

Fingerprinting

Dynamic programming

Shortest paths

Bellman–Ford algorithm

Dinic’s algorithm

Floyd–Warshall algorithm

Network flow problem

Flows and Matchings

Edmonds–Karp algorithm

Min-cost Flows

Zero Sum Games

Linear Programming

Mechanism Design

Approximation Algorithms

Online Algorithms

Multiplicative Weights Algorithm

Computational Geometry

Geometric Primitives

Convex hull

Sweep line algorithm

Sweepangle

SegTrees

Closest Pair

Smallest Enclosing Circle

Byzantine Agreement

Oblivious Algorithms

The Algorithmic Magic of Polynomials

15-451/651 Algorithms Carnegie Mellon University Spring 2022 This course explores the design and analysis of algorithms, algorithmic modelling techniques, and their efficiency. It aims to provide tools for designing and analyzing personal algorithms, using various analytical tools and frameworks. Some advanced topics not commonly covered in textbooks are also taught. This course is about the design and analysis of algorithms. We will study specific algorithms for a variety of problems, as well as powerful modelling techniques (e.g. graphs and linear programming) and design paradigms (e.g. amortized analysis, dynamic programming, and sweep-line). (The complete list of topics is on the "Home/Schedule" page linked above.) We will study ways to analyze the efficiency of algorithms, and give lower bounds on the complexity of a problem. The topics have been chosen for their power, beauty, and practicality. The main goal of this course is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future. By the end of this course, you should be able to:

- Use and explain algorithm design tools discussed including divide-and-conquer, balanced search trees, hashing, graphs, randomization, dynamic programming, network flows, and linear programming, as well as basic data structure and algorithm design principles.
- Use and explain analytical tools and frameworks discussed including recurrences, probabilistic Analysis, minimax optimality, amortized analysis, analysis within different concrete models, and potential functions.
- Identify and critique incorrect analyses, find counterexamples to faulty claims and "proofs" of correctness.  - Several of the topics we teach, particularly the more advanced ones, are not covered in the standard Algorithms textbooks. Hence we will provide lecture notes covering all the material in this course.
- However, we would like you to have a book to give you more detailed coverage. (Or to give you an alternative perspective if you find our own confusing!) We recommend you get one of the following:
    - Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (hereafter referred to as "CLRS"). It's big, it's fairly expensive, but it is the gold standard of algorithms books with a lot of material. Based on the Algorithms course at MIT.
   - Algorithms, by Dasgupta, Papadimitriou, and Vazirani (herafter referred to as "DPV"). Smaller, cheaper, more informal. A relatively new book based on Algorithms courses at UC Berkeley and UCSD. A preliminary (incomplete) version is available here.
Specific readings in CLRS and DPV will be listed on the course schedule. It is recommended that you skim the reading before lecture, with a more thorough read afterwards.
- Other helpful material can be found in: Algorithm Design by J. Kleinberg and E. Tardos, Data Structures and Network Algorithms by R. E. Tarjan, Randomized Algorithms by Motwani and Raghavan, Programming Pearls by J. Bentley, Introduction to Algorithms: a Creative Approach by U. Manber, and the classic Aho-Hopcroft-Ullman book. See also some excellent lecture notes by Jeff Erickson at UIUC.

15-451/651 Algorithms

Data Structures and Algorithms

Big-O notation

Integer multiplication

Master theorem

Median finding

Coefficient/value representation

Roots of unity

Topological sorting

Paths in graphs

Greedy Algorithm

Kruskal's Algorithm

Simplex Algorithm

Bipartite Matching

Search problem

Reductions

Sampling

Streaming

Arithmetic

Recurrence relation

Polynomial multiplication

Complex numbers

Fourier Transform

Depth-first search (DFS)

Strongly connected components

Single Source Shortest Paths

Algorithms to Linear Programming

Duality

Multiplicative Updates

NP-completeness

Sketching

Minimum Spanning Tree (MST)

CS 170: Efficient Algorithms and Intractable Problems UC Berkeley Spring 2020 This is an introductory course to computer science theory, exploring the design and analysis of various algorithms, number theory, and complexity. The prerequisites include familiarity with mathematical induction, big-O notation, basic data structures, and programming in a standard language. CS 170 is Berkeley’s introduction to the theory of computer science. In CS 170, we will study the design and analysis of graph algorithms, greedy algorithms, dynamic programming, linear programming, fast matrix multiplication, Fourier transforms, number theory, complexity, and NP-completeness.  The prerequisites for CS 170 are CS 61B and CS70. You will need to be comfortable with mathematical induction, big-O notation, basic data structures, and programming in a standard imperative language (e.g., Java/C/Python). Another “prerequisite” for doing well in the course is [mathematical maturity](https://en.wikipedia.org/wiki/Mathematical_maturity), or the ability to think about and work with proof-based math (which CS70 can help build). The required textbook is [Algorithms](http://cseweb.ucsd.edu/~dasgupta/book/index.html) by Dasgupta, Papadimitriou, and Vazirani, also known as DPV. Most readings will be from the textbook, and the relevant textbook chapters will be linked for each lecture. Any readings not from the textbook will be freely available as notes.

CS 170: Efficient Algorithms and Intractable Problems

Theoretical Computer Science

Fast Fourier transform

3 courses cover this concept

CS 267: Applications of Parallel Computers

15-451/651 Algorithms

CS 170: Efficient Algorithms and Intractable Problems