Final grades | |
|
The final grades have been submitted. Have a good summer! Keren |
| פורסם ב-2/7/2013, 09:32:14 Created on 2/7/2013, 09:32:14 Создано2/7/2013, 09:32:14 تم النشر ب-2/7/2013, 09:32:14 |
Correction to Question 1 | |
|
In sections b and c, it should be: |M|=Theta(n|S|) instead of: |S|=Theta(n|M|) |
| פורסם ב-26/6/2013, 10:30:34 Created on 26/6/2013, 10:30:34 Создано26/6/2013, 10:30:34 تم النشر ب-26/6/2013, 10:30:34 |
Home Exam | |
|
Good morning! The exam appears now in the home assignments tab. It contains 7 questions in 3 pages. Please go over all questions before starting. I will be available in person or by email throughout the exam for any questions. Good luck! Keren |
| פורסם ב-26/6/2013, 07:46:40 Created on 26/6/2013, 07:46:40 Создано26/6/2013, 07:46:40 تم النشر ب-26/6/2013, 07:46:40 |
A comment on today's discussion in class | |
|
We have previously bounded the running time of an algorithm by analyzed how a set of edges grows (rather than a set of nodes) when we talked about randomized algorithms for MIS. While we could not argue that in each iteration many nodes either get selected or have a neighbor that gets selected, we did argue that in each iteration many edges are connected to selected nodes or neighbors of selected nodes. We then bounded the running time from above by bounded the growth of this set from below. |
| פורסם ב-30/5/2013, 15:39:01 Created on 30/5/2013, 15:39:01 Создано30/5/2013, 15:39:01 تم النشر ب-30/5/2013, 15:39:01 |
Home exam | |
|
The home exam will take place on Wednesday 26.6. |
| פורסם ב-12/5/2013, 14:00:57 Created on 12/5/2013, 14:00:57 Создано12/5/2013, 14:00:57 تم النشر ب-12/5/2013, 14:00:57 |
Complementary class | |
|
There will be a complementary class on Monday 20.5, 9:30-11:30 in room 601. This is instead of the class on Thursday 13.6, which is cancelled. |
| פורסם ב-12/5/2013, 13:59:34 Created on 12/5/2013, 13:59:34 Создано12/5/2013, 13:59:34 تم النشر ب-12/5/2013, 13:59:34 |
Home exam | |
| Don't forget to email me your date preferences (June 16 - June 27) |
| פורסם ב-4/4/2013, 15:04:03 Created on 4/4/2013, 15:04:03 Создано4/4/2013, 15:04:03 تم النشر ب-4/4/2013, 15:04:03 |
Hints for home assignment 1 | |
|
Question 2: Look at B_{t,n} and search for cycles on its 2-coloring (what can you say about the length of cycles in a bipartite graph?) Question 4b: Find an MIS on a graph G' that is created from G by replacing each node v with a clique {v_0,..,v_d(v)} of size d(v)+1, and adding an edge between clique nodes v_i and u_i if v and u are neighbors in G. Notice that nodes in G can simulate the algorithm on G', and think how they can use it to get a Delta+1 coloring in G. |
| עדכון אחרון ב-4/4/2013, 15:01:45 Last updated on 4/4/2013, 15:01:45 Последняя модификация4/4/2013, 15:01:45 تمت الحتلنة الأخيرة ب-4/4/2013, 15:01:45 |