Zero Sum Games

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

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

Fast Fourier transform

The Algorithmic Magic of Polynomials

Graph Algorithms

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

Matrix Multiplication

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

Zero-sum game

Zero Sum Games

2 courses cover this concept

15-451/651 Algorithms

CS 170: Efficient Algorithms and Intractable Problems