P/NP

Abstract Data Type (ADT)

Stack (abstract data type)

Queue (abstract data type)

Map (higher-order function)

Algorithmic Analysis

Case Analysis

Algorithm Analysis

Asymptotic Analysis

Recursive Algorithm Analysis

Binary Search Tree (BST)

Hashing

AVL Trees

Tree (data structure)

Graphs

Breadth-first search (BFS)

Depth-first search (DFS)

Topological sorting

Graph traversal

Minimum Spanning Tree (MST)

Disjoint Sets

Dynamic programming

Graph Modelling

Sorting algorithm

Computer memory

Shortest paths

Heap (data structure)

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

Data Structures and Algorithms

Fundamental Results

Polynomial Time

Cook-Levin Theorem

Smalll Space

Polynomial Hierarchy

Probabilistic Classes

Reversible Computation

Turing Machines

Completeness

Nondeterminism

Ladner's Theorem

Counting

Randomness

Circuit Complexity

Complexity Theory

Hardness

Satisfiabilty

Karp's List

Polynomial Space

Kolmogorov complexity

Interactive Proofs

Hypercomputation

Computability

Time Complexity

Space Complexity

Immerman–Szelepcsényi theorem

Randomized Algorithms

Descriptive complexity theory

15-455 Undergraduate Complexity Theory Carnegie Mellon University Spring 2023 This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.  This course provides a gentle introduction into complexity theory, the theory of computations that are restricted by various resource bounds (time, space, energy, ...). We start with a brief tour of the computational universe at large and then home in on the low complexity classes that are most relevant in theoretical computer science such as P, NP, PSPACE. LOG,NLOG, BPP, RP and circuit-based classes.   

15-455 Undergraduate Complexity Theory

Theoretical Computer Science

P versus NP problem

P/NP

2 courses cover this concept

CSE 373 Data Structures and Algorithms

15-455 Undergraduate Complexity Theory