Practice Midterm Mar 14 2022 .
Team - Abhishek Vaid, Rishabh Pandey, Shashank Hegde
(Edited: 2022-03-14)Ayan Singh, Ivan Hernandez, and Gargi Sheguri
Team: Jatin Battu, Aditya Singhania
<pre>
Input: G=(V,E) Output: A maximal independent triangle set I contained in V
- I := emptyset
- Repeat { a) For all v in V do in parallel If d(v) = 0 then add v to I and delete v from V. else mark v with probability 1/(3d(v)). b) For all u,v,w in V do in parallel if both u and v, v and w, w and u are marked for any (e1,e2) in E then unmark the lower degree vertex. c) For all v in V do in parallel if v is marked then add v to S d) I := I union S e) Delete S union Gamma(S) from V and all incident edges from E } Until V is empty.
Gamma(vertex) is the triangles connected that vertex.
Now, the lemmas of Parallel MIS are changed in the following way for the Parallel MTIS algorithm
Lemma**. During any iteration, if a vertex w is marked then it is selected to be in S with probability at least 1/3.
Lemma*. Let v in V be a good vertex with degree d(v)>0. Then, the probability that some vertex w(v) gets marks is at least 1exp(1/9).
Lemma#. The probability that a good vertex belongs to S(S) is at least (1exp(1/9))/3.
- Manasa Mananjaya, Damanpreet Kaur, Venkat Teja Golamaru
</pre>
(Edited: 2022-03-14)Q5
A platform that deals with scheduling/ load balancing/ etc. for programmers to code parallel programs without directly dealing with the CPU and RAM.
A segment of code that spawns a thread of itself, so the threads are forked online recursively.
Creating and deleting threads are still heavy, despite lighter than forking processes, so keep the threads even when they ended. In this case, the threads seemed static.
2 sub-routines accessing a same piece of memory / storage, and at least one of them were trying to write, causing undetermined result for that piece of memory/storage
(Edited: 2022-03-14)Team - Sriya Balineni,Thomas, Likhitha Yelamanchili
'''William Wang, Abhishek Reddy, Pradeep Narayana '''
To prove that any n-permutation is equally likely to be generated by the Knuth shuffle, we first prove the lemma that prior to each i <= n, the subarray A[1, i - 1] contains each possible (i - 1)-permutation with probability (n - 1 + 1)!/n!. We do this by induction on i.
In the base case where i = 1, A[1, 0] is the empty array containing the 0-permutation with probability (n-1+1)!/n! = n!/n! = 1, which is true since there is exactly 1 0-permutation.
| In the induction step, we assume that at i = k, the subarray A[1, k - 1] contains each possible (k - 1)-permutation with probability (n - k - 1)!/n!. A particular k-permutation is composed of a (k - 1)-permutation <x_1,...,x_k-1> followed by an additional element x_k. By induction, the probability of the k-permutation is (n - k - 1)!/n! * P(A[k] = x_k | A[1, k - 1] = <x1,...,x_k-1>). Since x_k is chosen at random from A[k, n] in the Knuth shuffle algorithm, the second factor is 1/(n - k + 1) which produces the final probability as (n - k - 1)!/n! * 1/(n - k + 1) = (n k)!/n! and proves the lemma. |
|---|
With the lemma proven and the knowledge that the Knuth shuffle generates any n-permutation before the (n + 1)st iteration, we can conclude by the lemma that the Knuth shuffle generates a random n-permutation with probability (n - (n + 1) + 1)!/n! = 0!/n! = 1/n!, concluding the proof.
(Edited: 2022-03-14)Parth and Nemish
Question 6) Ajinkya Rajguru, Aditi Agrawal , Pranjali Bansod
Team - William Wang, Abhishek Reddy, Pradeep Narayana
