Foundations of Computer Science¶
This document was built on Sep 12, 2022.
- The Potential Method
- Divide and Conquer
- Dynamic Programming
- Greedy Algorithms
- Introduction to Computability
- Finite Automata
- Turing Machines
- The Halting Problem
- Computable Functions and Kolmogorov Complexity
- Rice’s Theorem
- Introduction to Complexity
- The Cook-Levin Theorem
- Search and Approximation
- Randomized Algorithms
- Probabilistic Complexity Classes
- Monte Carlo Methods and Concentration Bounds
This text was originally written for EECS 376, the Foundations of Computer Science course at the University of Michigan, by Amir Kamil in Fall 2020. This is version 0.3 of the text.
This text is licensed under the Creative Commons Attribution-ShareAlike 4.0 International license.
Please report bugs and other issues here.