PHP Search Engine

Practice Final May 16 2022 .

Parth Mehta, Sneh Kothari, William Wang

'''Problem 2'''

Euclid(a, b): if b = 0 return a; else return Euclid(b, a mod b);

Euclid(125, 45) -> return Euclid(45, 125 mod 45) -> Euclid(45, 35)

Euclid(45, 35) -> return Euclid(35, 45 mod 35) -> Euclid(35, 10)

Euclid(35, 10) -> return Euclid(10, 35 mod 10) -> Euclid(10, 5)

Euclid(10, 5) -> return Euclid(5, 10 mod 5) -> Euclid(5, 0)

Euclid(5, 0) -> return 5

(Edited: 2022-05-16)

Parth Mehta, Sneh Kothari, William Wang '''Problem 2''' Euclid(a, b): if b = 0 return a; else return Euclid(b, a mod b); ---- Euclid(125, 45) -> return Euclid(45, 125 mod 45) -> Euclid(45, 35) Euclid(45, 35) -> return Euclid(35, 45 mod 35) -> Euclid(35, 10) Euclid(35, 10) -> return Euclid(10, 35 mod 10) -> Euclid(10, 5) Euclid(10, 5) -> return Euclid(5, 10 mod 5) -> Euclid(5, 0) Euclid(5, 0) -> return 5

-- Practice Final May 16 2022

QUESTION 5

Teammate: Abhishek Reddy Punreddy

P: It is the collection of decision problems that can be solved by a deterministic turing machine in polynomial time.

NP: It is the collection of decision problems that can be solved by a non-deterministic turing machine in polynomial time.

p-time reduction: Language L is polynomial-time reducible to language L2 when L<=pL2 polynomial-time computable function f:{0,1}{0,1} such that for all x{0,1}, xL1 iff f(x)L2.

NP-hard: Language L is NP-hard when LPL for every LNP

NP-complete: Language L is NP-complete when LNP and LPL for every LNP

Integer Factorization is an example of a problem in NP that is not known to be in P or to be NP-complete.

QUESTION 5 Teammate: Abhishek Reddy Punreddy P: It is the collection of decision problems that can be solved by a deterministic turing machine in polynomial time. NP: It is the collection of decision problems that can be solved by a non-deterministic turing machine in polynomial time. p-time reduction: Language L is polynomial-time reducible to language L2 when L<=pL2 polynomial-time computable function f:{0,1}⋆→{0,1}⋆ such that for all x∈{0,1}⋆, x∈L1 iff f(x)∈L2. NP-hard: Language L is NP-hard when L′≤PL for every L′∈NP NP-complete: Language L is NP-complete when L∈NP and L′≤PL for every L′∈NP Integer Factorization is an example of a problem in NP that is not known to be in P or to be NP-complete.

-- Practice Final May 16 2022

Venkat Teja Golamaru, Nimesh Nischal, Manasa Mananjaya

Give a 2-aproximation algorithm for Vertex Cover and show why it is a 2-approximation.

APPROX-VERTEX-COVER(G)

1 C=

2 E'= E[G]

3 while E'

4 let {u, v} be an arbitrary edge of E'

5 C = C {u, v}

6 Remove from E' every edge incident with either u or v

7 return C.

To see that the cover returned is at most twice the optimal, let A denote the set of edges that were picked in line 4. To cover the edges in A, any vertex cover (including the optimal C*) must include at least one endpoint of each edge in A. No two edges in A share an endpoint, so no two edges from A are covered by the same vertex from C*. So |C*| |A|. On the other hand |C| = 2|A|.

(Edited: 2022-05-16)

Venkat Teja Golamaru, Nimesh Nischal, Manasa Mananjaya 7. Give a 2-aproximation algorithm for Vertex Cover and show why it is a 2-approximation. APPROX-VERTEX-COVER(G) 1 C=∅ 2 E'= E[G] 3 while E' ≠ ∅ 4 let {u, v} be an arbitrary edge of E' 5 C = C ∪ {u, v} 6 Remove from E' every edge incident with either u or v 7 return C. To see that the cover returned is at most twice the optimal, let A denote the set of edges that were picked in line 4. To cover the edges in A, any vertex cover (including the optimal C*) must include at least one endpoint of each edge in A. No two edges in A share an endpoint, so no two edges from A are covered by the same vertex from C*. So |C*| ≥ |A|. On the other hand |C| = 2|A|.

-- Practice Final May 16 2022

((resource:IMG_6381.jpg|Resource Description for IMG_6381.jpg))

-- Practice Final May 16 2022

Group - Abhishek Vaid, Rishabh Pandey, Thomas Shen

(Edited: 2022-05-16)

Group - Abhishek Vaid, Rishabh Pandey, Thomas Shen((resource:20220516_172531.jpg|Resource Description for 20220516_172531.jpg))

-- Practice Final May 16 2022

Jatin Battu, Pradeep Narayana, Aditya Singhania

Problem 1:

*An online algorithm is said to be C-competitive if the ratio of the number of misses it makes divided by the number the optimal offline algorithm makes is C (length of the request sequence can be arbitrarily long.

*An online algorithm with a cache size of k has competitiveness >= k.

*We can show that this is the case for LRU. Assume that MIN is an optimal offline algorithm.

*We need to show that if k is the size of our cache and R is any request sequence, then FLRU(R)kFMIN(R)+k.

*After the first access, LRU and MIN always have at least the page just accessed in common.

*Consider a subsequence T of R not including the first access and during which LRU faults k times. Let p be the page accessed just before T. If LRU faults on the same page twice during T, then T must contain accesses to at least k+1 different pages. This is also true if LRU faults on p during T.

*If neither of these cases occurs, then LRU faults on at least k different pages, none of them p, during T. In any case, MIN must fault at least once during T.

*Partition R into R0,R1,... such that R0 contains the first access and at most k faults by LRU, and Ri for i=1,...,k contains exactly k faults by LRU. On each of the Ri's where i1, the ratio of LRU faults to MIN faults is at most k to 1.

*During R0, if LRU faults k times, MIN faults at least once. This gives the proof.

Jatin Battu, Pradeep Narayana, Aditya Singhania Problem 1: ---------- *An online algorithm is said to be C-competitive if the ratio of the number of misses it makes divided by the number the optimal offline algorithm makes is C (length of the request sequence can be arbitrarily long. *An online algorithm with a cache size of k has competitiveness >= k. *We can show that this is the case for LRU. Assume that ‘MIN’ is an optimal offline algorithm. *We need to show that if ‘k’ is the size of our cache and ‘R’ is any request sequence, then FLRU(R)≤k⋅FMIN(R)+k. *After the first access, LRU and MIN always have at least the page just accessed in common. *Consider a subsequence T of R not including the first access and during which LRU faults k times. Let p be the page accessed just before T. If LRU faults on the same page twice during T, then T must contain accesses to at least k+1 different pages. This is also true if LRU faults on p during T. *If neither of these cases occurs, then LRU faults on at least k different pages, none of them p, during T. In any case, MIN must fault at least once during T. *Partition R into R0,R1,... such that R0 contains the first access and at most k faults by LRU, and Ri for i=1,...,k contains exactly k faults by LRU. On each of the Ri's where i≥1, the ratio of LRU faults to MIN faults is at most k to 1. *During R0, if LRU faults k times, MIN faults at least once. This gives the proof.

-- Practice Final May 16 2022

Ayan Singh, Ivan Hernandez, Pranjali Bansod

Algorithm: Use a random coin flip to set the value of n variables to 0 or 1. As this is an instance of 7-SAT, this is a 128/127 approximation algorithm.

Resource Description for PracFinal 9.jpeg

(Edited: 2022-05-16)

Ayan Singh, Ivan Hernandez, Pranjali Bansod Algorithm: Use a random coin flip to set the value of n variables to 0 or 1. As this is an instance of 7-SAT, this is a 128/127 approximation algorithm. ((resource:PracFinal 9.jpeg|Resource Description for PracFinal 9.jpeg))

-- Practice Final May 16 2022

Likhitha Yelamanchili, Lakshmi Prasanna Gorrepati Problem 4

The encryption of RSA gives M ^ ed M mod p -> 1 similary in the decryption step we get M ^ ed M mod q -> 2 Because n = pq, In the correctness of RSA algorithm we use chinese remainder theorem to prove that using 1 and 2 we could generate M ^ ed M(modn)

While proving the correctness of Rabin Miller algorithm,Zn is not cyclic for a carmichael case and we know that n is an odd number that means the cases 2, 4, 2p^e are all ruled out.

Case 1: notice n can't be a prime power. To see this suppose n=p^e. Since n is odd, p must also be odd, so Zn will be cyclic, so has a generator g and by assumption we have g^(n1)1modn. On the other hand, ord(g)=(n)=(p1)p^(e1) and the discrete logarithm theorem implies n10mod(n). I. e., (p1)p^(e1)p^e1, which is impossible as the left hand-side is divisible by p, but the right hand side is not.

Case 2:So suppose n is odd, not a prime power and composite. We can then decompose it as n=n1n2 where n1 and n2 have different prime factors.

In case 1 where n is odd and to show that n can't be a prime power we are making use of the given theorem.

(Edited: 2022-05-16)

Likhitha Yelamanchili, Lakshmi Prasanna Gorrepati Problem 4 ----------------------------------------------------------------- The encryption of RSA gives M ^ ed ≡ M mod p -> 1 similary in the decryption step we get M ^ ed ≡ M mod q -> 2 Because n = pq, In the correctness of RSA algorithm we use chinese remainder theorem to prove that using 1 and 2 we could generate M ^ ed ≡ M(modn) While proving the correctness of Rabin Miller algorithm,Z*n is not cyclic for a carmichael case and we know that n is an odd number that means the cases 2, 4, 2*p^e are all ruled out. Case 1: notice n can't be a prime power. To see this suppose n=p^e. Since n is odd, p must also be odd, so Z⋆n will be cyclic, so has a generator g and by assumption we have g^(n−1)≡1modn. On the other hand, ord(g)=φ(n)=(p−1)p^(e−1) and the discrete logarithm theorem implies n−1≡0modφ(n). I. e., (p−1)p^(e−1)∣∣p^e−1, which is impossible as the left hand-side is divisible by p, but the right hand side is not. Case 2:So suppose n is odd, not a prime power and composite. We can then decompose it as n=n1⋅n2 where n1 and n2 have different prime factors. In case 1 where n is odd and to show that n can't be a prime power we are making use of the given theorem.

-- Practice Final May 16 2022

Damanpreet Kaur, Aditi Agrawal, and Gargi Sheguri Q6

Damanpreet Kaur, Aditi Agrawal, and Gargi Sheguri Q6 ((resource:34a544c5-2528-445f-9c42-0b2f28f256c3.jpg|Resource Description for 34a544c5-2528-445f-9c42-0b2f28f256c3.jpg))

-- Practice Final May 16 2022

Q8: Ajinkya Rajguru and Rushikesh Padia

Resource Description for Finals_q8.jpeg

(Edited: 2022-05-16)

Q8: Ajinkya Rajguru and Rushikesh Padia ((resource:Finals_q8.jpeg|Resource Description for Finals_q8.jpeg))