CSE310 Homework 1 Grading KeysPlease note that you have to typeset your assignment using either LATEX or Mi-crosoft Word. Hand-written assignment will not be graded. You need to submita hardcopy at the start of the lecture on the due date. You also need to submit anelectronic version at the digital drop box on the blackboard. For the electronic version,you should name your file using the format CSE310-HW01-LastName-FirstName.1. (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) seconds to solve an instance of a problem ofsize n. Fill the value n in the corresponding entry. Note that n has to be an integer.1 second 1 minute 1 hour 1 day 1 monthlog2n21 2602260∗602224∗60∗602230∗24∗60∗602n2+ 1000 0 0 50 292 1609n3+ 100n 0 0 13 43 1372n0 5 11 16 21Grading: 0.5 pts for each of the 20 entries.2. (10 pts) Let f(n) = 100n2+ 800n. Prove that f(n) ∈ Θ(n2).Proof: Let C1= 100, C2= 200, n0= 8. For all n > n0, we havef(n) = 100n2+ 800n ≥ C1× n2= 100n2> 0,f(n) = 100n2+ 800n ≤ C2× n2= 200n2.According to the definition, we have f(n) ∈ Θ(n2) and this proves the claim.Grading: The correctness in C1and C2is 3 pts each, and the correctness inn0is 2 pts for each direction.13. (10 pts) Prove that Θ(n2) + O(n3) ⊆ O(n3).Note that for this problem, you are proving that the set of functions on theleft hand side (LHS) is a subset of the set of functions on the right hand side(RHS). The set on the LHS is the algebraic sum of two sets (not the union):an element of the LHS has the form f(n) = f1(n)+f2(n), where f1(n) ∈ Θ(n2)and f2(n) ∈ O(n3).Proof: Let f(n) be any function in the set of LHS. According to the defini-tion, there must be two functions g(n) ∈ Θ(n2) and h(n) ∈ O(n3) such thatf(n) = g(n) + h(n). Since g(n) ∈ Θ(n2), there are positive constants cg1andcg2along with big integer Ngsuch thatcg1× n2≤ g(n) ≤ cg2× n2≤ cg2× n3is true for all n ≥ Ng. Since h(n) ∈ O(n3), there is a positive constant chalong with a big integer Nhsuch thath(n) ≤ ch× n3is true for all n ≥ Nh. Therefore for all n ≥ max{Ng, Nh}, we haveg(n) + h(n) ≤ (cg2+ ch) × n3.This proves that f(n) ∈ RHS, and thus proves the claim.Grading: 4 pts for knowing the structure that f(n) can be rewritten as asummation of two functions; 2 pts for each correct upper bound, which arecg2, ch, and cg2+ ch, respectively.24. (10 pts) Prove that Θ(n2) + O(n3) 6= O(n3).Proof: If we choose f(n) = 1, obviously, f(n) is an element of RHS. However,f(n) /∈ Θ(n2) + O(n3), since there is no positive constant c1and integer Nsuch that for all n ≥ N,f(n) = 1 ≥ c1× n2is true. So f(n) is not an element of LHS, and thus we know Θ(n2) + O(n3) 6=O(n3).This completes the proof.Grading: 5 pts for finding the correct f(n), 5 pts for correctness of the proof.5. (10 pts) Prove that 3n6∈ Θ(2n).Proof: Sincelimn→∞3n2n=limn→∞(32)n= ∞.Hence, for any C > 0, there exists a positive integer N such that3n2n> Cfor all n ≥ N is true.This proves 3n6∈ O(2n), thus proves that 3n6∈ Θ(2n).Grading: 5 pts for knowing limn→∞3n2n= ∞, 5 pts for proving it
View Full Document
Unlocking...