CSE310 HW01 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 before the lecture on the due date You also need to submit an electronic version at the digital drop box For the electronic version you should name your file using the format HWxy LastName FirstName 1 10 pts Let f n n3 and g n 100 n log2 n Find the smallest integer N 1 such that 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 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 microseconds to solve an instance of a problem of size n Fill the value n in the corresponding entry 1 second n 1012 n 106 n2 103 2n 19 1 minute 36 1014 6 107 7745 25 1 hour 1296 1016 36 108 6 104 31 1 day 746496 1016 864 108 293939 36 1 year 9945 1023 31536 109 5615690 44 Grading 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 1 is equal to the set of functions on the right hand side RHS The set on the LHS is 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 n and f2 n O n1 5 Solution Because f1 n n there exist positive constants c1 c2 N such that for any integer n N1 c1 n f1 n c2 n Because f2 n O n1 5 there exist positive constants c3 N2 such that for any integer n N2 f2 n c3 n1 5 Let N3 max N1 N2 Thus when n N3 f n f1 n f2 n c2 n c3 n1 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 n50 n 2n n50 0 lim n 2n 0 50n49 50n48 lim lim n n2n 1 n 2n 1 lim 50 48 2n 0 1 n 2n 25 lim Thus there exists an integer N such that for any integer n N definition 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 50 10 pts if they use limn n2n 0 2 n50 2n 1 According to the 5 10 pts Prove that nn 3 6 n 3 n Solution We prove it by contradiction Assume that nn 3 n 3 n Thus there exist positive constants c1 c2 and N1 such that when n N1 c1 n 3 n nn 3 c2 n 3 n However we also have the following derivation n 3 n 1 1 3 lim 3 1 n e3 lim 3 0 n 3 n n n n n n n lim This indicates that there exists a positive constant N2 when n N2 1 n 3 n 1 nn 3 2c2 c2 nn 3 c2 n 3 n 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 limit 3 1
View Full Document
Unlocking...