UIUC CS 374: Introduction to Algorithms and Models of Computation

Intro

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

The course is divided into three sections:

1. 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
2. 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
3. Limits of Computing
   • Reductions
   • Decideable and Undecideable Languages
   • Halting Problem
   • 3SAT
   • P and NP
   • NP Completeness

Disclaimer

All of the material is from the course/professors: Chandra Chekuri, Patrick Lin, Nickvash Kani, and Yi Lu.

Download

Feel free to checkout the notes on the releases pages and download a copy of the PDF.