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
Sipser.
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.
Schedule
Tue 9.3011:30 (L), SPMSTR+17
Fri 9:3010:30 (L), SPMSTR+17
Fri 10:3011:30 (T), SPMSTR+17
Announcements

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).

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
Homework can be submitted by email (as PDF files obtained from LaTeX or Word sources),
or by pushing a hard copy under my office door (MAS 544).
Last modified: Nov 15, 2013