# Announcements

## 20 last messages

Office Hours for Moed C
The following staff members will hold office hours before Moed C (list constantly updated):

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

published on 16/11/2014 13:18:45 by Boaz Arad
Special consideration for students attending the course a second time
Students who are attending the course a second time, attended Moed B2 and received a final grade of 55 are kindly requested to contact the course mailbox.
published on 05/11/2014 14:48:41 by Boaz Arad
Moed B2 Grades Published in the Submission System

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.

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

published on 28/10/2014 17:14:25 by Boaz Arad
Michal Shemesh - office hours before moed B2
I'll hold my office hours this Friday, 17/10, 11-13.
published on 16/10/2014 09:25:59 by Michal Shemesh
Correctness of the structural formula at DP
Dear students,

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

published on 13/10/2014 16:02:50 by Yefim Dinitz
שעות קבלה
לקראת מועד ב2 אקיים ביום שלישי הקרוב (14.10) שעות קבלה בשעות 12-14

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

published on 11/10/2014 17:16:12 by Uri Stemmer
Reception hours before moed B2
Reception hours before moed B2:

Yefim Dinitz: 16-17.30 on Monday, October 13

Gal Amram: 14-16 on Sunday, October 12

published on 07/10/2014 15:02:34 by Yefim Dinitz
Moed B1 Grades Published in the Submission System

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.

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

published on 28/09/2014 10:07:40 by Boaz Arad
Moed B1 grades will be published on Sunday
Due to the holiday, Moed B1 grades will be published on Sunday.
published on 24/09/2014 15:37:08 by Boaz Arad
Grading comments for Moed B has been published in the exams section.

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

published on 23/09/2014 13:03:31 by Michal Shemesh
Moed B Solution Published
A sample solution for Moed B has been published in the exams section
published on 22/09/2014 21:42:19 by Ohad Ben baruch
Office hours for moed B have been updated
published on 13/09/2014 14:22:11 by Michal Shemesh
Final Exam time change!
Please note that the exam on Monday, 15/09/14, will begin at 13:30 instead of the original time- 09:00.

Good Luck!

published on 12/09/2014 12:15:43 by Algo142
Moed A Solution Published
A sample solution for Moed A has been published in the exams section
published on 10/09/2014 18:12:41 by Boaz Arad

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.

published on 08/09/2014 13:25:48 by Boaz Arad
Office Hours For Moed Beit - UPDATED
The following staff members will hold office hours prior to the upcoming exam. This list will be updated, so check back often.

Ran Taig 10.9 (Wed) 09.30-11.30 Mainly for questions on the first half of the course
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

published on 07/09/2014 11:40:28 by Boaz Arad
Special consideration for students who were called for reserve duty
The department has decided to give special consideration to students who have served (or are still serving) 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.

published on 26/08/2014 10:43:05 by Boaz Arad
Updated version of the proof for algorithm Dinitz (is recommended to read)
A brief (but full) central 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. 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.

published on 24/08/2014 14:26:52 by Yefim Dinitz
Update to components of final grade
Due to the continued conflict, which has disrupted many students ability to study, the course staff has decided to reduce the weight of the final exam in the course grade to 70%.

So, to reiterate:

If [exam_grade] > 56
Else