MAS 714: Algorithms and Theory of Computing

The course consists of two parts: algorithms and complexity.
The first part (algorithms) is based on Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (any edition).
The second part (complexity) is (loosely) based on the book Introduction to the Theory of Computation by Sipser.
The instructor is Asst. Prof. Hartmut Klauck.


Mo  10:30-11:30 (Lec),  SPMS-TR+12
Mo  11:30-12:30 (Tut),  SPMS-TR+12
Tue 10:30-12:30 (Lec),  SPMS-TR+12


Material covered


Lecture 1:  PDF [Introduction, Big O, Sorting, Searching]
Lecture 2:  PDF [Quicksort, Master Theorem, Randomized Quicksort, Lower Bound]
Lecture 3: 
PDF [Non-comparison based Sorting, Graphs, BFS]
Lecture 4: 
Lecture 5: 
PDF [DFS and Applications, Dijkstra]
Lecture 6: 
PDF [Priority Queues: Heaps, Bellman Ford]
Lecture 7:  PDF [Bellman Ford, APSP, Dynamic Programming]
Lecture 8:  PDF [Euler Circuits/Paths, Minimum Spanning Trees]
Lecture 9:  PDF [Minimum Spanning Trees, Union Find]
Lecture 10: PDF [Max Flow Problem]
Lecture 11: PDF [Max Flow and Matching]
Lecture 12: PDF [Linear Programming, Duality, Examples]
Lecture 13: PDF [Linear Programming: Simplex, Strong Duality]
Lecture 14: PDF [Complexity Classes, Turing machines, P]
Lecture 15: PDF [NP]
Lecture 16: PDF [NP-completeness, SAT]
Lecture 17: PDF [More NP-completeness]
Lecture 18: PDF [More NP completeness, Computability]
Lecture 19: PDF [More Computability, Time Hierarchy]
Lecture 20: PDF [Time Hierarchy, Space, Automata]
Lecture 21: PDF [DFA, NFA, Myhill-Nerode]
Lecture 22: PDF [2-way Automata, Automata Size, Probabilistic Automata]
Lecture 23: PDF [DFA  minimization, Regular Expressions, SPACE(o(loglog n)]


Tutorial 1: PDF
Tutorial 2: PDF
Tutorial 3: PDF
Tutorial 4: PDF
Tutorial 5: PDF
Tutorial 6: PDF
Tutorial 7: PDF
Tutorial 8: PDF
Tutorial 9: PDF

Recommended Literature

Last modified: November 11, 2019