CSE310 HW01 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 HWxy-LastName-FirstName.1. (10 pts) Let f(n) = n3and g(n) = 100 × n × log2n. Find the smallest integer N ≥ 1 suchthat f(N ) ≤ g(N) but f (N + 1) > g(N + 1). Show the values of N, f (N), g(N), f(N + 1)and g(N + 1).Solution:N = 20, f(N) = 8000, g(N ) = 8643.86, f (N + 1) = 9261, g(N + 1) = 9223.87.Grading Keys:6 pts for N ;1 pt for each of the other values.2. (10 pts) For each function f(n) (the row index in the following table) and time t (the columnindex in the following table), determine the largest size n of a problem that can be solved intime t, assuming that the algorithm takes f (n) microseconds to solve an instance of a problemof size n. Fill the value n in the corresponding entry.1 second 1 minute 1 hour 1 day 1 year√n 101236 × 10141296 × 1016746496 × 10169945 × 1023n 1066 × 10736 × 108864 × 10831536 × 109n21037745 6 × 104293939 56156902n19 25 31 36 44Grading Keys:0.5 pt for each entry. If dicimal number is used, take off 1 pt from final score.3. (10 pts) Prove that Θ(n) + O(n1.5) ⊆ O(n1.5).Note that for this problem, you are proving that the set of functions on the left hand side (LHS)1is equal to the set of functions on the right hand side (RHS). The set on the LHS is algebraicsum of two sets (not the union): an element of the LHS has the form f(n) = f1(n) + f2(n),where f1(n) ∈ Θ(n) and f2(n) ∈ O(n1.5).Solution: Because f1(n) ∈ Θ(n), there exist positive constants c1, c2, N such that for anyinteger n > N1, c1n ≤ f1(n) ≤ c2n. Because f2(n) ∈ O(n1.5), there exist positive constantsc3, N2such that for any integer n > N2, f2(n) ≤ c3n1.5. Let N3= max{N1, N2}. Thus,when n > N3, f (n) = f1(n) + f2(n) ≤ c2n + c3n1.5. Let c4= c2+ c3, we thus have f (n) ≤c4× n1.5, (n > N3) ⇒ f(n) = O(n1.5). Therefore, Θ(n) + O(n1.5) ⊆ O(n1.5).Grading Keys:2 pts for deriving the constants and inequality for f1(n);2 pts for deriving the constants and inequality for f2(n);2 pts for claiming c, N and deriving the inequality for f(n);4 pts for correctly deriving the constants and inequality for f(n).4. (10 pts) Prove that n50= O(2n).Solution: We have limit as follows:limn→∞n502n= limn→∞(n50)0(2n)0= limn→∞50n49n2n−1= limn→∞50n482n−1...= limn→∞50 × 48 × ··· × 2n2n−25= 0 < 1Thus, there exists an integer N, such that for any integer n > N ,n502n< 1. According to thedefinition of big-O, we have n50= O(2n).Grading Keys:6 pts for claiming the existence of c and N without proving;10 pts if the claim above is proved;10 pts if they use limn→∞n502n= 0.25. (10 pts) Prove that nn+36= Θ((n + 3)n).Solution: We prove it by contradiction. Assume that nn+3= Θ((n + 3)n). Thus, there existpositive constants c1, c2and N1such that when n > N1, c1(n + 3)n≤ nn+3≤ c2(n + 3)n.However we also have the following derivation:limn→∞(n + 3)nn(n+3)= limn→∞1n3(1 +3n)n= e3× limn→∞1n3= 0This indicates that there exists a positive constant N2, when n > N2,(n + 3)nnn+3≤12c2<1c2⇒nn+3> c2(n + 3)n(1)Inequality (1) contradicts with our assumption. Thus the claim holds.Grading Keys:2 pts for knowing to use proof by contradiction;3 pts for specifying the false assumption;5 pts for correct use of
View Full Document
Unlocking...