CSE310 HW02 Grading KeysPlease note that you have to typeset your assignment using either LATEX or MicrosoftWord. Hand-written assignment will not be graded. You need to submit a hardcopybefore the lecture on the due date. You also need to submit an electronic version atthe digital drop box. For the electronic version, you should name your file using theformat CSE310-HW02-LastName-FirstName.1. (10 pts) Algorithm A for solving problem P has a time complexity TA(n) for an instance ofsize n. We do not know the asymptotic order of TA(n). However, we know that TA(n) =7 · TA(n/2) + 8n2. Algorithm B for solving problem P has a time complexity TB(n) for aninstance of size n. We do not know the asymptotic order of TB(n). However, we know thatTB(n) = 8 ·TB(n/2) + n2.Compute the asymptotic orders for TA(n) and TB(n) using the master method. You need tospecify a, b, logba, and decide the case. You also need to write the derived conclusion.Which algorithm is asymptotically faster?Answer:For TA(n), a = 7, b = 2, logba = log27∼=2.8074. Choose ε = 0.5, logba − ε∼=2.3074,f(n) = O(n2.3074). Thus TA(n) belongs to case 1, TA(n) = Θ(nlog27)∼=Θ(n2.8074).For TB(n), a = 8, b = 2, logba = 3. Choose ε = 1, logba − ε = 2, f(n) = O(n2). Thus TB(n)belongs to case 1, TB(n) = Θ(nlog28) = Θ(n3).Since n2.8074< n3, TA(n) is asymptotically faster than TB(n).Grading:4 pts for calculating TA(n) (1 pt for a, b, and logba; 2 pts for the case; 1 pt for the conclusion).4 pts for calculating TB(n) (1 pt for a, b, and logba; 2 pts for the case; 1 pt for the conclusion).2 pts for knowing that Algorithm A is faster than Algorithm B.2. (10 pts) T (n) = 5 · T (n/5) + 0.001n +√n log2n. Use the master method to solve T (n). Youneed to specify a, b, logba, and decide the case. You also need to write the derived conclusion.Answer:a = 5, b = 5, logba = 1.Since limn→∞0.001n+√nlog2nn= 0.001 + limn→∞log2n√n= 0.001, f(n) = Θ(n). Thus, T (n) belongs tocase 2.Therefore, T (n) = Θ(nlogbalg n) = Θ(n lg n).1Grading:3 pts for correctly specifying a, b, and logba.4 pts for deciding the right case.3 pts for calculating T (n) correctly.3. (10 pts) T (n) = 7 ·T (n/2) + n2.85. Use the master method to solve T (n). You need to specifya, b, logba, and decide the case. You also need to write the derived conclusion.Answer:a = 7, b = 2, logba = log27∼=2.8074. Choose ε = 0.04, logba + ε∼=2.8474. f(n) = n2.85=Ω(n2.8474).a·f(n/b) = 7(n/2)2.85=722.85n2.85∼=0.9709n2.85, Choose c = 0.98 < 1, then a·f(n/b) ≤ c·f(n)for ∀n ≥ 0. Thus, T (n) belongs to case 3.Therefore, T (n) = Θ(f(n)) = Θ(n2.85).Grading:3 pts for correctly specifying a, b, and logba.4 pts for deciding the right case.3 pts for calculating T (n) correctly.4. (10 pts) T (n) = 3 · T (n/3) + n2. Use the master method to solve T (n). You need to specifya, b, logba, and decide the case. You also need to write the derived conclusion.Answer:a = 3, b = 3, logba = 1. Choose ε = 1, logba + ε = 2. f(n) = n2= Ω(nlogba+ε).a ·f(n/b) =39n2∼=0.3333n2. Choose c = 0.5 < 1, then a ·f(n/b) ≤ c ·f(n) for ∀n ≥ 0. Thus,T (n) belongs to case 3.Therefore, T (n) = Θ(f(n)) = Θ(n2).Grading:3 pts for specifying a, b, and logba.4 pts for deciding the right case.3 pts for calculating T (n) correctly.5. (10 pts) Given the sequenceA[1]=50, A[2]=40, A[3]=30, A[4]=20, A[5]=10.2List all of the inversions in the sequence.Answer:h1, 2i, h1, 3i, h1, 4i, h1, 5i, h2, 3i, h2, 4i, h2, 5i, h3, 4i, h3, 5i, h4, 5i.Grading:1 pt for each
View Full Document
Unlocking...