Algorithms
Spring 2006

Lecturers:

Prof. Micha Sharir (michas@post.tau.ac.il)

Prof. Amos Fiat (fiat@post.tau.ac.il)

Lectures:

Sunday 12:00-15:00, Holtzblat

Tuesday 16:00-19:00, Dan David 1

Each week one of the lecturers will give both lectures.

Assistants:

Vera Asodi (veraa@post.tau.ac.il)

Thursday 11:00-12:00, Schreiber 6

Thursday 12:00-13:00, Schreiber 6

Thursday 13:00-14:00, Schreiber 6

Amitai Armon (armon@post.tau.ac.il)

Wednesday 16:00-17:00, Shenkar 105

Wednesday 17:00-18:00, Schreiber 7

Messages:

Date	Message
8/3/06	There will be no class next Tuesday (Purim). Instead, there will be a class on Friday, 17/3/06, 9:00-12:00.
12/3/06	The make-up class will take place on Friday, 17/3/06, but the time was changed to 8:00-10:30. It will be in Melamed.
27/3/06	Question 5 in exercise 1 is canceled, since one of the groups hasn’t seen the complete algorithm.
30/3/06	There is a make-up class on Friday, 31/3/06, 08:00-10:30, in Melamed.
23/4/06	There will be a make-up class for Tuesday's group on Friday, 28/4/06, 9:00-12:00, in Melamed.
10/5/06	On Thursday, 11/5, there will be no recitations due to yom hastudent.
4/6/06	There will be a recitation for Thursday’s groups on Friday, 9/6/06, 11:10-12:00 in Melamed.
19/6/06	The exam will contain 6 questions, from which you have to choose 5. You may bring with you one A4 paper, written on both sides. The pseudo codes of the algorithms will be attached to the exam.
22/6/06	There will be a “tirgul hazara” on Tuesday, 27/6, at 14:00 in Lev.

Exercises:

Number	Exercise	Due	Solution
1	ex1	29-30/3/06	sol1
2	ex2	26-27/4/06	sol2
3	ex3	17-18/5/06	sol3
4	ex4	31/5/06	sol4
5	ex5	18/6/06	sol5
6	ex6	Not for submission	sol6

Grades:

Final exam = 90 percent; exercises = 10 percent (magen).

All exercises except for 1 must be submitted.

Moreover, in order to get a passing grade, one must pass the exam.

Textbooks:

· Cormen, Leiserson, Rivest, Introduction to Algorithms, 2nd Edition, 2001

· Translation to Hebrew of this book by the Open University

· Even, Graph Algorithms

· Aho, Hopcroft and Ullman, Data Structures and Algorithms

The syllabus of the course

(1) Introduction:

• Graphs - Basic definitions and properties.
• Data structures for representing graphs.
• Application of graphs.

(2) Euler Graphs:

• Euler cycles; Euler paths.
• Algorithms for constructing Euler cycles and paths.

(3) Scanning Graphs:

• Depth-first search (DFS). The DFS tree (forest) and its properties.
• Applications of DFS:
• In undirected graphs: Finding biconnected components; Finding bridges.
• In directed graphs: Finding strongly connected components.
• Breadth-first search (BFS) and its applications:
• Finding shortest paths.

(4) Minimum Spanning Trees in Weighted Graphs:

• The algorithms of Prim and Kruskal.

(5) Shortest Paths in Weighted Graphs:

• Shortest paths from a given vertex: Bellman-Ford and Dijkstra's algorithms.
• All-pairs shortest paths: Matrix multiplication, Johnson, Floyd-Warshall.

(6) Network Flow:

• Flow networks.
• The Ford-Fulkerson algorithm and the Max Flow - Min Cut theorem.
• The Edmonds-Karp algorithm - using shortest paths.
• Dinic algorithm. 0-1 flows.
• Maximum number of edge-disjoint and vertex-disjoint paths.
• Edge connectivity and vertex connectivity.
• Maximal matching in bipartite graphs. Hall’s theorem.

(7) Classes of Algorithms:

• Greedy algorithms.
• Dynamic programming.

(8) String Matching:

• The string matching problem.
• The naive algorithm.
• The K.M.P. algorithm.

(9) Additional Topics in Algorithms:

• To be announced later