Contents (hide)

Welcome to Design of Algorithms for IAF homepage

Introduction

This course is all about algorithms and this site is all about helping you to succeed in this course. It will be our main information channel so be sure to come back often (you can see the last updated pages by using the recent changes link on the left side tab.

The course syllabus and rules are all combined on the main page. Pay special attention to the academic integrity section.

Finally, make yourself a habit to check the announcements page for important messages.

Instructors

Full name Web page E-mail Office
Ran Taig www.cs.bgu.ac.il/~taig/ taig at cs dot bgu dot ac dot il Building 37, Room 207
Uri Stemmer www.uri.co.il stemmer at cs dot bgu dot ac dot il Building 37, Room 101

Syllabus

Reductions. Greedy algorithms.
Loop invariants and correctness proofs.
Dynamic programming.
Minimum spanning trees. Cuts.
Shortest paths algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall.
Depth First Search (DFS), strongly connected components, topological sort.
Maximum flow algorithms of Ford-Fulkerson, Dinitz. Applications to matching.
Introduction to complexity theory: complexity classes, Cook-Levin theorem, techniques for proving NP-completeness.
Randomized algorithms (if there will be enough time).

Text Books

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 2nd edition. An online student source is available at CLRS for students. A Hebrew version exists as well.
J. Kleinberg and E. Tardos, Algorithm Design.