Linear Programming

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

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

Informed Search

Adversarial Search

Integer Programming

Propositional calculus (Propositional logic)

First-order logic

Reinforcement learning (RL)

Bayes' Nets: Independence

Bayes' Nets: Representation

Hidden Markov Model (HMM)

Particle Filtering

Game Theory: Equilibrium

Contraint Satisfaction Problems

Probability

Agents and Search

Knowledge representation and reasoning

Classical Planning

Particle Filter

Markov Decision Process (MDP)

Bayes' Nets: Inference

Game Theory: Social Choice

Logical Agents

Bayes' Nets: Sampling

Human Compatible AI

15-381 Artificial Intelligence Carnegie Mellon University Spring 2019 This course from Carnegie Mellon University provides a deep understanding of AI's theory and practice, covering methods for decision-making, problem-solving, and handling uncertainty. Topics include search algorithms, computational game theory, and AI ethics.  This course is about the theory and practice of Artificial Intelligence. We will study modern techniques for computers to represent task-relevant information and make intelligent (i.e., satisficing or optimal) decisions towards the achievement of goals. The search and problem-solving methods are applicable throughout a large range of industrial, civil, medical, financial, robotic, and information systems. We will investigate questions about AI systems such as: how to represent knowledge, how to effectively generate appropriate sequences of actions and how to search among alternatives to find optimal or near-optimal solutions. We will also explore how to deal with uncertainty in the world and how to learn from experience. We will cover the aggregation of conflicting preferences and computational game theory. Throughout the course, we will discuss topics such as AI and Ethics and introduce applications related to AI for Social Good. We expect that by the end of the course students will have a thorough understanding of the algorithmic foundations of AI, how probability and AI are closely interrelated, and how automated agents make decisions. We also expect students to acquire a strong appreciation of the big-picture aspects of developing fully autonomous intelligent agents.  The prequisite for this course is 15-122, which implies that:

1. You have taken two college level computer science courses and have the programming and computer science experience necessary for the course. Programming assignments will be in Python, which you are expected to know or learn the basics quickly.
1. You have taken the 15-122 corequisite either 21-127 Concepts of Mathematics or 15-151 Mathematical Foundations of Computer Science.

The corequisites for this course are 21-122 Integration and Approximation (or higher level calculus) and 21-241 Matrices and Linear Transformations (or 21-242). For each corequisite, you should either have completed it prior to starting 15-381 or have it on your schedule for Spring 2019.

Please see the instructors if you are unsure whether your background is suitable for the course. [Artificial Intelligence: A Modern Approach, Third Edition](http://aima.cs.berkeley.edu/) (recommended)

15-381 Artificial Intelligence

Artificial Intelligence