Asymptotics

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)

Merge sort

Randomized Algorithms

Bucket Sort

Hashing

Breadth-first search (BFS)

Strongly connected components

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

Java (programming language)

Class (computer programming)

Software testing

References

Recursion (computer science)

List (abstract data type)

SLLists

Nested Classes

Debugging

Array (data structure)

Array Resizing

Inheritance (object-oriented programming)

Extends

Higher-order function (HOF)

Exception handling

Object Methods

Disjoint Sets

Set (abstract data type)

Red Black Trees

Tree traversal

Multi-Dimensional Data

Prefix Operations and Tries

Reductions and Decomposition

Algorithmic Bounds

Data structure

Scope

Linked list

Shortest paths

Heap (data structure)

Kolmogorov complexity

Sentinel Nodes

DLLists

ALists

SLists

Implements

Casting

Subtype Polymorphism

Iterators

Abstract Data Type (ADT)

Map (higher-order function)

B-tree

Priority queue (PQ)

Graph traversal

Range Searching

Software Engineering

Sorting algorithm

Radix Sorts

Compression

P=NP

Static

CS 61B: Data Structures UC Berkeley Fall 2022 CS 61B focuses on software efficiency from design and runtime perspectives. It covers object-oriented programming with Java, teaching data structures and various programming concepts. The course promotes hands-on learning with optional assignments. The CS 61 series is an introduction to Computer Science, with particular emphasis on software and machines from a programmer’s point of view. CS 61A covered high-level approaches to problem-solving, providing you with a variety of ways to organize solutions to programming problems as compositions of functions, collections of objects, or sets of rules. In CS 61B, we move to a somewhat more detailed (and to some extent, more basic) level of programming by focusing particularly on the efficiency of writing programs (design) and running programs (runtime).  This class assumes you have taken CS 61A, CS 88, or E 7, or have equivalent background to a student who has taken one of these courses. The course is largely built upon the assumption that you have taken CS 61A. CS 88 and E7 students may find the beginning of the course to be a bit scarier, particularly when it comes to object oriented programming. We assume you are coming in with zero Java experience, but we will move through basic Java syntax very quickly.

We recommend all students to complete the [optional introductory assignment](https://fa22.datastructur.es/materials/hw/hw0/) by the beginning of the semester to get comfortable with Java and practice some of the programming skills expected by this class.

If you already have Java experience, great! We hope that you’ll help out your fellow students in discussion, lab, and on our class forum, particularly in the opening weeks when everyone is catching up on Java. **There is no required textbook for the class.**

There is an online textbook written by myself and a large team of former TAs. It can be found at https://joshhug.gitbooks.io/hug61b. If you find these notes insufficient, you might consider consulting [Paul Hilfinger’s (free) Java Reference](http://www-inst.eecs.berkeley.edu/~cs61b/fa14/book1/java.pdf) or [Head First Java, 2nd Edition by Sierra and Bates (O’Reilly, 2005)](https://www.google.com/search?q=head+first+java). These are not required for the course. The **optional** textbook for the weeks 5-14 of the course is Algorithms, 4th Edition by Wayne and Sedgewick.

The official description of the Java core language is available online in [The Java Language Specification](https://docs.oracle.com/javase/specs/jls/se17/html/index.html) (Java SE 17 Edition) by James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Buckley, Daniel Smith, and Gavin Bierman. It’s extremely thorough and precise, at the expense of being quite dense and technical. You will find the official [Java 17 documentation](ttps://docs.oracle.com/en/java/javase/17/docs/api/index.html) to be useful as well

CS 61B: Data Structures

Asymptotic analysis

Asymptotics

2 courses cover this concept

CS 161 Design and Analysis of Algorithms

CS 61B: Data Structures