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
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
- There will be no lecture on Tuesday, August 19.
Midterm will be on October 10, 9:30am in Executive Classroom 1,
MAS-03-06. The duration will be 90 minutes and the exam will consist of
3 problems. The relevant material is from lectures 1-12. You are
allowed to bring a two-sided sheet of paper with handwritten notes.
- The Final will be on November 25, 1:30pm.
- Part II of the course (Complexity, Computability, Automata) starts on October 14.
- The final exam for students using the Pass/Fail option will take place on Nov. 25, 1:30-4:30 in Executive Classroom 2, MAS-03-07.
- For the final exam you may bring a single two-sided handwritten sheet with any notes.
Lecture 1: PPT PDF [Introduction]
- The course will give a introduction to algorithms, as well as the
topics of NP-completeness, computability, automata theory, and circuit
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 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).
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms. MIT Press
- Arora, Barak. Computational Complexity: A Modern Approach. Cambridge University Press
Last modified: November 19, 2014