Bellman–Ford algorithm

Worst-Case Analysis

Solving Recurrences

Median and Selection

Quick Sort

Lower Bounds for Sorting

Red-Black Trees

Graphs

Depth-first search (DFS)

Dijkstra's algorithm

Dynamic programming

Longest Common Subsequence (LCS)

Independent Set

Ford–Fulkerson algorithm

Gale–Shapley algorithm

Minimum Spanning Tree (MST)

Asymptotics

Merge sort

Randomized Algorithms

Bucket Sort

Hashing

Breadth-first search (BFS)

Strongly connected components

Floyd–Warshall algorithm

Knapsack problem

Greedy Algorithm

Max-Flow

Stable Matching

Binary Search Tree (BST)

Master theorem

CS 161 Design and Analysis of Algorithms Stanford University Winter 2023 This course provides an in-depth exploration of algorithm analysis and design. It covers various sorting, searching, and selection algorithms, data structures, and fundamental graph algorithms. It emphasizes the understanding of worst and average case analysis, recurrences, and asymptotics.  This course will cover the basic approaches and mindsets for analyzing and designing algorithms and data structures. Topics include the following: Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, amortized analysis, and randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow and string searching. Additional Calculus for Engineers (ACE) is one of the School of Engineering’s Equity and Inclusion Initiatives, designed to provide the skills and solid foundation in mathematics, computational math in engineering, and computer science to undergraduate students interested in pursuing an engineering degree. The goal of ACE is to increase confidence and content knowledge through small group interactive sessions and additional academic resources provided to students enrolled in the program. We especially want to provide an opportunity for students who come from educationally disadvantaged backgrounds or for anyone who feels they might need additional support in order to succeed. We limit enrollment to enable small classes that allow students to have one-on-one interactions with the CA. CS 106B or CS 106X; CS 103 or CS 103B; CS 109 or STATS 116. ### Textbook Information

All the following textbooks are optional. They are all excellent for supplementing lectures with details.

- *Introduction to Algorithms (3rd Ed)*, Cormen, Leiserson, Rivest, &amp; Stein ([available online!](https://searchworks.stanford.edu/view/12846639))
- *Algorithms*, Dasgupta, Papadimitriou, &amp; Vazirani
- *Algorithm Design*, Kleinberg &amp; Tardos
- *Algorithms Illuminated*, Roughgarden ([with great videos!](https://www.youtube.com/channel/UCcH4Ga14Y4ELFKrEYM1vXCg/playlists))

All students should retain receipts for books and other course-related expenses, as these may be qualified educational expenses for tax purposes. If you are an undergraduate receiving financial aid, you may be eligible for additional financial aid for required books and course materials if these expenses exceed the aid amount in your award letter. For more information, review your award letter or visit the [Student Budget website](https://financialaid.stanford.edu/undergrad/budget/index.html).

CS 161 Design and Analysis of Algorithms

Data Structures and Algorithms

Linear-time Selection

Recursion Trees

Concrete models

Tight upper/lower bounds

Amortized Analysis

Splay Trees

Streaming Algorithms

Fingerprinting

Shortest paths

Dinic’s 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

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

Bellman%E2%80%93Ford algorithm

Bellman–Ford algorithm

2 courses cover this concept

CS 161 Design and Analysis of Algorithms

15-451/651 Algorithms