((resource:IMG-20220314-WA0005.jpg|Resource Description for IMG-20220314-WA0005.jpg)) Team - Abhishek Vaid, Rishabh Pandey, Shashank Hegde

-- Practice Midterm Mar 14 2022

Ayan Singh, Ivan Hernandez, and Gargi Sheguri ((resource:255_practicemidterm.jpeg|Resource Description for 255_practicemidterm.jpeg))

-- Practice Midterm Mar 14 2022

Team: Jatin Battu, Aditya Singhania((resource:WhatsApp Image 2022-03-14 at 5.12.41 PM.jpeg|Resource Description for WhatsApp Image 2022-03-14 at 5.12.41 PM.jpeg))

-- Practice Midterm Mar 14 2022

 
 
Input: G=(V,E)
Output: A maximal independent triangle set I contained in V
1. I := emptyset
2. 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 1−exp(−1/9). 
 
Lemma#. The probability that a good vertex belongs to S∪Γ(S) is at least (1−exp(−1/9))/3. 
 
- Manasa Mananjaya, Damanpreet Kaur, Venkat Teja Golamaru 
 

<pre> Input: G=(V,E) Output: A maximal independent triangle set I contained in V 1. I := emptyset 2. 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 1−exp(−1/9). Lemma#. The probability that a good vertex belongs to S∪Γ(S) is at least (1−exp(−1/9))/3. - Manasa Mananjaya, Damanpreet Kaur, Venkat Teja Golamaru </pre>

-- Practice Midterm Mar 14 2022

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

-- Practice Midterm Mar 14 2022

Team - Sriya Balineni,Thomas, Likhitha Yelamanchili ((resource:IMG-6399.jpg|Resource Description for IMG-6399.jpg))

-- Practice Midterm Mar 14 2022

'''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.

-- Practice Midterm Mar 14 2022

Parth and Nemish ((resource:prac midterm q4.jpg|Resource Description for prac midterm q4.jpg))

-- Practice Midterm Mar 14 2022

Question 6) Ajinkya Rajguru, Aditi Agrawal , Pranjali Bansod ((resource:Prac_6.jpg|Resource Description for Prac_6.jpg))

-- Practice Midterm Mar 14 2022

Team - William Wang, Abhishek Reddy, Pradeep Narayana ((resource:IMG_1921.jpg|Resource Description for IMG_1921.jpg))