CSE310 HW02 Thursday 02 04 2010 Due Thursday 02 11 2010 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 HW02 LastName FirstName 1 10 pts T n 6 T n 2 f n where f n 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 Solution For this recurrence we have a 6 b 2 f n n and thus we have that nlogb a nlog2 6 Since f n n n O nlog2 6 where 1 we can apply case 1 of the master theorem and conclude that the solution is T n nlog2 6 Grading Keys 1 pt for a 1 pt for b 1 pt for writing correct function f n 5 pts for justifying the right case 2 pts for conclusion 2 10 pts T n 3 T n 3 8n 100 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 Solution For this recurrence we have a 3 b 3 f n 8n 100 n and thus we have that nlogb a nlog3 3 n Since f n nlog3 3 we can apply case 2 of the master theorem and conclude that the solution is T n n log n Grading Keys 1 pt for a 1 pt for b 1 pt for writing correct function f n 5 pts for justifying the right case 2 pts for conclusion 1 3 10 pts T n 7 T n 2 n3 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 Solution For this recurrence we have a 7 b 2 f n n3 and nlogb a nlog2 7 Since f n n3 nlog2 7 where 0 1 case 3 applies if we can show that the regularity condition holds for f n For sufficiently large n a f n b 7 n3 23 c f n where c 7 8 Consequently by case 3 the solution to the recurrence is T n n3 Grading Keys 1 pt for a 1 pt for b 1 pt for writing correct function f n 5 pts for justifying the right case 2 pts for conclusion 3 pts will be cut off if there is no justification of regularity condition 3 pts will be cut off if there is no claim that f n nlog2 7 4 10 pts Given the sequence 8 7 3 1 4 List all of the inversions in the sequence Solution We sequentially label the elements of the sequence with index i i 1 2 3 4 5 According to the definition of inversion all the inversions in this sequence are 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 Grading Keys 1 pt for each correct inversion 5 pts will be cut off if you do not use index representation 5 10 pts Let A be an array of n integers We say element i is out of order with its left neighbor if either i 1 and A i 1 A i If we know that n is huge and that there are only 4 elements that are out of order with its left neighbor Between quick sort and insertion sort which is the better algorithm for sorting array A Justify your answer Solution Between quick sort and insertion sort insertion sort is the better algorithm for sorting array 2 A This is because that array A is an almost sorted array That is to say most elements in array A are in their right place since array A has just 4 elements which are out of order It is the best case for insertion sort while the worst case for quick sort In this scenario the number of inversions in this array is O n so the time complexity of insertion sort is n O n n however the time complexity of quick sort is n log n Grading Keys 6 pts for correct choice 1 pt for correct number of inversions 1 pt for correct time complexity of insertion sort 2 pts for correct time complexity of quick sort 3
View Full Document
Unlocking...