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.
Schedule
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
Announcements
- There will be no lecture on Monday, August 12 (Public Holiday).
- There will be no tutorial on Monday, August 19, but instead a 2 hour lecture.
- The CA component will consist of a midterm test, and 4 homework problem sets, which are graded.
- The midterm exam is confirmed for Monday Oct. 7, 10:30 in MAS EC1 (on level 3 in SPMS).
- The course will give a introduction to algorithms, as well as the
topics of NP-completeness, computability, automata theory, and circuit
complexity.
Lectures
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: PDF [BFS and DFS]
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)]
Tutorials
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
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms. MIT Press
- Sipser: Introduction to the Theory of Computation
- Arora, Barak: Computational Complexity: A Modern Approach. Cambridge University Press
Last modified: November 11, 2019