Strongly connected components

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)

Bellman–Ford algorithm

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

Big-O notation

Integer multiplication

Median finding

Coefficient/value representation

Roots of unity

Topological sorting

Paths in graphs

Kruskal's Algorithm

Linear Programming

Simplex Algorithm

Bipartite Matching

Zero Sum Games

Search problem

Reductions

Sampling

Streaming

Fast Fourier transform

Arithmetic

Recurrence relation

Matrix Multiplication

Polynomial multiplication

Complex numbers

Fourier Transform

Single Source Shortest Paths

Algorithms to Linear Programming

Duality

Multiplicative Updates

NP-completeness

Sketching

Network flow problem

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