MAS 714: Algorithms and Theory of Computing
The class consists of two parts: complexity and algorithms.
The first part (complexity, 6 weeks) is based on the book Introduction to the Theory of Computation by
The instructor for this part of the course is Asst. Prof. Edith Elkind. See here for information pertaining to this part of the course.
The second part on algorithms will start Friday. Sept. 27. The instructor for this part is Asst. Prof. Hartmut Klauck.
Tue 9.30-11:30 (L), SPMS-TR+17
Fri 9:30-10:30 (L), SPMS-TR+17
Fri 10:30-11:30 (T), SPMS-TR+17
There will be a lecture on Friday, Sept. 27. There will be no lecture on October 15.
- Recommended book: Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (any edition).
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).
Lecture 1: Introduction/Sorting
- Lecture 2: Sorting
- Lecture 3: Sorting in linear time, Graphs
- Lecture 4: BFS
- Lecture 5: DFS+applications, Shortest Paths
- Lecture 6: Dijkstra and Priority Queues
- Lecture 7: Heaps, Bellman Ford, Floyd Warshall
- Lecture 8: Dynamic Programming
- Lecture 9: All pairs distances via Matrix Multiplication, Spanning Trees, Union Find
- Lecture 10: Prim's algorithm, Euler tours, Flow Networks
- Lecture 11: Ford Fulkerson, MaxFlow MinCut Theorem
- Lecture 12: Ford Fulkerson Running Time, Matching
Last modified: Nov 15, 2013