The course consists of three parts on: Automata theory (approx. 50%), computability & complexity theory (approx. 25%), graph algorithms (approx. 25%)
- Class: CPSC 406 Algorithm Analysis
- Instructor: Jonathan Weinberger, [email protected]
- Lectures: TuTh 1:00 PM -- 2:15 PM / 2:30 PM -- 3:45 PM, both KC 153
- Office Hours: Tu at N204 from 4--5:30 PM and Th at N308 from 4--5:30 PM
On Thursdays, office hours will take place in Swenson N308, 4--530.
- Syllabus
- Participation
- Report
- Git best practices
- Top 12 Git commands every developer must know
- Resources for participation
- J. E. Hopcroft, R. Motwani, J. D. Ullman: Introduction to Automata Theory, Languages, and Computation (ITALC)
- N. Deo: Graph Theory with Applications to Engineering and Computer Science (GTAECS)
The following schedule is subject to some potential changes or adjustment as the course progresses.
| Week | Topic |
|---|---|
| W1 | Introduction to automata |
| W2 | DFAs: Definition and properties, Programming (with) automata |
| W3 | Operations on automata |
| W4 | Extended transition function, NFAs and Determinization |
| W5 | Regular expressions |
| W6 | Minimization |
| W7 | Pumping Lemma |
| Spring Break | |
| W8 | Computability, Turing machines, (un)decidability |
| W9 | Algorithm complexity & Big O |
| W10 | Complexity classes and P vs NP |
| W11 | Constraint satisfaction problems |
| W12 | Graph algorithms I (Shortest paths) |
| W13 | Graph algorithms II (Flow networks) |
| W14 | Graph algorithms III (Game theory) |