## Final grades | |

The final grades have been submitted. Have a good summer! Keren |

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 |

## 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 |

## 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 |

## Home exam | |

The home exam will take place on Wednesday 26.6. |

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 |

## Home exam | |

Don't forget to email me your date preferences (June 16 - June 27) |

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 |