Contents (hide)

# Welcome to Design of Algorithms homepage

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 class schedule and staff information is found on the course info page. The practical sessions are based on the lecture. You should be in at least one lecture before the practical session (every week).

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

# Syllabus

• Reductions.
• Greedy algorithms.
• Minimum spanning trees.
• Dynamic programming.
• 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.

PDF

The course coordinator is Prof. Amos Beimel, his office hours can be found on the Course Info page.

# Text Books

1. 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.
2. J. Kleinberg and E. Tardos, Algorithm Design.

• 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.
• If your exam grade is at least 56 and your homework assignment grade is at least 56, but your exam+midterm component is below 56, your final grade will be exactly 56. This will not allow a low midterm grade to result in a failing final grade for students with a passing test and HW scores.

Formally, let e = final exam grade, m = midterm grade, h = average homework grade, and f = final course grade. The final course grade is computed as follows:

if ( (0.65e + 0.2m)/0.85 >= 56 ) then
f = 0.65e + 0.2m + 0.15h
else
if ( (e >= 56) and (h >= 56) ) then
f = 56
else
f = (0.65e + 0.2m)/0.85


Please note that according to the university Exam Procedures a student qualifies for a special testing date only in very specific situations. Also note that a student that will be absent from the Midterm or exams due to any other reason will be graded zero. Doctor approval will not be accepted. If you have a problem, send a email or talk with one of the TA or lectures BEFORE the exam / Midterm and we will find a solution.

Important dates
• Midterm 20/5
• Moed A 20/7
• Moed B 8/8

Good luck!

# Assignments

You will have 6 homework assignments throughout this semester. We encourage you to submit in pairs for three reasons:

1. It is easier.
2. Nothing compares to midnight debates about a spanning tree.

Each assignment will be partially graded. That is, we will arbitrarily choose some questions for checking.

• Questions we do not check will receive full grade if there was some effort to solve it.
Providing a nice recipe for a cheese cake does not count for an effort.
• Questions we do check, will be graded with full strictness - be aware!

Naturally, you will not know which questions are checked, otherwise it wouldn't be fun… The assignments page will provide you with submission details and everything else relevant on the matter.

The final assignment grade will be made off 5 out of 6 best assignments. The drawback is that we are going to be much stricter with delay requests. We already published the deadline for all assignment and you should plan your schedule carefully.

Any requests such as " Hi, I have a midterm / exam / big assignment in different course / need more time for the assignment" will be automatically rejected.

You are welcome to orally discuss the assignments, but you are not allowed read solutions of other students or to publish your solution in the net. Cheating will not be tolerate.

As completing the assignments is the best way to practice and understand the course material, assignment exemptions will only be granted due to the circumstances detailed in university regulations (reserve duty, hospitalization etc.). This includes students repeating the course which are required to complete all assignments, no exceptions.

## Assignment appeals

You will be able to submit assignment appeals, under the following conditions:
• You may submit assignment appeals at most ONE WEEK following the announcement of grades in the course announcements page.
• Appeals will only be considered if your work has been properly submitted to the submission system.
• Appeals must be submitted to the mailbox of the TA in charge.
• Appeals will be considered only if you believe 10 points or more have been incorrectly reduced.
• Appeals for handwritten submissions will not be considered.
• Appeals will be checked thoroughly and may result in a reduction to your grade.

In order to appeal, attach a page clearly describing the mistakes you believe have been made to your graded assignment, and submit it to the mailbox of the TA in charge of your assignment. TA mailboxes are on floor 1, adjacent to the department head's office.

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.

In case that you are quoting an external resource (such as books, internet etc.) you must follow the university Quoting Rules. You cannot use a reference without appropriate citation.

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. Be aware that publishing the assignment solution in the internet before the deadline is a serious violation of the academic integrity. Please avoid that.

In the previous course some students broke the academic integrity rules in their assignments. They were punished by the university disciplinary board!

# 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 university's appeal system.

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

# If you have a question or request…

Usually students have questions. We will try to provide you with as much information as possible through this site, but sometimes if will not be enough. Before asking us try to search for an answer on the site and read the FAQ page. You can also use the search box at the upper right.

We will make an effort to provide each assignment with a forum for your questions. In addition you can contact the relevant staff member by e-mail (see course info for details).

Administrative questions/requests (sickness, delays, anything else…) MUST be sent to algo162@cs.bgu.ac.il.