These are my notes for CS 374: Introduction to Algorithms and Models of Computation. I took the class Spring 2021, and here's the course website for the semester: https://courses.engr.illinois.edu/cs374/sp2021/.
The course is divided into three sections:
- Models of Computation
- What is a Regular Language
- What is a Regular Expression, Deterministic Finite Automaton (DFA), and Nondeterministic Finite Automata (NFA)
- What can and cannot be computed via DFAs and NFAs
- What is a Turing Machine
- What is a Universal Turing Machine
- Algorithms
- Reductions
- Divide and Conquer
- Backtracking
- Dynamic Programming
- Graphs
- Breadth and Depth First Search
- Directed Acyclic Graphs (DAGs), Topological Sort, and Strongly Connected Components
- Dijkstra's Algorithm
- Bellman-Ford
- Floyd-Warshall
- Limits of Computing
- Reductions
- Decideable and Undecideable Languages
- Halting Problem
- 3SAT
- P and NP
- NP Completeness
All of the material is from the course/professors: Chandra Chekuri, Patrick Lin, Nickvash Kani, and Yi Lu.
Feel free to checkout the notes on the releases pages and download a copy of the PDF.