# Announcements

Boaz Arad, TUE 18.11 0800-1000

Yehonatan Cohen, WED 19.11 1400-1600

Ohad Ben Baruch, MON 17.11 1000-1200

Gal Amram, WED 19.11 1000-1200

Yefim Dinitz WED 19.11 17.15-18.00

**a second time**, attended

**Moed B2**and received a final grade of

**55**are kindly requested to contact the course mailbox.

A 12 point bonus to the grade of Moed B2 was granted to all students who took it, the grades in the submission system include this correction, fractional grades were rounded up.

Final Grade Distribution

(zero grades are non-attendance)

* students who received test exceptions due to extended reserve duty (and only them), may contact the course e-mail in case of grade errors.

Pay attention to the two following points relevant to the correctness proof of the structural formula at the dynamic programming approach:

1) The structural formula and its correctness are fully MATHEMATICAL issues, with no relation to algorithms and programming. Simply one value EQUALS a formula on other values, and this needs a proof.

2) You should use explicitly the fact that a part of an optimal solution is itself an optimal solution to a sub-problem, and its value is denoted by opt(…).

Yefim

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

בנוסף, יש מספר אקספוננציאלי של אפשרויות להמשיך אחרי התזוזה ימינה או למטה. והיה צריך לציין שבפתרון אופטימאלי גם ההמשך חייב להיות אופטימלי, ושהאופטימום הזה מסומן ב opt המתאים.

מועדים לשמחה, אורי

Yefim Dinitz: 16-17.30 on Monday, October 13

Gal Amram: 14-16 on Sunday, October 12

**final course grades**, test grades and assignment component grades are visible in the "grader notes" section. Appeals to these grades should be submitted only via the test appeal system* - you may only appeal an incorrect test grade, or incorrect calculation of your final grade based your "Final Assignment Grade" as it appears in the submission system. Assignment grade appeals are no longer accepted.

As per the "Zuk-Eitan" special consideration policy, your final grade is based on the best of your exam grades.

Students who received a grade between 52 and 55 (inclusive) on their exam were granted a passing test grade of 56, fractional grades were rounded up.

Final Grade Distribution

(zero grades are non-attendance)

* students who received test exceptions due to extended reserve duty (and only them), may contact the course e-mail in case of grade errors.

Once exams will be scanned, if you submit an appeal, make sure you read them very carefully.

Good Luck!

**you must pass the test in order to pass the course**. If your test grade is under 56, your test grade will be your final grade.

**Appeals**

Any appeals to your test/final grade should be submitted only to through the regular **test appeal system**, this includes errors in grade calculation. Once your scanned test notebooks are available you will have three days to submit your appeals, please be sure to submit them on time as extensions will not be granted (excluding those mandated by university regulations).

While university regulations prevent course staff from discussing your appeals before they are submitted, the test questionnaire and an example solution will be available in the Exams section shortly.

Ran Taig 10.9 (Wed) 09.30-11.30 **Mainly for questions on the first half of the course**

Boaz Arad 10.9 (Wed) 11:30-13:30

Michael Elkin 11.9 (Thu) 10.00-12.00

Ohad Ben Baruch 11.9 (Thu) 12.00-14.00

Eden Chlamtac 11.9 (Thu) 14.00-16.00

Yefim Dinitz 11.9 (Thu) 16.00-17.30

Michal Shemesh 14.9 (Sun)**14:00-16:00**

Yehonatan Cohen 14.9 (Sun)**16:00-18:00**

**very long**terms of reserve duty. Students who have served such terms of reserve duty should contact

**Prof. Avraham Feintuch**from the department of mathematics in order to be considered.

Students who are found eligible for special consideration will receive a final grade equal to their assignment grade. If such students have attended the midterm AND their midterm grade is greater than their assignment grade, their final grade will be comprised of 70% - midterm grade, 30% assignment grade (The midterm is a "magen").

Update: Please **do not** contact Prof. Feintuch requesting an exemption unless you have served a long period of reserve duty. Also, any requests to "vaadat horaa" should be made through the students office in the standard procedure for all requests, please do not contact the committee chair via e-mail or in person, as he will be unable to assist you without a formally submitted request.

Statement: The length of the layered network strictly increases from phase to phase.

Proof: Consider some phase (henceforth called "current phase"). At its beginning, we built a layered network L_f of length l in the residual network N_f. The stopping condition of the phase is that there is no path from s to t in the updated layered network. Denote by f' the flow when the current phase stops. In order to prove the statement, it is sufficient to show that the residual network N_f' contains no path from s to t of length at most l. Let us prove that.

Notation: For any vertex v, we denote by d0(v) the layer number of v in L_f. (Important: Since layers are never changed during the phase, also d0(v) is fixed during the phase!) We say formally that an edge (u,v) "increases d0" by d0(v) - d0(u). We call (u,v) a jumping edge if it increases d0 by at least 2 (that is if d0(v) >= d0(u) + 2).

First of all, let us investigate the residual network N_f' (with no relation to paths in it).

Lemma 1: There is no jumping edge in residual network N_f'.

Proof. In N_f', there are old edges, inherited from N_f, and new edges, added during the phase. There is no jumping edge in N_f, by the property of BFS. Pay attention that any new edge (v,u) added to the residual network after some iteration is opposite to an edge (u,v) of the augmenting path of that iteration. Since (u,v) increases d0 by 1 (by the algorithm), edge (v,u) decreases d0 by 1. Hence also no new edge in N_f' is a jumping edge.

Now, let us consider an arbitrary path P from s to t in N_f'.

Lemma 2: a) The length of P is at least l. b) The length of P equals l only if P belongs entirely to the layered network L_f.

Proof: Pay attention that all edges of P together increase the layer number from 0 (d0(s)) to l (d0(t)).

a) Assume |P|<l. Since there are less edges than the total increase of d0, there exists an edge in P which increases d0 by at least 2, a contradiction to Lemma 1.

b) Assume |P| equals l. By the same reasons, every edge in P should increase d0 by exactly 1. Indeed, if some edge of P does not increase d0, then the remaining l-1 edges increase d0 together by at least l, and we continue as in item a. Pay attention that edges increasing d0 by 1 are old edges only, since any new edge decreases d0 by 1. By the definition of L_f, this implies that any edge in P is in L_f, as required.

Proof of the main statement: By Lemma 2, the only case of |P| =< l is when P is included in L_f. Since P is a path in N_f', all edges of P are not saturated by f', by the definition of N_f'. In other words, the updated layered network L_f still contains a path from s to t, a contradiction to the assumed stopping condition of the current phase.

As long as you receive a passing grade (>56), the exam grade will comprise 70% of your final grade, and your assignment grade will comprise the remaining 30%. In order to avoid unnecessary grade reductions, students that scored higher in the exam than on their assignment grade will receive a final grade based only on their exam grade (the assignments will be a "magen").

So, to reiterate:

If [exam_grade] > 56 [final grade] = max([exam_grade],0.7*[exam_grade]+0.3*[assignment_grade]) Else [final_grade] = [exam grade]

And yes, if it was not *abundantly clear* from the above **you must pass the exam** in order to pass the course.

גל

Yefim Dinitz: Monday 18.8 and Monday 25.8, 16:00-18:00

Uri Stemmer: Wednesday 20.8, 12:00-14:00

Eden Chlamtac: Thursday 21.8, 14:00-16:00

Michael Elkin: Monday 25.8, 10:00-12:00

Michal Shemesh: Monday 25.8, 13:15-15:00

Ran Taig (First part of the course related questions): Monday 25.8, 08:45-10:30

Check back here for updates, and good luck!

לאלו מביניכם שאינם יכולים להגיע ביום חמישי - אתם מוזמנים לפנות אלי ביום רביעי (20.8) במייל או בטלפון בין השעות 16-18 (שלחו לי מייל עם מס' טלפון ואחזור אליכם).

מתנצל על התקלה, אורי.

גל

Instead, I will have them on Wednesday 16-17.30.

If somebody needs talking with me exactly to-morrow, it will be possible by either e-mail, or phone, or Skype in the period from 14 to 15.30. You are welcome to apply by e-mail.

Yefim

Reception hours of prof. Dinitz before moed A are currently set to Mondays, August 18 and 25, from 16 to 18.

Keep eye on possible changes.

Have a good luck with your preparation.

Yefim

**CAREFULLY**as appeals that do not meet them will be discarded.

- Submit your appeal only in the appeal period (26.8-31.8), not before, not after.
- You may not appeal the assignment grades themselves, as the appeal period for each assignment has passed. Please submit an appeal only if your individual assignment grades do not match those that appear in the submission system for you or your partner.
- Do not include any file/image attachments in your appeal.
- Assignments that have not been submitted digitally are not eligible for appeal.
- If only one of two partners is missing a grade, provide the ID # of both partners, along with the submission group # of the relevant assignment.

Appeals must be submitted to the course e-mail.

בשבוע הבא לא אקיים שעות קבלה. אני אשתדל להיות זמין במייל

גל

A brief (but full) proof for algorithm Dinitz is as follows (to be read carefully word by word (מילה מילה) ):

Statement: The length of the layered network strictly increases from phase to phase.

Proof: Consider some phase (henceforth called "current phase"). At its beginning, we built a layered network L_f of length l in the residual network N_f. At the end of the current phase, there is no path from s to t in the updated layered network (the stopping condition of a phase). Denote the flow at that moment by f'. Consider an arbitrary path P from s to t in the residual network N_f'. In order to prove the statement, it is sufficient to show that |P|>l. (why?)

Important: Everywhere in the following analysis, the notation d(v) (=layer number of v) will relate to the layered netwok L_f built at the beginning of the current phase.

Lemma 1: There is no jumping edge in (the new) residual network N_f' with respect to (the old) layered network L_f, that is no edge (u,v) with d(v) >= d(u) + 2.

Proof. Indeed, there was no jumping edge at the beginning of the current phase, by the property of BFS. Any new edge (v,u) decreases d by 1, since it is opposite to an edge (u,v) of an augmenting path. Therefore, such a new edge also is not a jumping edge.

Lemma 2: a) The length of P is at least l. b) The length of P equals l only if P belongs entirely to the layered network L_f.

Proof: We will use the pigeon holes principle, where holes are edges of P, and the number of pigeons in the hole corresponding to edge (u,v) is d(v)-d(u). Clearly, the total number of pigeons in all the |P| holes corresponding to the edges of a path P from s to t is equal to d(t) - d(s), that is to l.

a) If |P|<l, then there exists an edge in P which increases d by at least 2. However, this contradicts Lemma 1.

b) By the same reasons, if |P| equals l, then every edge in P should increase d by exactly 1. (Indeed, if some edge does not increase d, then the remaining |P|-1 = l-1 edges increase d together by l.) Pay attention that those are old edges only, since any new edge decreases d by 1. By the definition of L_f, this implies that any edge in P is in L_f, as required.

Proof of the main statement: By Lemma 2, the only case of |P| =< l is when P is included in L_f. However, this contradicts to the stopping condition of the current phase.

גל

- IS
- VC
- CLIQUE
- SAT (and variations thereof)
- SUSU
- KnapSack
- 3-Coloring

As not all students have seen the same reductions in class, you are not required to memorize any reductions by heart. That said, it is recommend that you familiarize yourselves with as many reductions as possible, as each demonstrates useful strategies that may come in handy while solving the test.

Uri Stemmer: 8.7 1200-1400

Eden Chlamtac: 6.7 1600-1800

Michael Elkin: 8.7 1400-1600

Michal Shemesh: 7.7 1315-1500

Ran Taig: 7.7 1000-1200

Ohad Ben Baruch: 6.7 1200-1400

Statement: The length of the layered network strictly increases from phase to phase.

Proof: Denote by l the length of the shortest path from s to t at the current phase. Consider any path P from s to t in the residual network N_f' at the end of the phase. On us to show that |P|>l.

The notation d(v) (= layer number) will relate to the layered netwok L built at the beginning of the current phase, everywhere in our analysis.

Lemma 1: There is no jumping edge in N_f', that is an edge (u,v) with d(v) >= d(u) + 2.

Proof. Indeed, there was no jumping edge at the beginning of the current phase, by the property of BFS. Any new edge decreases d by one, so it also is not a jumping edge as well.

Lemma 2: The length of P is at least l, and equals l only if P belongs to the layered network L built at the beginning of the current phase.

Proof: By the pigeon holes principle, if |P|<l, then there exists an edge in P which increases d by at least 2. However, this contradicts Lemma 1. By the same reasons, if |P|=l, then every edge in P should increase d by exactly one. By the definition of L, this implies that any edge in P is in L, as required.

Proof of the main statement: By Lemma 2, the only case of |P| =< l is when P is included in L. However, this contradicts to the stopping condition of the current phase.

מחר (30.6) לא אקיים שעות קבלה.

אני אהיה במשרד ביום ד' (2.7), מי שעוניין להפגש איתי - שלחו לי מייל ונקבע שעה.

גל

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

גל

Please be sure to submit your physical copy of the assignment to the course mailbox by this date.

In fact, before the first lecture on the last week, you should only know how what is it a Turing machine RUN, and the definition of a configuration of TM.

1) The layers and the distance function d(s,v) discussed in the proof are both related to the state at the BEGINNING of the phase, that is when the layered network was built.

2) At the end of the phase, there is no "jumping edges", that is edges increasing more than by one the value of the abovementioned distance from s.

3) The proof of the distance increasing is made using עקרון שובך היונים.

Hoping that this would help,

Yefim

Any student who wishes to discuss any of the topics mentioned here is most welcome to arrive to the lecturers office hours.

In case you need to see me for office hours, feel free to email me, and I will find time for you.

סטודנטים יקרים,
כפי שפורסם באתר, מחר, יום ראשון, 8.6.14 בשעות 12-14 __ בכיתה 72/210__ תתקיים הרצאת השלמה בקורס.
מחר אנו מתחילים את הנושא האחרון, מבוא לסיבוכיות, נושא רחב וחשוב. עקב כך ישנה חשיבות גדולה לנוכחותכם בהרצאה. אנא עשו כל מאמץ להגיע.
פועל יוצא של ההשלמה מחר הוא שהשבוע יועברו שלוש הרצאות בנושא (מתוך חמש בסך הכל), יום אחר יום ברצף. זהו קצב גבוה מאוד בהתחשב בעובדה שהנושא עמוק ודורש זמן "עיכול". זוהי סיבה חשובה נוספת לנוכחותכם מחר ובשאר השבוע.

מצפה לראותכם,

מיכל

Group 2: 11.6 18:00-20:00 - Bldg. 34, Room 202

Group 4: 8.6 12:00-14:00 - Bldg. 72, Room 210

Group 5: 9.6 12:00-14:00 - Bldg. 35, Room 3

Classrooms will be announced shortly.

2.6.14 18;00 room 205, building 28.

5.6.14 17:00, 32 room 210

5.6.14 15:00, 72 room 210

Michal

q.2 – Michal Shemesh

q.3 – Ohad Ben Baruch

Midterm forms are in the returning area, next to Zehava's office.

Enjoy!

Good luck.

**will not be postponed**due to this change.

- Students who submit their work to the course mailbox by 19/5 at 12:00 will receive a 10 point bonus to their assignment grade. To clarify: Only students whose
**hard copy**is**in the course mailbox**on the fateful day of May 19th at noon will receive the bonus. Please do not address the course staff requesting a bonus for reasons that do not involve your*complete solution*being*in the course mailbox*by said time. - Exemptions granted for assignment 4 will remain in effect even if the delayed submission date is no longer in your granted "ptor" period.
- As always, further delays will not be granted, though you may receive an assignment exemption for the reasons detailed in the academic regulation (i.e. Reserve duty, Hospitalization, etc.).

If you need me, Please set a meeting by e-mail.

Good Luck to you all in the rest of the course,

Ran

Have a good luck with your submission.

Yefim, Ran, and Ohad

7) In question 2, you may add any information to the original graph, without changing its vertex and edge sets.

6) There is an extension of 20 minutes of the midterm time.

5) In question 2d, the algorithm description should be formal, with explanation what does each its phase. In other words, in the form of a not too much detailed pseudo-code, as at the lectures and practical sessions.

4) At question 1, pay attention: the graph asked for may be not a tree.

3) In question 3, item b should be proved for the case d(v) < infinity.

2) In question 2, in the case of absence of any path as required, the optimum value should be minus infinity.

1) From now on, questions during midterm should be asked as published in the title page.

Good Luck

Please be sure to use the answer sheet (in order to simulate a real exam).

An English version is also available for your convenience, but it is not fully the same as the Hebrew one. Please notice: The Hebrew version is the only formal one in any case of mismatching between the two version. Be sure to follow the Hebrew version.

Good Luck

We encourage you to participate. See below the Call-for-Participation published on the previous week.

Dear students,

The midterm in the course will be held on May 9, from 9.00 to 11.30. Its material is up to algorithm Dijkstra, including. "Homer ezer sagur".

This will be a home midterm, with on-line communication on your questions during the midterm time. Submission up to May 12 at 12.00. Checking the midterm works will be based on the same standards as the final exam checking. The midterm grade will NOT take part in the final grade computation. The detailed midterm arrangement rules will be published in-advance.

The main purpose of the midterm is providing a rehearsal to the final exam. Our rich experience shows that misunderstandings on the exam requirements happen VERY OFTEN. Hence, trying in-advance to answer real exam questions, with getting a real feedback on your answers, would prevent painful cases of misunderstanding at the final exams.

Even if you would not have time to prepare the entire midterm material, you have a possibility to prepare a part of it, and then to answer and submit a part of the midterm questions. Getting those answers checked would also be of a substantial help to you.

Looking forward to your participation in the midterm.

07.05.14 14:00-16:00, building 72, room 487

11.05.14 13:00-15:00, building 32, room 308

11.05.14 18:00-20:00, building 35, room 115

Note that the last two sessions are scheduled for Sunday next week.

I forgot to submit my assignment to the submission system, what happens now?

May I have a few extra days to complete assignment X due to [personal issue] or [other academic assignments]?

Full solution will be published soon.

שבוע טוב, יהונתן.

The midterm in the course will be held on May 9, from 9.00 to 11.30. Its material is up to algorithm Dijkstra, including. "Homer ezer sagur".

This will be a home midterm, with on-line communication on your questions during the midterm time. Submission up to May 12 at 12.00. Checking the midterm works will be based on the same standards as the final exam checking. The midterm grade will NOT take part in the final grade computation. The detailed midterm arrangement rules will be published in-advance.

The main purpose of the midterm is providing a rehearsal to the final exam. Our rich experience shows that misunderstandings on the exam requirements happen VERY OFTEN. Hence, trying in-advance to answer real exam questions, with getting a real feedback on your answers, would prevent painful cases of misunderstanding at the final exams.

Even if you would not have time to prepare the entire midterm material, you have a possibility to prepare a part of it, and then to answer and submit a part of the midterm questions. Getting those answers checked would also be of a substantial help to you.

Looking forward to your participation in the midterm.

תרגול 23 לא יתקיים היום (כפי שפורסם בטעות בהודעה המקורית לגבי תרגולים סביב פסח). תרגול זה התקיים בשבוע שלפני הפסח

ביום ה' ה 24.4 בשעות 9-11 יתקיים תרגול השלמה לקבוצה 43 במקום התרגול של יום ב' ה 7.4 שהתבטל.

התרגול יתקיים בבניין 28 חדר 107.

חג שמח

גל עמרם

Chag Sameach.

התרגול של קבוצה 51 מחר (יום ד' 10-12) לא יתקיים הודעה על השלמה תגיע בהמשך

חג שמח גל

Please note that solutions exceeding the allotted space or deviating significantly from the answer sheet format were penalized up to 25% of the relevant question value. Please read the general submission guidelines and the instructions for each assignment carefully in the future as to avoid such penalties.

If you believe your assignment was graded incorrectly, you may submit an appeal, please be sure to read the appeal policy carefully. Please remember that assignment appeals are provided as a courtesy by an already overworked course staff. We have a limited amount of grading hours available and our first priority is fully grading your assignments in order to provide valuable feedback before your final exam. While you are indeed encouraged to submit an appeal if you feel a mistake has been made * and* your assignment meets the conditions of our appeal policy - if a large number of appeals that do not conform to this policy are submitted, we will be forced to reconsider the ability to appeal.

Also - remember that the weight of each assignment is at most 3 points in your final grade, so you may receive a grade of 67 in one assignment, or an average grade of 93.4 in all assignments and still receive a perfect course grade (the assignment grade component will be rounded up).

Appeals for assignment 1 can be submitted to Ramzi Kahil's mailbox no later than 15.4.2014 at 12:00.

UPDATED 10:30 4.8.2014: Hour of appeal submission deadline added.

GOOD LUCK!

מחר (7.4) שעות הקבלה שלי לא יתקיימו. כמו כן, התרגול של קבוצה 43 (16-18) נדחה לאחר פסח.

גל

שבוע טוב, יהונתן.

Sessions for groups 11,12,23,33 and 53 will be given on the week of 6-11.4 as usual. Sessions for groups 21,22,31,23,41,42,51,52 will be given on the week of 20-25.4.

An extra session will be given for group 43 at Thu. 24.4 9-11. The exact place will be announced shortly.

Happy holiday.

Good luck

I'll be available instead on Wed, 02.04, 15-16 or via e-mail.

Sorry

Ran

The change has been made in order to accommodate students that arrive from off campus on Sunday, and have trouble making the 12:00 AM deadline. Please note that **submission time remains 12:00 AM** and extensions will not be granted. If you are unable to be on campus at 12:00 AM either submit your work at an earlier time, or have a friend submit it for you.

Additionally, as stated on the course website, the ability to submit 5 out of 6 assignments is designed to allow students to exempt themselves from one assignment due to tests, personal events or heavy workload in another course. Therefore delay requests due to tests, personal events or heavy workload in another course are automatically rejected. Nevertheless, the course staff has received a large amount of delay requests due to tests, personal events or heavy workload in another course…

In order to allow quick feedback, assignment solutions are published immediately following the submission deadline. Therefore submission delays are never granted, but submission exemptions are granted in special cases. For this reason, before requesting an exemption, we kindly request that you consider: "would the exam board exempt me from a test due to this issue?" if (and only if) the answer is yes, odds are that you will receive an exemption.

This is a permanent change.

This is a permanent change.

If you are wish to submit a printed assignment, you are not required to use the provided PDF, as long as your answer sheet is in a similar format and conform to the allotted space for each question.

While you may submit a handwritten solutions, appeals on handwritten submission will not be accepted.

In addition there will be complementary lectures for groups 1,2,5 instead of the canceled Sunday lectures as follows:

**35/212 (updated!)**.

1. Please remember that the submission is at Sunday 12:00

**noon**! No extensions are planed, so please don't miss the deadline because of misunderstandings.

2. Don't forget to look from time to time at the assignments page, especially the change log section.

Good luck and happy Purim. :)

Students who wish to write the assignment on a computer may make their own documents, use the same amount of lines, and font size 14 at least in MS-Word.

Please note that group 42 was quiet crowded last week, so students registered to this group will take precedence over students attending it as a make up session.

Ran

The accurate information can be found now at the Course info page.