Algorithms (Efficiency of Computation) - 0368.2160

Yossi Azar ( azar@tau.ac.il )
1st Semester, 2005/6 - Tuesday 15-18, Handasat Tochna 102
School of Computer Science,
Tel-Aviv University

This page will be modified during the course, and will outline the classes

Grade:

10% Exercises
90% Final Exam

PAGE FOR THE EXAM:

Page for the Exam

Exercises:

Exercise 1
Exercise 2
Exercise 3
Exercise 4
Exercise 5
Exercise 6

Solutions:

Solutions 1
Solutions 2
Solutions 3
Solutions 4
Solutions 5
Solutions 6

Text books:

Introduction to Algorithms, by T. Cormen, C. Leiserson and R. Rivest. MIT Press, 1990 (CLR).
Most of the course follows the above book.
Graph Algorithms, by S. Even. Computer Science Press, 1979.
Data Structures and Network Algorithms by R. E. Tarjan. SIAM, 1983.

Course syllabus:

Greedy algorithms and Dynamic Programming. Graph Algorithms: Breadth first search, Depth first search, Topological sort, Strongly connected components, Biconnected components, Minimum spanning trees (Kruskal, Prim), Shortest path (Dijkstra, Bellman-Ford), All-pairs shortest path (Floyd-Warshall, Johnson), Flow algorithms (Ford-Fulkerson, Edmonds-Karp, Dinic). String matching: KMP. Introduction to Linear Programming. Randomized and Approximation Algorithms

Notes

Here is a link to course notes written by the student Assaf Shtilman.
The notes are NOT offical, were NOT checked by me in any way and may contain errors.
Link to Notes

Course outline

Session numbers referred to the CLR book (first edition). Newer editions may have different chapter numbers.
  1. Nov 1 :
    Introduction
    Dynamic Programming (16)
    Ex. Nov 3
    Greedy algorithms (17) Dynamic Programming (16)
  2. Nov 8 :
    Dynamic Programming (16)
    Representations of graphs (23.1)
    Breadth first search (23.2)
    Ex. Nov 10
    Euler cycle and path
  3. Nov 15 :
    Breadth first search (23.2)
    Depth first search (23.3)
    BFS and DFS for undirected graphs
    Ex. Nov 17
    BFS applications (23)
  4. Nov 22 :
    Topological sort and DAGS (23.4)
    Strongly connected components (23.5)
    Ex. Nov 24
    Bridges and articulation points (23) Strongly connected components (23)
  5. Nov 29 :
    Minimum spanning trees (Kruskal, Prim) (24)
    Ex. Dec 1
    Minimum spanning trees (24)
  6. Dec 6 :
    Shortest paths - general (25.1)
    Shortest paths - Dijkstra (25.2)
    Ex. Dec 8
    DAG shortest paths (25) Dijkstra (25)
  7. Dec 13 :
    Shortest paths - Bellman-Ford (25.3)
    All pairs shortest paths (26.1)
    Ex. Dec 15
    Bellman-Ford applications (26)
  8. Dec 20 :
    Floyd-Warshall (26.2)
    Transitive closure (26.2)
    Johnson algorithm (26.3)
    Ex. Dec 22
    All pairs shortest paths (26)
  9. Dec 27 :
    Max Flow (27.1)
    Ford-Fulkerson (27.2)
    Ex. Dec 29
    Max Flow (27)
  10. Jan 3 :
    Ford-Fulkerson (27.2)
    Edmonds-Karp (27.2)
    Dinics (Even's book)
    Ex. Jan 5
    Bipartite matching (27) Hall's theorem k-connectivity
  11. Jan 10 :
    0-1 flow and matching (27.3)
    String matching (34)
    Ex. Jan 12
    Flow
  12. Jan 17 :
    String matching (34)
    Intorduction to Linear Programming
    Ex. Jan 19
    String matching (34)
  13. Jan 24 :
    Intorduction to Linear Programming
    Approximation algorithms - Vertex cover
    Ex. Jan 26
    Linear Programming
  14. Jan 31 :
    Randomized algorithms, Approximation algorithms
    Ex. Feb 2
    Randomized and Approximation Algorithms
Last updated January 29, 2006