# Announcements

## 20 last messages

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.

גל