CSE310 Homework 1 Grading Keys Please note that you have to typeset your assignment using either LATEX or Microsoft Word Hand written assignment will not be graded You need to submit a hardcopy at the start of the lecture on the due date You also need to submit an electronic 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 column index in the following table determine the largest size n of a problem that can be solved in time t assuming that the algorithm takes f n seconds to solve an instance of a problem of size n Fill the value n in the corresponding entry Note that n has to be an integer 1 second log2 n2 1 2 n 1000 0 n3 100n 0 n 2 0 1 minute 1 hour 60 60 60 22 2 2 0 50 0 13 5 11 1 day 24 60 60 2 2 292 43 16 1 month 30 24 60 60 2 2 1609 137 21 Grading 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 have f 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 C1 and C2 is 3 pts each and the correctness in n0 is 2 pts for each direction 1 3 10 pts Prove that n2 O n3 O n3 Note that for this problem you are proving that the set of functions on the left 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 definition there must be two functions g n n2 and h n O n3 such that f n g n h n Since g n n2 there are positive constants cg1 and cg2 along with big integer Ng such that cg1 n2 g n cg2 n2 cg2 n3 is true for all n Ng Since h n O n3 there is a positive constant ch along with a big integer Nh such that h n ch n3 is true for all n Nh Therefore for all n max Ng Nh we have g 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 a summation of two functions 2 pts for each correct upper bound which are cg2 ch and cg2 ch respectively 2 4 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 c1 and integer N such that for all n N f n 1 c1 n2 is 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 3n 6 2n Proof Since n limn 32n limn 32 n n Hence for any C 0 there exists a positive integer N such that 23n C for all n N is true This proves 3n 6 O 2n thus proves that 3n 6 2n n Grading 5 pts for knowing limn 32n 5 pts for proving it correctly 3
View Full Document
Unlocking...