2022-05-16
Practice Final May 16 2022.
Parth Mehta, Sneh Kothari, William Wang
Problem 2
Euclid(a, b):
Euclid(125, 45) -> return Euclid(45, 125 mod 45) -> Euclid(45, 35)
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
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<=pL2polynomial-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.
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.
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|.
(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|.
((resource:IMG_6381.jpg|Resource Description for IMG_6381.jpg))
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))
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.
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.
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.
(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))
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
------------------------------------------------------------- The encryption of RSA gives M ^ ed ≡ M mod p -> 1 similary in the decryption step we get
M ^ ed ≡ M mod q -> 2Because 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.
(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.
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))
Q8: Ajinkya Rajguru and Rushikesh Padia
(Edited: 2022-05-16) Q8: Ajinkya Rajguru and Rushikesh Padia
((resource:Finals_q8.jpeg|Resource Description for Finals_q8.jpeg))
(c) 2024 Yioop - PHP Search Engine