Algorithms - 2007/A

 

Lecturer:

 

Prof. Uri Zwick (zwick@post.tau.ac.il)

 

Lectures:

Tuesday 15:00-18:00, Dan David 1

 

Assistants:

 

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

Thursday 12:00-13:00, Schreiber 7

Office hour: Wednesday 15:00-16:00, Schreiber Open-space

 

Svetlana Olonetsky (olonetsk@post.tau.ac.il)

Thursday 14:00-15:00, Schreiber 7

Thursday 15:00-16:00, Shenkar(physics) 222

Office hour: Thursday 12:00-13:00, Schreiber Open-space

 

 

Messages:

 

Date

Message

31/1/07

Homer-Ezer: I want to make sure you know that you can bring one A4 page to the exam (written on both sides). No other homer-ezer will be supplied with the exam.
Good luck!

29/1/07

Returned Ex.5: The grader updated me that the returned exercises will be in Schreiber 114 by 14:00 tomorrow (Tuesday).

28/1/07

Shiur-Hazara: Recall that the lecturer will deliver it this Tuesday, 30/1, 14:00-16:00, at Dan-David 001 (the usual room).

28/1/07

Regarding old exams: The recommended way of studying for the exam is to repeat all the course material (you don't have to solve old exams). If you do look at old exams, note that they may contain topics which are not in the syllabus anymore or were not covered this semester (such as NP-hardness, pattern-searching and KMP, approximation-algorithms).

28/1/07

Feedback: Those of you who attended the lectures/tirgulim are encouraged to give us feedback by filling the seker-horaa (note that the system only enables filling it until the day before the exam).

25/1/07

Exercises: If you submit Ex.6 on Sunday (28/1), please put it in the mailbox of your metargel/et. Ex.5 will be returned next week (an announcement will be published at the website after it is returned).

25/1/07

Extended office-hour of Amitai: Next Wednesday, 31/1, 15:00-18:00, at the Schriber open-space (as announced in the tirgul).

22/1/07

Ex.6 - question 5: Just to clarify that items' weights and profits are positive number.

16/1/07

Please note that we published Ex.6 - the last exercise for this semester (you should also receive a notice about it by email). The first question is still related to flow, and questions 2-5 are related to dynamic-programing. It may be good to wait with question 5 until after the tirgul this Thursday.
As usual, feel free to contact us about any questions/problems. Good luck!

7/1/07

For all the groups, an elaborate explanation of the last exercise of the last tirgul can also be found here.

26/12/06

Exercise 4, question 3: Assume that the capacities and m are integers.

20/12/06

Strike update: Due to the students and staff strike, Amitai's group will NOT have a Tirgul tomorrow. Instead, there will be Tirgul this Friday, 22/12, at 13:00, in Schreiber 6 (as was announced via email to those listed in the group).

3/12/06

Amitai's office-hour this week will be on Thursday, 13:30-14:30 (shortly after the tirgul), and not on Wednesday.

28/11/06

Following questions of several students, I would like to clarify that the tirgulim this week will take place as usual. The planned strike was canceled by Agudat-Hastudentim and the academic staff (even if there is a demonstration, they are not going to make a strike).

30/10/06

Recall that Amitai's class this week will take place on Friday , on 11-12, at Schreiber 8 (this is due to the memorial ceremony for Yitzhak Rabin on Thursday).

22/10/06

Good luck!



Exercises:

 

Number

Exercise

Due

Solution

1

Ex1

16/11

Sol1

2

Ex2

30/11

Sol2

3

Ex3

14/12

Sol3

4

Ex4

28/12

Sol4

5

Ex5

11/1

Sol5

6

Ex6

28/1

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, Stein, 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