## Moed B Grades | |

The Moed B grades, along with factored grades, are available online. The final grade was calculated according to the following formula: round((examB<49)?FinalB*1.3:FinalB*1.45) where FinalB = ExamB*0.85 + HW_AVG*0.15. ExamB = the exam's grade. HW_AVG = average of the best 5 HW assignments. Appeals should be submitted to David's cell by Thursday 03/11, 12:00. Wishing you a fruitful semester and good luck with the rest of your studies, Course Staff |

27/10/2011, 13:18:23 |

## Moed B | |

The Moed B exam will take place next Sunday, 23/10, 17:00-20:00, in Taub 7. The exam is "closed material", except for the handout page,which can be found under Course Material/Exam Material.Exam MaterialThe material for the exam covers everything taught in class (both lectures and recitations) and homework, greedy algorithms included. Reception Hours before the examShmuel: Monday, 17/10, 12:00-13:00 in his office. David: Tuesday, 18/10, 12:00-13:00 in his office. Good luck on the exam, Course Staff |

16/10/2011, 19:14:37 |

## Moed A Grades | |

The Moed A grades, along with factored grades, are available online. The final grade was calculated according to the following formula: FactorA = round((ExamA<34)?FinalA*1.6: FinalA*1.6 + 3) where FinalA = ExamA*0.85 + HW_AVG*0.15. ExamA = the exam's grade. HW_AVG = average of the best 5 HW assignments. Appeals should be submitted to David's cell by Monday 03/10, 14:00. Regards, Course |

21/9/2011, 13:59:52 |

## Clarification concerning Matrix Multiplication | |

As announced by Prof. Zaks in class, the subject of multiplying matrices of size n x n in time faster than O(n^3), will not appear in either exam (this subject has only been mentioned shortly in class - Strassen's recursive algorithm, based on multiplying 2x2 matrices, was mentioned in one of the lectures). Regards, Course Staff |

12/9/2011, 19:40:55 |

## HW 6 + Dynamic Programming framework explanation | |

The last assignment's grades are available online and will be available at the secretariat by Sunday 12:00. In addition, an explanation of a framework for problem-solving based on Dynamic Programming can be found in the course website, under Course Material. Have a good weekend, Course Staff |

9/9/2011, 13:08:50 |

## Moed A | |

The Moed A exam will take place next Wednesday, 14/09, 17:00-20:00, in Ullman 306 and 311. The exam is "closed material". The Moed A first page and the handout can be found under Course Material/Exam Material. ReminderWe wish to remind you that to pass the course, you must have passed at least 5 of the 6 hw assignments. Students who did not pass 5 assignments are required not to come to the exam, as their exam will not be checked. Exam MaterialThe material for the exam covers everything taught in class (both lectures and recitations) and homework, besides the subject of greedy algorithms. Reception Hours before the examShmuel: Sunday 11:00-12:00 in his office. David: Monday 11:00-12:00 Good luck on the exam, Course Staff |

8/9/2011, 13:20:48 |

## Assignments returned to the secretariat | |

Assignments 4 and 5 have been returned to the secretariat. Regards, Course Staff |

7/9/2011, 10:19:19 |

## Announcement concerning HW6. | |

Due to David's reception hour being cancelled today, and to allow students to attend a reception hour before the assignment's deadline, you can submit the 6th assignment by Thursday (8/9) at 12:30. Students who submit late should submit the assignment by email to David. Regards, Course Staff |

5/9/2011, 20:05:55 |

## A few annnouncements | |

Assignment 5 has been graded and grades are online. It will be returned to the secretariat during the week. David's reception hour today is cancelled. Regards, Course Staff |

5/9/2011, 07:49:03 |

## Assignment 6 available online | |

The sixth (and last) assignment is available online. Due date: 7/09 12:30. Submission to David's cell in Taub 5th floor (alternatively, you can submit at the beginning of the lesson). Enjoy! Course Staff |

31/8/2011, 10:23:55 |

## Simplification of HW5, Q2 | |

You can solve Q2 with all inequalities not strict inequalities. That is, the inequalities are all of the form x_i - x_j <=c_k (and not x_i - x_j < c_k). While the original phrasing, with strict inequalities, is solvable, it is somewhat harder than intended. Regards, Course Staff |

29/8/2011, 14:30:32 |

## Assignment 4 graded, grades online | |

Assignment 4 has been graded, and its grades appear online. The assignments will be returned on Wednesday's recitation (as the secretariat is closed this week).Also, note some common mistakes:2b) If you claim you have returned all elements of set X (in this case, all edges not in any MST), you need to show all elements you returned are in X, but also that all elements in X have been returned, as just saying "I returned only elements in X" can be achieved easily by returning the empty set.3) A simple claim to prove (but one that still needs proving) is that a shortest circle containing s and v is made up of a a shortest path from s to v and a shortest path from v to s. 4) Too few students gave a short and simple proof of why their reduction is valid. That is, showing that solutions found in their G' correspond to "legal" paths in G and vice versa. Please learn from the remarks you got on your work and the mistakes above. Regards, Course Staff |

29/8/2011, 11:55:21 |

## Needed information for Q5 in Assignment 5 => 5a cancelled | |

As you have not yet learned a theorem necessary to prove 5a, and will only see a proof of this theorem next Wednesday, you do not have to prove 5a, and can take it as a given. Regards, Course Staff |

24/8/2011, 18:29:18 |

## Schedule Change | |

Due to popular demand, the last two weeks' schedule will continue until the end of the semester. That is: Lectures: Monday 14:30-16:30. Wednesday 8:30-10:30. Recitations: Wednesday 14:30-16:30. Prof. Zaks's reception hours: Thursday 11:00-12:00. David's reception hours: Monday 13:00-14:00, Wednesday 16:30-17:00. Regards, Course Staff |

24/8/2011, 12:06:45 |

## Assignment 5 available online | |

The fifth assignment is available online. Due date: 31/08 12:30. Submission to David's cell in Taub 5th floor (alternatively, you can submit at the beginning of the lesson). Enjoy! Course Staff |

24/8/2011, 09:33:00 |

## Non-terminating example of Ford-Fulkerson | |

A simple example of a real-valued flow network on which the Ford Fulkerson may not terminate has been uploaded to the course site, and can be found under Course Material/Lectures. Regards, Course Staff |

24/8/2011, 09:32:22 |

## Lecture Notes for Maximum Flow | |

Lecture Notes for Maximum Flow are available online, under Lectures. Regards, Course Staff |

23/8/2011, 15:45:22 |

## Question 4: Better running time of Dijkstra | |

In some of the questions of assignment 4 you are required to give algorithms with running time related to (E+VlogV). For these questions you are allowed to assume Dijkstra can be implemented in time O(E+VlogV), even though this implementation required data structures that you have most probably not learned. Regards, Course Staff |

22/8/2011, 13:07:30 |

## Assignment 3 graded, grades online | |

Assignment 3 has been graded, and its grades appear online. The assignments can be found in the return cells, in a cell dedicated to the summer semester's algo course.A big motif of this assignment:Most, if not all, of the algorithms presented by students could, unsurprisingly, be seen as a special implementation of the generic (MST) algorithm. Short and simple proofs could be given using this observation, though not all students noticed this. Note that when proving your algorithm's correctness you should prove that you are indeed making a legal application of the blue or red rule - in a cut/circle with no blue/red edges. Once you've done this, the algorithm's correctness follows directly from the generic algorithm's correctness. Students who missed this point found themselves writing long and elaborate proofs, in which they had just enough space to make small mistakes. Please learn from the remarks you got on your work and the above note. Regards, Course Staff |

22/8/2011, 13:33:33 |

## Missing detail in yesterday's proof concerning yellowest MST | |

The (delicate) part of the proof showing e' was considered after e^* has been highlighted (in yellow :-)) in the slides for recitation 6. Please go over it. Regards, Course Staff |

18/8/2011, 12:43:47 |

## Assignment 4 available online | |

The fourth assignment is available online. Due date: 24/08 12:30. Submission to David's cell in Taub 5th floor (alternatively, you can submit at the beginning of the lesson). Enjoy! Course Staff |

17/8/2011, 10:33:30 |

## Assignment 2 graded, grades online | |

Assignment 2 has been graded, and its grades appear online. The assignments can be found in the return cells, in a cell dedicated to the summer semester's algo course.Also, note some common mistakes:2) When referring to the White Path Theorem, the fact that a path exists between 2 vertices is not enough for there to be some ancestral relation between them in the DFS tree. Specifically, if v is the vertex you claim is the ancestor, you must prove a WHITE path exists when v is discovered. 4) Many students messed up seif a, trying to prove the claim by induction. If you want to use an inductive proof, make sure you can use your inductive hypothesis in your step, otherwise you have proven nothing. In this case, students who wanted to claim that a source exits in G and proved that it is true for any subset of size n-1 that the induced graph has a target iff it's a "shortcut graph" and then wanted to "add back" the n-th vertex, using the fact that the n-1 first vertices induce a graph with a target HAD to show that there exists a vertex v such that its removal still leaves you with a shortcut graph. 5) Some students returned a minimal strongly connected component with no proof that this is indeed a minimal sized closed set. Notice that a claim "starting from a strongly connected component and removing vertices gives you a non-closed set" is not a proof of minimality, as there could (conceivably) be some closed set which is not contained in only 1 strongly connected component. Please learn from the remarks you got on your work and the mistakes above. Regards, Course Staff |

15/8/2011, 12:06:39 |

## Clarification concernig assignment 3, question 1 | |

In Question 1, G is connected (otherwise the claim in 1.a is false). Regards, Course Staff |

10/8/2011, 17:51:40 |

## Assignment 3 available online | |

The third assignment is available online. Due date: 17/08 12:30. Submission to David's cell in Taub 5th floor (alternatively, you can submit at the beginning of the lesson). Enjoy! Course Staff |

10/8/2011, 09:47:58 |

## Lecture Changes for the next 2 weeks | |

The lectures on Mondays 15/8 and 22/8 will take place at 14:30-16:30 (instead of 08:30-10:30). The recitations of the 15/8 and 22/8 will not take place. Instead, we will have 2 recitations on Wednesday 17/8 and 24/8, at 14:30-16:30. To allow for reception hours before the 3rd and 4th assignments' deadlines, David will hold reception hours on Mondays 15/8 and 22/8 at 13:00-14:00, instead of his usual reception hour after the Monday recitation. The change is necessary since Professor Zaks has to participate in important Technion meetings. We apologize for any inconvenience. Regards, Course Staff |

9/8/2011, 12:53:07 |

## Assignment 1 graded, grades online | |

Assignment 1 has been graded, and its grades appear online.Also, note some common mistakes:When confronted with a problem similar to a problem you have seen before, you can either: - make a variation of an algorithm which solves the old problem (might very well be difficult to prove). - make a reduction to the known problem. In this case, you need to show that solutions in the original problem correspond to solutions in the new problem instance (see notes about question 6). Particular questions:1+4) Lack of proof of correctness. When giving some output, you need to prove that this output does indeed meet the problem's requirements. 3) BFS does not solve shortest paths for weighted graphs (we will learn more about this problem in the coming weeks) 5) an algorithm which runs in time O(U*...) is not polynomial (as the size of the input would be of the form logU*...). We say about such run-time that it is pseudo-polynomial.6) Many students did not show that the paths in their new graph corresponded to colorful paths in the original graph and vice versa. Please learn from your mistakes and the mistakes above. Regards, Course Staff |

8/8/2011, 14:19:02 |

## Recitation Slides for Recitation 5 online | |

Notice that they contain both an "old" version and a "new" version. The new version is the version we will use in the lesson today. The old version is mainly there to show how not to write up algorithms... Regards, Course Staff |

8/8/2011, 13:37:31 |

## Correction of HW2 Question 5 | |

As has been pointed out by a few students, the definition of Closed Group given in the previous announcement is in fact trivial, as U=V fits the requirements. The original phrasing of the question was, in fact, interesting enough (let this be a lesson not to post announcements after 9pm...). In short, the question as appears in the assignment is correct (find a minimal non-empty closed set). While the original question's phrasing was correct, we will still let students who solve the above question be eligible for a 10 point bonus to the assignment's grade. Regards, Course Staff |

8/8/2011, 11:10:44 |

## Typo in HW 2 => bonus | |

There is a typo in HW 2's question 5: Finding a *minimal* set U with the required property is somewhat uninteresting (to say the least). The correct definition is a *maximal* cardinality set with the required property.As the assignment is due in less than 3 days we will not require you to solve the intended question, but will allow you to solve it for an extra bonus of 10 points to the assignment's grade. In short:only submit question 5 if you find a set U of maximal cardinality (in which case you may be eligible for a bonus of 10 points).Regards, Course Staff |

7/8/2011, 22:45:42 |

## Assignment 2 available online | |

The second assignment is available online. Due date: 10/08 12:30. Submission to David's cell in Taub 5th floor (alternatively, you can submit at the beginning of the lesson). Regards, Course Staff |

10/8/2011, 09:48:08 |

## Assignment 1 extension | |

Students who have not yet finished assignment 1 are allowed to submit it until Friday (5/8) 12:30 (in this case, submit the assignment by mail to David directly). Notice that assignment 2 will be published later today, so we strongly recommend you finish the first assignment as soon as possible. Also notice that due to the length of the summer semester no more postponements will be given to assignments. Please plan accordingly. Regards, Course Staff |

3/8/2011, 11:22:38 |

## Lecture classroom change | |

The course lectures will take place in Taub 3 from now on. Also, recall that tomorrow's lecture will be from 14:30-16:30 (instead of 8:30-10:30), and that this is a one time change. Regards, Course Staff |

31/7/2011, 12:44:17 |

## BFS inductive proof | |

An inductive proof of correctness of BFS has been uploaded to the course site, and can be found under Course Material->Lectures. Regards, Course Staff |

31/7/2011, 10:23:48 |

## Reception Hours Next Week | |

To allow for questions concerning assignment 1 before its deadline, David will hold a reception hour on Monday 01/08 at 12:30-13:30. Regards. Course Staff |

27/7/2011, 20:33:31 |

## Assignment 1 available online | |

The first assignment is available online. Due date: 03/08 12:30. Submission to David's cell in Taub 5th floor (alternatively, you can submit at the beginning of the lesson). Enjoy! Course Staff |

10/8/2011, 09:48:23 |

## Next week's schedule | |

As discussed in class, next week's schedule will be a little different than usual (this is a one time change). Specifically: Monday 01/08: The lecture take place at 14:30-16:30 in Taub 6 (instead of 8:30-10:30). No recitation will be given on Monday. Wednesday 03/08: Two recitations will be given, 14:30-16:30 in Taub 6. Lecture will take place as usual. Regards, Course Staff |

27/7/2011, 16:02:45 |

## Recommended reading before the first lesson | |

To freshen up on some graph theory definitions, which we will use throughout the course, you are asked to read the file on graph theory definitions before the first lessons, this Monday. The file is in the Course Material section under Other Materials Wishing you all a fruitful semester, Course Staff |

21/7/2011, 14:13:35 |

## Algorithms 1 (234247) - Welcome ! | |

Welcome to the Algorithms 1 course. All information about the course can be found on the site (staff, tutorials, syllabus and homework). The first 2 tutorials are already online and the rest of the tutorials will be uploaded during the semester. If you did not receive this e-mail to your account, please register to the course mailing list (through the "Auto-Update" link), as the announcements made in the course site are binding. We wish you a good semester ! Algorithms 1 course staff. |

19/7/2011, 15:25:39 |