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 Uri Stemmer www.uri.co.il stemmer at cs dot bgu dot ac dot il Building 37, Room 101 Ran Taig www.cs.bgu.ac.il/~taig/ taig at cs dot bgu dot ac dot il Building 37, Room 207

## 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.

You will have a final EXAM, a midterm and 6 homework assignments.
The course grade will be composed of at least 65% final exam, up to 20% midterm and 15% homework assignments.

The weight w of the midterm will decrease the higher the exam grade is, according to the following formula. Let e - final exam grade, m - midterm grade:

if (e > m) then:
if (e-m < 45) then:
w = 20-(e-m)/3
else
w = 5
else
w = 20


Cheating in university courses is regarded as a serious offense. To avoid any possible misunderstanding, please read the following carefully.

Academic dishonesty includes any act of obtaining, soliciting or making available to others, material related to homework assignments. If you commit any of the above, then you are guilty of academic dishonesty. If your partner commits any of the above and you submit the assignment jointly, then you are just as guilty of academic dishonesty. If you choose to work with a partner, then you are both personally responsible for what you submit together. Claiming that you were not aware of the fact that your partner copied the assignment from somebody else will not absolve you of any responsibility.

To eliminate any doubts, we make no distinction between the two (or more) sides of the cheating. If we suspect that Bob and Alice have copied an exercise one from the other, we see no way they could have done this without cooperation. It is your own responsibility to make sure that nobody can copy your assignment.

We will not tolerate academic dishonesty in this course. If you are suspected of academic dishonesty, then a complaint will be filed with the university disciplinary board (ועדת משמעת) and a detailed report placed in your academic records. The minimal penalty for this type of offense is a grade of zero in the course. You might also be expelled from the university.

Be aware that publishing the assignment solution in the internet before the deadline is a serious violation of the academic integrity. Please avoid that.

We reserve the right to check for academic dishonesty anytime after you have submitted an assignment.

# Assignments

You will have 6 homework assignments throughout this semester. You must submit all the assignment, submission is personal.
Please see here the assignments schedule.

You are welcome to discuss the assignments, but you are not allowd to publish your solution in the net, Cheating will not be tolerated - meaning we expect each of you to write the answers in his own words .