Algorithms to Linear Programming

Arithmetic

Big-O notation

Bipartite Matching

Coefficient/value representation

Complex numbers

Depth-first search (DFS)

Duality

Dynamic programming

Fast Fourier transform

Fourier Transform

Greedy Algorithm

Integer multiplication

Kruskal's Algorithm

Linear Programming

Master theorem

Matrix Multiplication

Median finding

Minimum Spanning Tree (MST)

Multiplicative Updates

NP-completeness

Network flow problem

Paths in graphs

Polynomial multiplication

Recurrence relation

Reductions

Roots of unity

Sampling

Search problem

Simplex Algorithm

Single Source Shortest Paths

Sketching

Streaming

Strongly connected components

Topological sorting

Zero Sum Games

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

Data Structures and Algorithms is the foundation of many other areas of computer science, as well as a requirement for many Computer Science-related jobs. Common sub topics include: Linked Lists, Stack and Queues, Trees, Hash Tables, Sorting and Search Algorithms etc.

Data Structures and Algorithms

Computer Science

Theoretical Computer Science (TCS) is a subset of computer science that focuses on the more abstract, mathematical aspects of computing. Its main purpose is to understand the nature of computation, to provide rigorous frameworks for designing and analyzing algorithms, and to determine the inherent limitations of efficient computation. Common sub-topics include algorithms and data structures, complexity theory, automata theory, cryptography, and other mathematical models of computation.

Theoretical Computer Science

CSE 373 Data Structures and Algorithms University of Washington Summer 2022 This course focuses on common data structures and algorithms. It integrates theoretical understanding with practical exercises, preparing students for software-related roles and industry technical interviews. Programming projects, unit testing, and source control techniques are emphasized.  In this course, you will gain a strong theoretical and conceptual understanding of common data structures and algorithms, as well as how to apply them within larger programming projects.

Specific topics we will cover include:

- **Data structures and ADTs**: lists, stacks, queues, sets, dictionaries, linked lists, arrays, trees, balanced trees, AVL trees, hash tables, priority queues, binary heaps, and disjoint sets.
- **Graphs and graph algorithms**: graph search, shortest path, and minimum spanning trees.
- **Algorithm analysis**: asymptotic analysis, and P and NP complexity classes.
- **Sorting** and divide-and-conquer.

This course is designed to have a practical component to help you gain basic familiarity with techniques used within industry. In particular, you’ll be asked to:

- Work on **programming projects** and integrate your work in an existing codebase.
- Learn how to use an **industrial-strength IDE**.
- Learn techniques for **checking correctness**: writing unit tests with JUnit, designing and checking invariants, etc.
- Learn how to collaborate on a single code base using **source control** repositories.

Finally, this course emphasizes the importance of making and justifying design decisions. Taken together, all of the above skills are chosen to set you up for success in a software-related role. In fact, this course is typically regarded as useful preparation for industry and technical interviews. [CSE 143](https://courses.cs.washington.edu/courses/cse143/), or similar Java programming experience. 

CSE 373 Data Structures and Algorithms

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

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

CS 166 Data Structures Stanford University Spring 2022 Focused on the design, analysis, and implementation of data structures, this course assumes familiarity with the command-line, designing, testing, and debugging nontrivial programs, among others. It explores some of the most fascinating constructs in data structures.  Welcome to CS166, a course in the design, analysis, and implementation of data structures. We've got an exciting quarter ahead of us - the data structures we'll investigate are some of the most beautiful constructs I've ever come across - and I hope you're able to join us.  CS166 has two prerequisites - CS107 and CS161. From CS107, we'll assume that you're comfortable working from the command-line; designing, testing, and debugging nontrivial programs; manipulating pointers and arrays; using bitwise operators; and reasoning about the memory hierarchy. From CS161, we'll assume you're comfortable designing and analyzing nontrivial algorithms; using O, o, Θ, Ω, and ω notation; solving recurrences; working through standard graph and sequence algorithms; and structuring proofs of correctness. 

CS 166 Data Structures

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

CS 170: Efficient Algorithms and Intractable Problems

Overview

Prerequisites

Learning objectives

Textbooks and other notes

Other courses in Data Structures and Algorithms

CSE 373 Data Structures and Algorithms

CS 161 Design and Analysis of Algorithms

15-451/651 Algorithms

CS 166 Data Structures

CS 61B: Data Structures

Courseware availability

Covered concepts