- Uri - 11.09, 14:00-16:00
- Amos - 12.09, 14:00-16:00
- Yair - 12.09, 14:00-16:00
- Michal - 12.09, 18:15-20:00
- Ran - 13.09, 10:00 - 11:30 (updated)

Yefim

אני מתנצל על הטעות

עמוס

Yefim - Today (Thursday) 18:00 - 19:30

Uri - Sunday - 11:30 - 13:30

Amos - Sunday - 14:00 - 16:00

Rotem - Sunday - 14:00 - 16:00

Yefim

Alex.

I wish you all good luck!

Michal

Good Luck!

Ilan

טופס הבחינה והפתרון נמצאים ב- Exams.

My e-mail availability on the coming month will be very limited.

Good Luck to you all!

Ran

In case you had a ptor (800) to one of the assignment, the grade is the average of the best 4 out of 5.

Any problems, remarks, wonders, doubts etc MUST be sent to algobgu@gmail.com before the next Monday.

Good luck in the exam

Yair

Grades are published in the submission system.

Please note that only questions 1 and 3 were graded for correctness.

The graders would like to emphasize that many students did not fully understood the requirements from a verification algorithm - i.e (for all… and there exist…) - Please repeat this material before the exam.

Also - Recall that reduction is a transitive relation. If it's given that a language L is NP-HARD, and you PROVE: L <=_p L' , no need to show anything else in order to prove that L' is NP-HARD.

- Alex - Sunday, 15.07.12 , 16:00-18:00
- Michal - Monday, 16.07.12 , 10:00-12:00
- Amos - Monday, 16.07.12 , 14:00-16:00
- Ran - Monday, 16.07.12 , 15:00-18:00
- Rotem - Tuesday, 17.07.12 , 13:00-16:00
- Yair - Tuesday, 17.07.12 , 13:00-15:00
- Ilan - Tuesday, 17.07.12 , 16:00-18:00

Good luck!

Assignment 6 grades should be published on Sunday.

Note that ALL the solutions for the assignments are published.

**instead**of my regular Thursday office hours.

Ran

If any of you wish to meet me for office hours, please schedule a time by email. I'll be more than happy to help you prepare for the exam. Good luck!

In two weeks (18/7/12) we will hold Moed A. We would like to emphasize the fact that **the exam will cover ALL* the material in the course,
including, of course, the subjects covered in the beginning of the course (midterm material).**

**Please**arrive to the exam prepared.

We wish you the best of luck!

* = The proof of Cook-Levin Theorem and the approximation algorithms that you saw in the last lecture are not included in the exam.

**Tuesday**June 26 will be in Building 26 room 6 (in the usual time 10-12).

Amos's reception hours on Monday June 25 are canceled.

Alex.

The answer sheet will be published later.

Please note that the deadline is next Thursday and not Sunday as usual.

Good Luck!

**19/6 13:45: We published the wrong reduction. Please read the correct file. **

if you want to come in different hours on Mon or Wed, PLEASE SEND AN EMAIL FIRST.

Yefim

Make sure you have enough time to solve it.

The answer sheet had been published.

Tomorrow PS between 18:00-20:00 is canceled.

Yair office hours are canceled tomorrow.

Make sure you download the updated version!

The answer sheet will be published soon.

Good luck.

class:

**34/107**.

Please come after:

- Make sure that you really have a problem
- If you have the assignment, bring it with you.
- If not, make sure that it is not in the returning area.

Here is an auxiliary text containing the proof that in algorithm Dinitz, the length of the layered network strictly increases from a phase to the next one. Proof_of_algorithm_Dinitz.pdf

Enjoy

Here are two examples of Dinitz Algorithm from my class.

Since this week PS is a little bit complicated, Yair will have the same PS again next week, on Wed 18-20.

So you have two options - tomorrow and next Wed 18-20.

HAVE FUN!

English speakers are considered to be more polite than us, the Israeli guys. Actually, most of the nations of the world are considered to be more polite than us. When one says in English "please submit your assignment in the submission system", he actually means

ובכלל התרגום של

Grades will be published later (probably next week).

Please note that for questions 1-2 and 4 you got 15 points if you did something and 0 if not - correctness was checked only in q. 3.

**Please note:**If you got
הערה 1
It means you didn't justify your formula by explaining that the sub problems are disjoint.
If you got
הערה 2/3
It means your algorithm has a problem with the order of solving sub problems. You didn't solve all needed sub-problems (for example leafs) before solving the current problem.
There are a few Assignments without a name - contact Ran if you think they belong to you.

The tirgul on Sunday is canceled.

If you do not have a grade for ass1 and ass2 - __ we have a problem__.

The most common reason is that you did not open a group at the submission system, but there are more reasons - you did not write a name, a dog ate the assignment and many more.

Please come to Yair today at 13:00 or 15:00, or after the midterm and we try to solve the problem….

Remember: no grade == zero.

**18.05.12**at

**09:00**in the morning and will be

**2.5**hours long.

Please note the time!

**32/108**.

Ran

- Alex Lan Mon 12:00-14:00
- Michal Shemesh Monday, 12:00-14:00
**and Thursday, 11:00-13:00.** - Amos Beimel Monday 14-16
- Yefim Dinitz Monday 12-14,
- Ran Taig Wednesday 10:00-12:00
**and Thursday, 10:00-11:00. (Ran's second office hour is canceled this week)**. - Uri Stemmer Wednesday 12:00-14:00
- Yair Adato Wednesday 13:00-14:00, 15:00-16:00.
- Yefim Dinitz Thursday 17.30-19.

Michal

Group 42, Tue 12-14 by Rotem is canceled next week.

Uri will replace Rotem in his PS on Sunday 18-20.

You can also have extra practice using our amazing quizzes.

**tomorrow, Thursday, 10.05.12, 11:50 (and not a minute later…)**

I wish you a nice "second half of the semester" with Ilan!

Sorry for any confusion that might occurred.

**Please note that although the deadline was postponed the assignment requires work, We strongly recommend not to begin at the weekend**

צלמו את התרגיל לפני ההגשה כיוון שלא בטוח שנספיק לבדוק את התרגיל לפני הבוחן (למרות שנשתדל).

אנו מודעים לעומס הלימודים שיש לכם כרגע. למרות זאת אנו ממליצים בחום לפתור את התרגיל ברצינות כהכנה לבוחן.

Alex.

1) It turned out that we studied approximately the same material as the other classes. So, no need of an additional meeting on cheapest paths, in the meanwhile.

As was set, I add on LCS during my reception hours, from 12.10 and on on Monday, April 30, room 203/37.

2) The missed simple proof (eq denotes = , sorry):

Statement: If Relax could update at no edge (that is, for any edge (u,v) holds d(v) eq< d(u)+w(u,v)), then for any vertex v holds d(v)=delta(s,v).

Proof by contradiction: Assume to the contrary that delta(v) < d(v), for some v. That is, there exists a path P from s to v, such that w(P) < d(v). Let us denote the prefix of P from s to any u by P_u. Let us take the first edge (x,y) on P such that w(P_x) eq> d(x), while w(P_y) < d(y) (recall that w(P_s) eq d(s) eq 0 ). Then:

d(y) > w(P_y) = w(P_x) + w(x,y) eq> d(x) + w(x,y).

That is, Relax(x,y,w) could update d(y) via edge (x,y), a contradiction to the asssumption.

Note the answer sheet will be published on Sunday.

- 16:00 - 18:00 28 / 104
- 18:00 - 20:00 34 / 007

ההרצאות בין 10-11 יתקיימו בחדרים הרגילים

ההרצאה של מיכל ב-12:10 תתקיים בחדר 34/102

ההרצאה של עמוס ב- 12:10 תתקיים בחדר 97/202

**שימו לב כי הודעה זו מעדכנת את ההודעות הקודמות**

lectures:

- The lectures on tuesday between 09:45-11:00 are canceled (memorial ceremony).
- Michal Shemesh's group will have an extra hour on 24/4, 12:00-13:00 on 34/102.
- Prof. Beimel group will have an extra hour on 24/4, 12:00-13:00 on 97/202.

Practical sessions:

- All the PS on wednesday and thursday are canceled.
- Ran's PS on tuesday 24/4 will start on 9:00 (sharp)
**241/90**. - Yair will have a PS on Monday 18:00-20:00
**205/34**. - Ran will have 2 PS on sunday 29/4 at 16:00-18:00 and 18:00-20:00. Please note that Ran's PS are a week after the independence day.

We apologize for that.

The group will be given by Uri Stemmer on Mondays, 18:00-20:00, at bld. 34 room 16.

**at noon**. This means the middle of the day when the sun is exactly above our heads.

**Ran's regular practical session on Tuesday, 10-12, is canceled this week. **

Yair will have a complementary practical session on Tuesday at 18:00-20:00 in Building 28 Room 201.

All students are requested to go to practical sessions on Sunday through Tuesday.

~dinitz/Course/Algs-10/10-W_B

**The lecture on Tuesday, 20.3.12, 10:00-12:00, for group 4 will be held in**.

__classroom 26/6__1. הרצאה לקבוצה 1 ביום ראשון ה-18.3.12 בשעות 13:00-15:00 מבוטלת בשל קרנבל פורים. הרצאת השלמה לקבוצה זו תתקיים באותו היום, בכיתה 32/308 בשעות 18:00-20:00.

סטודנטים יקרים, אנא הקפידו להגיע לקבוצת ההרצאה אליה אתם רשומים.

2. שינוי קבוע בכיתת לימוד לקבוצת הרצאה 2, השיעור בימי ראשון בשעות 16:00-18:00 עובר לכיתה 72/210.

3. ההרצאה לקבוצה 2, ביום ג' ה- 20.3.12 בשעות 10:00-12:00 תיערך באופן קבוע בכיתה 26/6.

In any case (even if the strike will be over) there'll be NO tirgoolim in the course on Wednesday and Thursday, 14-15/03/2012.

We'll start the course as usual beginning on Sunday, 18.03.2012.

Please make sure you check this announcements page regularly (and especially before the beginning of next week) to see on any changes in the schedule or other important course issues, No e-mails will be sent.

Good Luck in the Semester.

`algobgu@gmail.com`

If you have a representative Vaad, please contact Yair Adato.

Note that the practical sessions are based on the first lecture of the week. You should attend at least one lecture before the weekly practical session. Therefore, the first week practical session on Sunday 18-20 is canceled. Please go to other session groups.