Give the randomized PRAM algorithm for maximal independent set described in class. Analyze its run time. ---- ((resource:Ans8.png|Resource Description for Ans8.png)) ---- '''Analysis of Runtime''' 1: Each iteration of the above algorithm takes O(log n) time on an EREW PRAM with O(m + n) processors 2: The "while" loop in Step 2 has a run time of O(log n) : This is due to the argument based on Good and Bad vertices and Edges. Call a vertex v good if it has at least d(v)/3 neighbors of degree no more the d(v); otherwise, the vertex is bad. An edge is good if one of its endpoints is good and is bad otherwise. A good vertex is quite likely to have one of its lower degree neighbors in S and so is likely to be deleted from V. We argue that the number of good edges is large, and since good edges are likely to be deleted, a large number of edges will be deleted each iteration and this will ensure that the number of iterations to be carried out decreases logarithmic times 3: The parallel for loop in Step 2a : Takes O(log n) time to execute 4: The parallel for loop in Step 2b : Takes O(log n^2) time to execute since the maximum number of edges in a dense graph can be at most n^2. This value can be simplified to 2 log n 5: The parallel for loop in Step 2c : Takes O(log n) time to execute 6: Total runtime = O(log n) * O(log n + 2 log n + log n) = O (log ^ 2 n) ---- Team : Anumeha Shah, Neha Rajkumar, Shruti Sharma