CSE310 HW02 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 CSE310 HW02 LastName FirstName 1 10 pts Algorithm A for solving problem P has a time complexity TA n for an instance of size 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 an instance of size n We do not know the asymptotic order of TB n However we know that TB n 8 TB n 2 n2 Compute the asymptotic orders for TA n and TB n using the master method You need to specify a b logb a 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 logb a log2 7 2 8074 Choose 0 5 logb a 2 3074 2 3074 log2 7 2 8074 f n O n Thus TA n belongs to case 1 TA n n n For TB n a 8 b 2 logb a 3 Choose 1 logb a 2 f n O n2 Thus TB n belongs to case 1 TB n nlog2 8 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 logb a 2 pts for the case 1 pt for the conclusion 4 pts for calculating TB n 1 pt for a b and logb a 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 log2 n Use the master method to solve T n You need to specify a b logb a and decide the case You also need to write the derived conclusion Answer a 5 b 5 logb a 1 n 2 0 001 f n n Thus T n belongs to Since lim 0 001n n nlog2 n 0 001 lim log n n n case 2 Therefore T n nlogb a lg n n lg n 1 Grading 3 pts for correctly specifying a b and logb a 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 specify a b logb a and decide the case You also need to write the derived conclusion Answer a 7 b 2 logb a log2 7 2 8074 Choose 0 04 logb a 2 8474 f n n2 85 n2 8474 7 n2 85 a f n b 7 n 2 2 85 22 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 logb a 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 specify a b logb a and decide the case You also need to write the derived conclusion Answer a 3 b 3 logb a 1 Choose 1 logb a 2 f n n2 nlogb a a f n b 93 n2 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 logb a 4 pts for deciding the right case 3 pts for calculating T n correctly 5 10 pts Given the sequence A 1 50 A 2 40 A 3 30 A 4 20 A 5 10 2 List 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 inversion 3
View Full Document
Unlocking...