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]]>
**Moed B2** and received a final grade of **55** are kindly requested to contact the course mailbox.]]>

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

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 המתאים.]]>

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

Gal Amram: 14-16 on Sunday, October 12]]>

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

Good Luck!]]>

**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.]]>
**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**

]]>**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.]]>

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

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