• Main

Contents (show)

Contents (hide)   1 Syllabus   2 Text Books   3 Grade Calculation   4 Academic Integrity   5 Appeals

Welcome to Design of Algorithms homepage

The site is dedicated to Design of Algorirthms, 2009 course. Be sure to read the General information page.

Syllabus

• Reductions.
• Greedy algorithms.
• 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 and assignment problems.
• Randomized algorithms. String matching.
• Introduction to complexity theory: complexity classes, Cook-Levin theorem, techniques for proving NP-completeness.

Text Books

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

Grade Calculation

The course grade will be composed of 65% final exam, 20% midterm and 15% homework assignments, provided the weighted average of the final exam and the midterm is at least 56. Otherwise the weighted average will be your course grade.

The weight of the midterm will decrease the higher the exam grade is, according to the following formula, let e - final exam grade, m - midterm grade, h - average homework grade, c - combined final exam and midterm grades and f - final course grade.

Here is the computation of f and c:

if (e > m) then:
    if (e-m < 45) then:
        w = 20-(e-m)/3
    else
        w = 5
else
    w = 20
c = ((85-w)*e + w*m)/85
if (c &ge 56) then:
    f = 0.85*c+0.15*h
else
    f = c

Academic Integrity

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.

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

Appeals

Some things you ought to know before you submit an ir'ur(appeal). Note that the grade can also be decreased. If you decide to proceed, you should do it through the department's secretariat.

Ir'ur (Appeal)

An ir'ur is justified only if you feel that we misunderstood your answer. Since we try to grade the questions in a similar way for all the students do not lodge a request if your only complaint is that too many points were deducted.

When lodging a request for an ir'ur, you have to:

1. Tell us exactly where, and in what, you feel we did not understand your thinking. A request saying " I deserve more for my answer", or "Please recheck question 1" will be returned to its sender.
2. Explain the correctness of your solution as a whole, and not only the problematic sentence. That is, you have to write a full answer and show that what you wrote in the exam matches your solution.

We ask you not to bother us with an ir'ur if the expected grade change is at most 3 points (a change of at most 0.6 in the course grade). Note that we may recheck any other part of the midterm as well, and that your grade can decrease as a result of a recheck request.