Algorithms (0368.2160) – 2008/2009a

 

Lecturer:

 

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

 

Assistant:

Danny Feldman (dannyf@post.tau.ac.il)

 

Messages:

 

Date

Message

21/2/09

In the last recitation I solved exercises from http://www.cs.tau.ac.il/students/summaries/efficiency/?C=M;O=D

2/11/08

Welcome to Algorithms course

2/12/08

Ok, ok, Ex2 is due to 11/12/08

2/1/09

Useful links added below



Exercises:

 

Number

Exercise

Due

Solution

1

ex1.doc

27/11/08

 

2

ex2.doc

11/12/08

 

3

ex3.doc

25/12/08

 

4

ex4.doc

15/1/09

 

5 – part 1

ex5.doc

29/1/09

 

 

Procedural Matters:

Prerequisite Courses: Data Structures, Linear Algebra, Calculus, Discrete Mathematics. Exercises will be given in the recitations, and their solutions will be graded. These will form about 10% of the final grade . The rest of the final grade will be determined by the final exam.

Text books:

Introduction to Algorithms, by T. Cormen, C. Leiserson and R. Rivest. MIT Press, 1990.
Algorithm Design, by J. Kleinberg and E. Tardos. Pearson/Addison Wesley, 2006.
Most of the course follows the above two books.
Graph Algorithms, by S. Even. Computer Science Press, 1979.
Data Structures and Network Algorithms, by R. E. Tarjan. SIAM, 1983.

The Design and Analysis of Algorithms, by D. Kozen, 1992.

Course syllabus:

Graph Algorithms: Breadth first search, Depth first search, Topological sort, Strongly connected components, Biconnected components, Minimum spanning trees (Kruskal, Prim), Shortest paths (Dijkstra, Bellman-Ford), All-pairs shortest paths (Floyd-Warshall, Johnson), Dynamic Programming, Flow algorithms (Ford-Fulkerson, Edmonds-Karp, Dinic). String matching: Finite automata, KMP. Probabilistic Algorithms.

Course Outline (to be updated during the term):

  1. Introduction and notation, representation of graphs, BFS
  2. DFS
  3. Applications of DFS: topological sort, strongly connected components.
  4. Minimum Spanning Trees, Kruskal's Algorithm, Prim's Algorithm
  5. Shortest paths.
  6. More on shortest paths. Dijkstra's Algorithm. The algorithm of Bellman and Ford.
  7. All pairs shortest paths. The algorithm of Floyd and Warshall, Johnson's Algorithm.
  8. Dynamic Programming.
  9. Network flows, the Max-flow Min-cut Theorem, Ford and Fulkerson's algorithm.
  10. The algorithm of Edmonds and Karp, Dinic' algorithm, 0/1 networks.
  11. String matching

Useful Links

Shlomi Rubinstein (also contain exercises from last recitations)

http://ranger.uta.edu/~gdas/Courses/Fall2004/advAlgos/student_slides/W7Presentation.ppt

http://www.math.unipd.it/~kvenable/algo2_2008/Grafi8.ppt#2

http://httpdyn.cs.huji.ac.il/moodles/cs08/file.php/67504/sol05.pdf

formulas.doc

spamfilter.pdf

notebook.pdf

u.multinet.co.il

informal materia for Lecture 1   2  3 4 5 6 7  8.