MAS 714: Algorithms and Theory of Computing

The class consists of two parts: complexity and algorithms.
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.


Tue  9:30-11:30 (L), SPMS-TR+20
Fri  9:30-10:30 (L), SPMS-TR+20
Fri 10:30-11:30 (T), SPMS-TR+20


Material covered


Lecture    1: PPT  PDF [Introduction]
Lecture    2: PPT  PDF [Big O Notation, Sorting and Searching]
Lecture    3: PPT  PDF [Quicksort, Master Theorem]
Lectures 4-5: PPT  PDF [Sorting: Lower bound, Non-comparison-based, Graphs, BFS]
Lecture    6: PPT  PDF [DFS and applications]
Lecture    7:
PPT  PDF [Dijkstra]
Lecture    8: PPT  PDF [Priority Queues, Bellman Ford]
Lecture    9: PPT  PDF [APSP, Dynamic Programming, LCS]
Lecture   10: PPT  PDF [Euler Tours, Spanning Trees, Kruskal]
Lecture   11: PPT  PDF [Union Find, Prim]
Lecture   12: PPT  PDF [Max Flow Problem]
Lecture   13: PPT  PDF [Matching, Linear Programming]
Lecture   14: PPT  PDF [Linear Programming: Duality, Simplex]
Lecture   15: PPT  PDF [Turing Machines and the class P]
Lecture   16: PPT  PDF [The class NP]
Lecture   17: PPT  PDF [NP-completeness of 3-SAT]
Lecture   18: PPT  PDF [NP-completeness Vertex Cover, Hamiltonian Cycle, Clique, Set Cover,TSP, Subgraph Isomorphism]
Lecture   19: PPT  PDF [NP-completeness Subset Sum,3DM; Computability, Halting Problem, Reductions]
Lecture   20:
PPT  PDF [Decidable, Enumerable, Rice's theorem]
Lecture   21: PPT  PDF [Time-Hierarchy, Overview Space complexity, DFA]
Lecture   22: PPT  PDF [NFA, Communication game for Myhill Nerode]
Lecture   23: PPT  PDF [Equivalence of the game and DFA, Power of 2-way Automata, Size of DFA/NFA]
Lecture   24: PPT  PDF [Minimizing DFA, Regular Expressions]

Homework assignments

Homework can be submitted by e-mail (as PDF files obtained from LaTeX or Word sources), or by pushing a hard copy under my office door (MAS 5-44).

Recommended Literature

Last modified: November 19, 2014