Extension to HW3 | |
|
We are delaying the deadline of HW3 to the 10.3. Good luck, The course staff |
| פורסם ב-9/2/2025, 10:58:14 Created on 9/2/2025, 10:58:14 Создано9/2/2025, 10:58:14 تم النشر ب-9/2/2025, 10:58:14 |
HW3 is published! | |
|
The assignment is due by 3.3.2025. Good luck, The course staff. |
| פורסם ב-4/2/2025, 14:24:55 Created on 4/2/2025, 14:24:55 Создано4/2/2025, 14:24:55 تم النشر ب-4/2/2025, 14:24:55 |
More clarifications on HW2 | |
|
Q2 - The purpose of this questions is to see how in some problems you can reach better results using a greedy approach over the local search approach. Therefore, the algorithm in Q2.2 cannot output an optimal solution for every instance. A local search algorithm starts with a feasible solution, and in each iteration changes it in a way that should improve it. You cannot start with an empty solution or remove all the intervals in the first step of the algorithm. The purpose of the previous clarification on this question is that although the local search algorithm is not optimal at all times, it needs to try and reach the best solution we can with this approach, i.e., an algorithm that starts with a feasible solution and returns it is not good enough. Q5 - you can assume that all weights and values are natural positive numbers as assumed in class. |
| פורסם ב-3/2/2025, 15:42:33 Created on 3/2/2025, 15:42:33 Создано3/2/2025, 15:42:33 تم النشر ب-3/2/2025, 15:42:33 |
Feedback for HW1 | |
|
Feedbacks are given in the webcourse. Please take them into consideration when submitting HW2. Appeals can be sent in the coming week by mail to Rotem. |
| פורסם ב-2/2/2025, 17:47:01 Created on 2/2/2025, 17:47:01 Создано2/2/2025, 17:47:01 تم النشر ب-2/2/2025, 17:47:01 |
Clarifications on HW2 | |
|
1. In Q2.2, you need to describe the best local search algorithm you can think of. A degenerated algorithm would not receive a full score. 2. Besides Q2.2, when you are requested to provide an algorithm, you need to prove its correctness. 3. Although some questions are similar to what you've seen in class, your answers should include all the relevant proofs and explanations. Best of luck, The course staff |
| פורסם ב-29/1/2025, 20:00:35 Created on 29/1/2025, 20:00:35 Создано29/1/2025, 20:00:35 تم النشر ب-29/1/2025, 20:00:35 |
Clarification on HW2 Q3 | |
|
You are asked in the question to give a Greedy algorithm for finding a fully nice set. To show that the algorithm runs in poly-time, you can assume that there is a membership oracle for 'nice' sets; that is, given a subset S \subseteq E, we can call an oracle which decides in poly-time whether S \in I. |
| פורסם ב-21/1/2025, 12:05:48 Created on 21/1/2025, 12:05:48 Создано21/1/2025, 12:05:48 تم النشر ب-21/1/2025, 12:05:48 |
HW2 is published! | |
|
The assignment is due by 4.2.2025. Good luck, The course staff. |
| פורסם ב-13/1/2025, 15:13:20 Created on 13/1/2025, 15:13:20 Создано13/1/2025, 15:13:20 تم النشر ب-13/1/2025, 15:13:20 |
Lectures - Change of Classroom | |
|
Dear Students, Following the return of teaching to the campus, the lectures permanently move to Ullmann 103. Regards, Course Staff |
| פורסם ב-8/12/2024, 14:04:58 Created on 8/12/2024, 14:04:58 Создано8/12/2024, 14:04:58 تم النشر ب-8/12/2024, 14:04:58 |
HW1 is published! | |
|
The assignment is due at 26.12.2024. Good luck, The course staff. |
| פורסם ב-2/12/2024, 12:20:41 Created on 2/12/2024, 12:20:41 Создано2/12/2024, 12:20:41 تم النشر ب-2/12/2024, 12:20:41 |
Lectures - Location Change (1/12) | |
|
Dear Students, As of tomorrow (2/12), the lectures will take place at Ullmann 804. Regards, Course Staff |
| עדכון אחרון ב-1/12/2024, 12:52:05 Last updated on 1/12/2024, 12:52:05 Последняя модификация1/12/2024, 12:52:05 تمت الحتلنة الأخيرة ب-1/12/2024, 12:52:05 |
Lectures - Change of Location | |
|
Dear Students, As of Monday (18/11), the lectures will take place at Auditorium 1 in the Kahn (Mechanical Eng.) building. Regards, Course Staff |
| עדכון אחרון ב-13/11/2024, 22:36:36 Last updated on 13/11/2024, 22:36:36 Последняя модификация13/11/2024, 22:36:36 تمت الحتلنة الأخيرة ب-13/11/2024, 22:36:36 |
Welcome to Approximation Algorithms | |
|
Dear Students, We are excited to open the Winter 2024/5 semester! The lectures will take place in the campus, in Taub 401. More info. about the course will be given in the first class. We wish you a successful Winter semester, and hope for quieter days soon, Hadas and Rotem |
| עדכון אחרון ב-9/11/2024, 23:13:47 Last updated on 9/11/2024, 23:13:47 Последняя модификация9/11/2024, 23:13:47 تمت الحتلنة الأخيرة ب-9/11/2024, 23:13:47 |