# Announcements

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


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

published on 24/08/2014 11:55:54 by Boaz Arad
שעות קבלה
ביום ב' ה25.8 אקיים שעות קבלה ב 10-12

גל

published on 21/08/2014 22:18:07 by Gal Amram
Office Hours for Moed A
We will hold office hours this week and next week, to help you prepare. The following office hours have been scheduled:

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!

published on 21/08/2014 21:32:39 by Algo
שינוי שעות קבלה - אורי שטמר
לא אוכל לקיים את שעות הקבלה שתוכננו ליום רביעי 20.8 בשעות 12-14. במקומן אקיים שעות קבלה ביום חמישי 21.8 בשעות 12-14.

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

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

published on 20/08/2014 03:35:48 by Uri Stemmer
מיני שעות קבלה
מחר אני אהיה במשרד ב 9-11. מי שרוצה מוזמן להגיע עם שאלות

גל

published on 18/08/2014 19:52:40 by Gal Amram
CHANGE of reception hours of prof. Dinitz
Unfortunately, I am not able to give reception hours to-morrow, Monday 18.8 from 16 to 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

published on 17/08/2014 22:03:47 by Yefim Dinitz
Reception hours of prof. Dinitz before moed A
Dear students,

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

published on 12/08/2014 15:53:48 by Yefim Dinitz
You can now view your final assignment grade in the submission system under "Final Assignment Grade". Your individual assignment grades can be seen under "Grader Notes". Assignment grades have been rounded up. You may appeal this grade between the 26th of August and the 31th of August (and only then). Please review the following guidelines 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.
published on 03/08/2014 10:40:33 by Boaz Arad
The grades for assignments 5 and 6 are now available in the submission system.
published on 31/07/2014 19:45:26 by Boaz Arad
ביטול שעות קבלה
שלום לכולם

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

גל

published on 18/07/2014 23:10:40 by Gal Amram
Office Hours
My office hours today are cancelled. However, I will be available to answer questions on email and on phone from 16:00 to 18:00.
published on 08/07/2014 12:29:44 by Uri Zoran
Assignment 5' assignments returned
The assignments can be found in the return area.
published on 07/07/2014 21:37:54 by Uri Zoran
Extended proof for algorithm Dinitz - edited (on pigeon holes)
After today's reception hours, I edited the proof published previously (see the updated version below).
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.

published on 07/07/2014 18:00:40 by Yefim Dinitz
Office hours
I will hold my office hours tomorrow from 13-15 instead the regular hours.
published on 07/07/2014 17:31:06 by Ramzi Kahil
Reception hours of Yefim Dinitz: Monday 16-18
I will hold office hours this Monday, 7.7, from 16:00 to 18:00. (room 203/37)
published on 07/07/2014 14:15:26 by Yefim Dinitz
Office Hours
I will hold office hours this Monday, 7.7, from 10:00 to 12:00.(room 226)
published on 06/07/2014 22:01:55 by Igor Mishsky
Office Hours
I will hold office hours this Tuesday, 8.7, from 16:00 to 18:00, for those of you who have last-minute questions before the exam.
published on 06/07/2014 18:36:35 by Uri Zoran
Exam Handout
During the exam, a handout will be provided, this handout can be viewed on the Exams page.
published on 06/07/2014 13:57:30 by Boaz Arad
שעות קבלה
ביום ב' 7.7 10-12 אקיים שעות קבלה. להזכירכם - אני נמצא ב 37/219

גל

published on 05/07/2014 21:43:41 by Gal Amram
Assignment 5 solution
The solution has been published and can be found in the assignment' page.
published on 03/07/2014 22:25:38 by Uri Zoran
NP-Complete problems for the test
In order to clarify, while studying for the test you should be familiar with the following NP-Complete problems:
• 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.
published on 03/07/2014 18:41:38 by Boaz Arad
Exam Details
The first page of the exam (detailing the exam structure and allowed supplementary material) is now available in the exams section.
published on 03/07/2014 16:27:25 by Boaz Arad
Office hours preceding the test
The following staff members will hold office hours preceeding the test (please check back here for updates):

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

published on 03/07/2014 13:31:53 by Boaz Arad
Proof for algorithm Dinitz
A brief (but full) proof for algorithm Dinitz is as follows:

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.

published on 01/07/2014 18:57:47 by Yefim Dinitz
Assignment 5 solutions
We are aware that you are all eager to see the official solution for assignment 5. It will be published as soon as it is ready.
published on 01/07/2014 12:31:33 by Boaz Arad
Office hours
My office hours this week will be at Tuesday at 16-18.
published on 29/06/2014 16:24:08 by Ramzi Kahil
שעות קבלה
שלום לכולם

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

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

גל

published on 29/06/2014 10:05:35 by Gal Amram
Assignment 6 solutions published
published on 23/06/2014 09:36:20 by Boaz Arad
שעות קבלה
מחר (23.6) לא אקיים שעות קבלה.

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

גל

published on 22/06/2014 09:45:12 by Gal Amram
Office Hours
For the students in my practical sessions whom I told I won't be holding office hours tomorrow: Change of plans - office hours will be held after all! :D
published on 18/06/2014 17:31:05 by Uri Zoran
Midterm
Midterms with technical issues (late submission, etc) are now back in the returning area. Submission System grades have been updated.
published on 17/06/2014 11:11:58 by Ohad Ben baruch
שעות קבלה לשבוע הנוכחי
אהלן, אקיים את שעות הקבלה שלי מחר, יום ב', בשעות 16:30 - 18:30, ולא בשעות הקבועות. יהונתן.
published on 15/06/2014 21:11:01 by Yehonatan Cohen
Office Hours
This week I will hold my office hours on Thursday from 8:00 to 10:00.
published on 15/06/2014 18:19:56 by Igor Mishsky
Office hours
Due to foreseen circumstances, my normal Sunday office hours (tomorrow, 15/6) will be cancelled. Instead, I am moving this week's office hours to 14:00-16:00, Thursday, 19/6. -Eden
published on 14/06/2014 21:19:43 by Eden Chlamtac
Assignment 6 submission date postponed
The submission date of assignment 6 has been postponed to 20/6 at 12:00.

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

published on 13/06/2014 13:58:06 by Boaz Arad
Assignment 4 grades are now visible in the submission system.
published on 13/06/2014 13:46:55 by Boaz Arad
Assignment 4 is in the returning area
Your assignments are in the returning area, next to Zehava's office.
published on 12/06/2014 15:18:55 by Ohad Ben baruch
Turing machines UPDATED
Comment on Turing Machines:

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.

published on 11/06/2014 15:09:25 by Yefim Dinitz
proof of algorithm Dinitz
It turned out that the available lecture notes on the proof of algorithm Dinitz: the statement that after any phase the distance from s to t increases, are not full. Three following central points are lacking or not sufficiently distinguished there:

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

published on 11/06/2014 13:44:38 by Yefim Dinitz
Algorithms requirements (Data Structures and Automata and Formal Languages)
Dear Students, Please review the course requirements regarding Data Structures and Automata.
Any student who wishes to discuss any of the topics mentioned here is most welcome to arrive to the lecturers office hours.
published on 10/06/2014 20:55:49 by Michal Shemesh
Room change
Please note that my lecture tomorrow (10/6, 18:00-20:00) will be held just this once in building 34, room 10. -Eden
published on 09/06/2014 11:03:51 by Eden Chlamtac
Office Hours
This week I will hold my office hours on Wednesday from 10:00 to 12:00.
published on 08/06/2014 23:18:40 by Ohad Ben baruch
Office Hours
This week, my office hours will be held from 8:00 to 10:00 on Wednesday.
published on 08/06/2014 19:35:13 by Igor Mishsky
Office hours canceled and PS update this week
This Tuesday I will not be in town, therefor my office hours are canceled and I will not hold my regular PS. Boaz will replace me at the PS 14-16. The second PS will be held Monday (tomorrow) 18-20, 34/007.

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

published on 08/06/2014 09:33:42 by Ramzi Kahil
הרצאת השלמה - עדכון כיתה

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

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

מיכל

published on 07/06/2014 21:14:55 by Michal Shemesh
Complementary Lectures
Groups 5, 2 and 4 will hold complementary lectures as follows:

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.

published on 05/06/2014 10:56:45 by Boaz Arad
Assignment 6 Published
Assignment 6 has been published, good luck!
published on 05/06/2014 10:56:01 by Boaz Arad
Practical sessions during Shavuot holiday
Since many practical sessions will be canceled due to the Shavuot holiday, students are kindly requested to attend an alternative session or one of the following make-up sessions (the list will be updated 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

published on 03/06/2014 13:44:40 by Boaz Arad
The auxiliary examples file for ass. 5 was detailed on T-operation
The auxiliary examples file for ass. 5 was detailed on T-operation, see in brown at page 3.
published on 01/06/2014 22:50:11 by Yefim Dinitz
Assignment 5 space allocation update
The space allocated for question 2b was increased by 5 lines. The space allocated for question 4a was increased by 10 lines.
published on 01/06/2014 20:56:18 by Uri Zoran
Michal's office hours
I'll not be available tomorrow (Monday, 2/6) after class for office hours (12-14). Students who wish to meet me regarding the midterm (or any other matter) can set up a time on Thursday by email (5/6) or can meet me next Monday, 9/6 or Tuesday 10/6, (both during) 12:00-14:00.

Michal

published on 01/06/2014 19:19:08 by Michal Shemesh
Midterm questions checking
q.1 – Yefim Dinitz

q.2 – Michal Shemesh

published on 01/06/2014 14:52:44 by Yefim Dinitz
Hints for q.1 of ass. 5
Two comments were added at page 8 of the text of Tutorial 8. They may be of help for your work on question 1 of assignment 5.
published on 01/06/2014 13:15:36 by Yehonatan Cohen
Practical sessions during Shavuot holiday
Edited: See above
published on 29/05/2014 13:40:31 by Boaz Arad
Assignment 5 submission date postponed
The submission deadline for assignment 5 has been postponed to 5.6.14 at 11:59am, as per the request of the class "Vaad".
published on 29/05/2014 13:36:33 by Boaz Arad
Midterm grades are now available on the Submission System and in the Midterm Page.

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

published on 29/05/2014 12:26:03 by Ohad Ben baruch
Complementary lecture of prof. Dinitz
Prof. Dinitz will give a complementary lecture on Tuesday, June 10 from 18 to 20.
published on 28/05/2014 15:32:48 by Yefim Dinitz
Midterm Solution
The midterm solution is now available at the Midterm page.
published on 28/05/2014 13:25:41 by Ohad Ben baruch
Assignment 5 Auxiliary Examples
A file with an explanation of the algorithm ideas and a couple of examples was published and can be found in the assignment page. We hope it will help you in the process of understanding the algorithm in question 3.
published on 27/05/2014 22:11:43 by Uri Zoran
Office Hours
This week, my office hours will be held from 13:00 to 15:00 (on Thursday).
published on 27/05/2014 04:06:19 by Uri Zoran
Assignment 5 answer sheet has been published and can be found in the assignments page.
published on 26/05/2014 22:16:03 by Uri Zoran
Assignment 4 Solution
Solution for assignment 4 is now available on the assignment page.

Enjoy!

published on 25/05/2014 12:32:12 by Ohad Ben baruch
Assignment 5 published
Assignment 5 has been published and is available on the Assignments page. The answers sheet and an additional explanation file will be added in the next few days. It is advised that you start reading the assignment and thinking about it soon.
published on 20/05/2014 04:39:46 by Uri Zoran
Office hours are postponed
My office hours this week will be at Thursday 10-12. In case you need to see me and cannot attend this time you are welcomed to email me.
published on 19/05/2014 20:05:43 by Ramzi Kahil
Assignment 4 - submission system
The submission date for assignment 4 has been corrected in the submission system, you may now submit your work digitally if you have not done so already.

Good luck.

published on 19/05/2014 14:41:40 by Boaz Arad
Assignment 2 Appeals
Your appeals are in the returning area, next to Zehava's office.
published on 18/05/2014 11:34:03 by Igor Mishsky
Assignment 4 submission date postponed.
As per a request from the class "Vaad", the submission date of assignment 4 has been postponed to the 21st of May. Assignments must be submitted in hard copy form to the course mailbox by 12:00 as usual. Assignment 5 will be published on schedule, and its submission date 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.).
published on 18/05/2014 09:03:24 by Boaz Arad
Ran's office hours
Ran's regular office hours are canceled until further notice.
If you need me, Please set a meeting by e-mail.

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

Ran

published on 13/05/2014 10:41:53 by Ran Taig
Cancelled lecture and make-up class
Tomorrow (Tuesday), my 18:00-20:00 class is cancelled due to Student Day. A make-up session will be scheduled for next Sunday, 18.5, 18:00-20:00 in building 34, room 202 (in addition to the 13:00-15:00 class as usual). Eden
published on 12/05/2014 12:03:25 by Eden Chlamtac
Practical sessions this week
Students whose practical sessions are scheduled during the student day celebrations are kindly requested to attend an alternative session.
published on 11/05/2014 11:37:09 by Boaz Arad
8) Mazal tov with the midterm finished!

Have a good luck with your submission.

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

published on 09/05/2014 09:10:53 by Ran Taig
Midterm 2014
The Midterm is now available at the Midterm page.

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

published on 09/05/2014 09:01:28 by Ohad Ben baruch
Title Pages and Handout of HOME Midterm 2014
The title pages and handout of the coming HOME Midterm can be found under Midterm.

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.

published on 08/05/2014 16:52:02 by Ohad Ben baruch
Grades for assignment 3 have been published in the submission system.
published on 07/05/2014 19:15:07 by Boaz Arad
עבודה 3 בנקודת האיסוף
אהלן, בדיקת עבודה 3 נסתיימה ואתם מוזמנים לגשת ולאסוף את העבודות מאיזור ההחזרה. יהונתן.
published on 07/05/2014 16:20:19 by Yehonatan Cohen
פתרון עבודה 3
אהלן, פתרון שאלה 1 של עבודה 3 הועלה לעמוד העבודה. יהונתן.
published on 07/05/2014 16:19:02 by Yehonatan Cohen
Grades for assignment 2 have been published in the submission system.
published on 07/05/2014 12:44:46 by Boaz Arad
Assignment 2 is in the returning area
Your assignments are in the returning area, next to Zehava's office.
published on 07/05/2014 10:17:33 by Igor Mishsky
Practical sessions this week
Due to Memorial day and Independence day, several practical session will be canceled. Students are invited to attend any other regularly scheduled session, or one of the additional session listed below. All sessions this week, as well as the those listed here will cover the subject of DFS (PS 7).

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.

published on 04/05/2014 10:15:36 by Boaz Arad
Abuse of the course mailbox
Due to recurring emails regarding issues clearly explained on the Assignment page or the main course page, such e-mails will be ignored from now on. Please review the course site carefully before addressing the staff. Examples of such inquires are:

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

published on 04/05/2014 10:07:47 by Boaz Arad
Assignment 3
The solution for questions 2-4 is now published at the Assignment page.
Full solution will be published soon.
published on 01/05/2014 14:24:32 by Algo142
שעת השלמה לקבוצה של מיכל
On Thursday, 1.5.14, 8:00-9:00 I'll hold "shiur hashlama" for Group 4 at 32/210. Michal
published on 30/04/2014 18:59:07 by Michal Shemesh
Lectures and practical sessions next week (memorial day)
Next week (4-8.5.14) all lectures will be canceled. Practical sessions will be given as usual on school days, and three make-up sessions will be scheduled (times to be announced later this week). Students may attend any regularly scheduled PS, or one of the make up sessions.
published on 30/04/2014 14:12:02 by Boaz Arad
שיעור השלמה לקבוצה 4
On Thursday, 1.5.14, 8:00-9:00 I'll hold "shiur hashlama" for Group 4 at 32/210. Michal
published on 29/04/2014 20:08:54 by Michal Shemesh
השיעור של גב' מיכל שמש מחר
קבוצת ההרצאה של מיכל שמש תתקיים מחר החל משעה 11:00 ועד 12:00. שימו לב כי השיעור יתחיל בשעה העגולה! הודעה על מועד השלמת השעה החסרה יתפרסם בהמשך.
published on 27/04/2014 21:58:02 by Boaz Arad
ביטול תרגול
אהלן, קבוצת תרגול 12 (יום ב', 10:00 - 12:00, יהונתן) מבוטלת לשבוע זה בשל הפסקת הלימודים החופפת לשעות התרגול. לא יתקיים תרגול השלמה ולכן אתם מוזמנים להגיע לתרגול באחת מהקבוצות האחרות.

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

published on 27/04/2014 08:31:39 by Yehonatan Cohen
Midterm on May 9
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.

published on 24/04/2014 16:38:00 by Yefim Dinitz
Office Hours
I will not hold office hours today. Sorry for the inconvenience.
published on 24/04/2014 11:11:06 by Uri Zoran
Assignment 4 Published
Assignment 4 has been published and is available on the Assignments page. Please read the general assignment instructions carefully, as course staff are still receiving questions regarding issues that are explained clearly there. Good luck!
published on 24/04/2014 09:28:42 by Boaz Arad
תזכורת: ביטול תרגול
אהלן חברים, מזכיר לכם שקבוצת תרגול 32 (ימי חמישי, 13:00 - 15:00, יהונתן) בוטלה לשבוע זה, מכיוון שהתרגול של השבוע הנוכחי הועבר לפני היציאה לחופשת הפסח. בשמחות, יהונתן.
published on 23/04/2014 22:59:05 by Yehonatan Cohen
תרגול 23
שלום לכולם

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

published on 23/04/2014 12:27:57 by Ohad Ben baruch
תרגול השלמה לקבוצה 43
שלום לכולם

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

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

חג שמח

גל עמרם

published on 20/04/2014 18:15:13 by Gal Amram
Assignment 2 solution published
The solution for assignment 2 is now available on the assignment page.
Chag Sameach.
published on 17/04/2014 20:17:24 by Igor Mishsky
Dynamic programing tutorial v2
The tutorial presented in the second dynamic programming practical session is now available at the Class material section.
published on 12/04/2014 16:01:23 by Boaz Arad
Office Hours
I will not hold office hours tomorrow.
published on 10/04/2014 03:11:33 by Uri Zoran
שלום לכולם

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

חג שמח גל

published on 08/04/2014 21:07:00 by Gal Amram
Assignment 1 grades are now available in the submission system.

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.

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.

published on 08/04/2014 09:09:00 by Boaz Arad
Assignment 1 is in the returning area
Your assignments are in the returning area, next to Zehava's office.
published on 07/04/2014 13:19:27 by Ramzi Kahil
Assignment 3
Assignment 3 is online.

GOOD LUCK!

published on 06/04/2014 21:46:55 by Algo142
שינוי בשעת הקבלה
אהלן, שעות הקבלה שלי בשבוע הנוכחי תערכנה ביום רביעי, בשעות 14:00 - 16:00 (ולא כמתוכנן, ביום ב'). יהונתן.
published on 06/04/2014 19:32:40 by Yehonatan Cohen
שעות קבלה
שלום לכולם.

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

גל

published on 06/04/2014 15:46:18 by Gal Amram
שינויים בקבוצת תרגול 32 (יום חמישי)
אהלן חברים, קבוצת תרגול 32 (ימי חמישי, 13:00 - 15:00, יהונתן) תוזז השבוע באופן חד-פעמי. התרגול יערך ביום רביעי (9.4), בשעות 16:00 - 18:00, בניין 28, חדר 106.

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

published on 06/04/2014 10:39:38 by Yehonatan Cohen
Practical sessions around passover
During the week preceding Passover (6-11.4) and the week following it (20-25.4) the same practical session (6) will be given.

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.

published on 06/04/2014 10:17:50 by Boaz Arad
My practical sessions next week are canceled.
The next week and the week after the holiday we will cover Dijkstra's algorithm in the practical sessions. Because Tuesday is a learning day in both weeks, I will hold the PS about Dijkstra at the 22.4, and next week I will not hold any PS.

Happy holiday.

published on 04/04/2014 14:54:08 by Ramzi Kahil
Classroom changed
Michal's lecture (Group 4) on Monday mornings (10:00-12:00) will be held from now on at 92/2 (instead of 72/501).
published on 02/04/2014 20:26:41 by Michal Shemesh
Assignment 2 update
An extra space was added to question 2, and some clarifications were added.
Good luck
published on 01/04/2014 14:49:32 by Igor Mishsky
Boaz Arad's office hours tomorrow (TUE 31.3) are cancelled. An alternate time will be announced later. For urgent issues, please contact him via e-mail.
published on 31/03/2014 18:17:08 by Boaz Arad
Office hours are canceled
I will be replacing Boaz at tomorrows PS, therefore my office hours are canceled. If you wish to see me, send me an email and I will find some other time for you.
published on 31/03/2014 13:00:02 by Ramzi Kahil
Ran's office hours
Ran's office hours for tomorrow, 31.03, are canceled due to unforeseen circumstances.
I'll be available instead on Wed, 02.04, 15-16 or via e-mail.

Sorry

Ran

published on 30/03/2014 18:35:55 by Ran Taig
Assignment submission dates updated
The submission dates for assignments 2,4 and 5 have been postponed by one day as requested by the class "Vaad".

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.

published on 25/03/2014 07:22:21 by Boaz Arad
Permanent change to Igor's office hours
Igor's office hours will be held at 16:00-18:00 on Mondays.

This is a permanent change.

published on 23/03/2014 20:37:12 by Igor Mishsky
Permanent change to Prof. Yefim Dinitz's office hours
Prof. Yefim Dinitz's office hours will be held at 11.30-13.10 on Wednesdays.

This is a permanent change.

published on 23/03/2014 12:39:25 by Boaz Arad
Assignment 1 solution published
The solution for assignment 1 is now available on the assignment page.
published on 23/03/2014 12:34:07 by Boaz Arad
Assignment 2 is online
Good luck.
published on 23/03/2014 11:35:18 by Igor Mishsky
Technical issues regarding the submission system
Any technical issues you may have with the submission system should be directed towards the CS Helpdesk.
published on 22/03/2014 21:53:05 by Boaz Arad
Clarification on Assignment Submission
Use of the provided answer sheet is mandatory, answers that exceed the allotted space may have points reduced, and submissions made in an alternative format may receive a zero grade.

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.

published on 21/03/2014 12:29:44 by Boaz Arad
Office Hours Location
There is a mistake in the Course Info page regarding the building in which I am holding my office hours. It should be building 37 room -107 instead of building 58 room -107.
published on 20/03/2014 15:14:32 by Uri Zoran
Michael Elkin make up session reshcheduled
Michael's make up session has been postponed to 1400 at room 105, building 28.
published on 20/03/2014 12:31:34 by Boaz Arad
Office Hours
My office hours are permanently moved to Thursday at 12:00.
published on 19/03/2014 18:36:35 by Uri Zoran
complementary lectures
Tuesday lectures for all groups will take place as usual.
In addition there will be complementary lectures for groups 1,2,5 instead of the canceled Sunday lectures as follows:

• Ran's group 2 complementary lecture will take place on Tuesday, 18.03, 08:00 - 10:00 (just before the usual Tuesday lecture) - class: 35/212 (updated!).
• Group 5 (Dr. Chlamtac) complementary lecture will take place on Wednesday,19.03, 15:00 - 17:00 - class: 90/230.
• Group 1 (Prof. Elkin) complementary lecture will take place on Thursday,20.03, 09:00 - 11:00 - class: 90/326.
• published on 17/03/2014 11:31:39 by Ran Taig
Assignment 1
A few notes:
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. :)

published on 17/03/2014 11:30:36 by Ramzi Kahil
Igor's office hours
My office hours are moved to Tuesday, 18:00 - 20:00, room 226.
published on 16/03/2014 19:32:33 by Igor Mishsky
complementary classes
We plan to hold complementary lectures for groups 1,2,5 (instead their Sunday lectures)during the coming weeks - we'll announce locations and times on Monday - Please follow.

Ran's students (group 2) - Please note Ran's complementary lecture is planned (given we'll find a free class) for this Tuesday at 08:00-10:00 (just before the usual Tuesday lecture) - Please follow this on Monday for final time and place.
published on 15/03/2014 19:23:15 by Algo142
שעות קבלה
אהלן, שעות הקבלה שלי בשבוע הנוכחי תתקיימנה ביום שני, בשעות 14:00 - 16:00. חג שמח ושבוע טוב, יהונתן.
published on 15/03/2014 18:17:39 by Yehonatan Cohen
Lectures 17-18.3
Please note that lectures scheduled for next Monday/Tuesday (17-18.3) will be held as usual.
published on 12/03/2014 14:05:43 by Boaz Arad
Eden Chlamtac office hours
Eden Chlamtac's office hours on Sunday will be canceled due to the Purim break. Therefore he will be available at a different time: Wednesday, 19.3, 17:00-19:00 (this week only).
published on 12/03/2014 11:30:05 by Boaz Arad
You can find it on the assignments page.
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.
published on 11/03/2014 11:14:02 by Ramzi Kahil
Practical sessions on Thursday
Classes will be suspended this Thursday, students are encouraged to attend other practical sessions on Tuesday or Wednesday.

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.

published on 10/03/2014 17:08:11 by Boaz Arad
Assignment appeals
Due to student requests, the course staff has decided to reinstate the ability to appeal assignment grades. Please review the appeal requirements and procedures on the course homepage. Among other restrictions, it is important to note that appeals for handwritten assignments will not be considered - we strongly recommend that you type your assignment.
published on 10/03/2014 13:43:51 by Boaz Arad
Igor's office hours
My office hours are moved to Monday, 12:20 - 14:20, room 226.
published on 10/03/2014 11:31:44 by Igor Mishsky
Assignment 1 is online
Good luck.
published on 09/03/2014 16:02:59 by Ramzi Kahil
Ran's office hours
My office hours for the rest of the semester will be held on Mondays, 11:15-13:00. office: 37/207.

Ran

published on 06/03/2014 16:06:11 by Ran Taig
Class schedule
Please note that the BGU course file is not accurately updated yet with all the correct information regarding the course schedule.
The accurate information can be found now at the Course info page.
published on 03/03/2014 09:41:20 by Algo142