Hint for HW3 | |
|
Q1. For section a think of the coupon collector problem and look for an analogous proof. For section b assume that you covered 1-eps fraction of the vertices. Think how many steps are needed to cover an additional eps/2 fraction of vertices. Q4. Prove that: 1. At each step of the DFS algorithm we have a partition of the vertices to 3 sets L, P, R such that P is always a path and L and R have no edges between them. 2. Each step of the DFS algorithm either moves a vertex from P to L or a vertex from R to P. |
| עדכון אחרון ב-23/2/2014, 15:31:40 Last updated on 23/2/2014, 15:31:40 Последняя модификация23/2/2014, 15:31:40 تمت الحتلنة الأخيرة ب-23/2/2014, 15:31:40 |
HW3 is online | |
|
Submission date is February 26th. |
| פורסם ב-26/1/2014, 15:14:20 Created on 26/1/2014, 15:14:20 Создано26/1/2014, 15:14:20 تم النشر ب-26/1/2014, 15:14:20 |
Final revision to HW2 ? | |
|
There is yet another update to Q5. We are truly sorry about that. If you have further comments about Q5 please send them directly to Ariel. |
| פורסם ב-14/1/2014, 17:58:36 Created on 14/1/2014, 17:58:36 Создано14/1/2014, 17:58:36 تم النشر ب-14/1/2014, 17:58:36 |
HW2 revised | |
|
There is yet another update to HW2 due to some errors that were pointed out by Gal and Mor. I have extended the submission date by one week. |
| עדכון אחרון ב-13/1/2014, 22:20:00 Last updated on 13/1/2014, 22:20:00 Последняя модификация13/1/2014, 22:20:00 تمت الحتلنة الأخيرة ب-13/1/2014, 22:20:00 |
HW2 revised | |
| There is an update to HW2 due to some errors that were pointed out by Mor. |
| עדכון אחרון ב-6/1/2014, 15:22:01 Last updated on 6/1/2014, 15:22:01 Последняя модификация6/1/2014, 15:22:01 تمت الحتلنة الأخيرة ب-6/1/2014, 15:22:01 |
HW2 is online | |
| Submission date is January 17th. |
| פורסם ב-1/1/2014, 09:56:18 Created on 1/1/2014, 09:56:18 Создано1/1/2014, 09:56:18 تم النشر ب-1/1/2014, 09:56:18 |
Addendum to Q5 | |
|
To slove Q5 you probably need the following fact: Fact: the number of closed walk of length 2k (from a vertex v to itself) in a d-regular graph is at least the number of closed walks of length 2k on the d-regular (infinite) tree (from the root to itself). The proof is fairly simple, but you can use it as a fact. |
| עדכון אחרון ב-28/11/2013, 16:54:35 Last updated on 28/11/2013, 16:54:35 Последняя модификация28/11/2013, 16:54:35 تمت الحتلنة الأخيرة ب-28/11/2013, 16:54:35 |
Small correction to Q4 in HW1 | |
| In Q4 the upper bound on h should be 1/2 + o(1) as pointed out by Ben lee. |
| עדכון אחרון ב-28/11/2013, 15:16:58 Last updated on 28/11/2013, 15:16:58 Последняя модификация28/11/2013, 15:16:58 تمت الحتلنة الأخيرة ب-28/11/2013, 15:16:58 |
HW1 is now online. | |
| Submissions are due by December 6th. |
| פורסם ב-18/11/2013, 10:53:06 Created on 18/11/2013, 10:53:06 Создано18/11/2013, 10:53:06 تم النشر ب-18/11/2013, 10:53:06 |