CS6363 Fall 2023 HW1 Solution Tan Lam September 11 2023 1 Problem 1 15 pts Problem Problem 2 4 Inversions p 41 Text Let A 1 n be an array of n distinct numbers If i j and A i A j then the pair i j is called an inversion of A a List the five inversions of the array 2 3 8 6 1 2 pts b What array with elements from the set 1 2 n has the most inver sions How many does it have 3 pts c What is the relationship between the running time of insertion sort and the number of inversions in the input array Justify your answer 5 pts d Give an algorithm that determines the number of inversions in any permu tation on n elements in n log n worst case time Hint Modify merge sort 5 pts Answer cid 1 n n 1 2 a The five inversions are 1 5 2 5 3 4 3 5 and 4 5 Remember that inversions are specified by indices rather than by values in the array b The array n n 1 n 2 2 1 has the most number of inversions 2 The number of inversions is cid 0 n Then cid 80 n insertion sort is cid 80 n c The running time of insertion sort is a constant times the number of inversions Let I i denote the number of j i such that A j A i i 1 I i equals the number of inversions in A Now consider the while loop on lines 5 7 of the insertion sort algorithm The loop will execute once for each element of A which has index less than j is larger than A j Thus it will execute I j times We reach this while loop once for each iteration of the for loop so the number of constant time steps of j 1 I j which is exactly the inversion number of A d We ll call our algorithm M Merge Sort for Modified Merge Sort In addi tion to sorting A it will also keep track of the number of inversions The 1 algorithm works as follows When we call M Merge Sort A p q it sorts A p q and returns the number of inversions in the elements of A p q so lef t and right track the number of inversions of the form i j where i and j are both in the same half of A When M Merge A p q r is called it returns the number of inversions of the form i j where i is in the first half of the array and j is in the second half Summing these up gives the total number of inversions in A The runtime is the same as that of Merge Sort because we only add an additional constant time operation to some of the iterations of some of the loops Since Merge is nlogn so is this algorithm Algorithm 1 M Merge Sort A p r 1 if p q then 2 q p q 2 lef t M Merge Sort A p q right M Merge Sort A q 1 r inv M Merge A p q r lef t right return inv 3 4 5 6 7 end 8 return 0 2 Algorithm 2 M Merge A p q r 1 inv 0 2 n1 q p 1 3 n2 r q 4 Let L 1 n1 and R 1 n2 be new arrays 5 for i 1 to n1 do L i A p i 1 6 7 end 8 for j 1 to n2 do R j A q j 9 10 end 11 i 1 j 1 k p 12 while i n1 1 and j n2 1 do if L i R j then A k L i i i 1 else A k R j inv inv j j j 1 end k k 1 21 22 end 23 if i n1 1 then 24 for m j to n2 do A k R m k k 1 end 27 28 end 29 if j n2 1 then 30 for m i to n1 do 13 14 15 16 17 18 19 20 25 26 31 32 33 k k 1 end 34 35 end 36 return inv 3 inversions between the left and right arrays This keeps track of the number of A k L m inv inv n2 exhausted the right array element of the right array contributes an inversion Tracks inversions once we have At this point every 2 Problem 2 10 pts Problem Compare the following pairs of functions f n g n in terms of or der of magnitude In each case determine whether f n O g n f n g n and orf n g n Give a brief justification for your answers 1 f n 0 1n1 05 log log n g n 100n log n 5 3 pts 2 f n log n log log n g n n1 5 log n 4 pts 3 f n n42n 8 g n 4n 3 pts Answer 1 f n 0 1n1 05 log log n g n 100n log n 5 f n n1 05 g n n Hence f n g n 2 f n log n log log n g n n1 5 log n Let m log n then n 2m f n mlog m g n 21 5 m m cid 19 cid 18 m mlog m cid 19 n cid 18 1 21 5m f n g n Then lim n lim m Hence f n O g n 3 f n n42n 8 g n 4n n42n 8 f n g n lim n Hence f n O g n lim n 4n lim n 2 28n4 0 cid 32 cid 33 lim m m 2log2 m 21 5m 0 4 1 Show that cn o log log n n for any constant c 5 pts 3 Problem 3 10 pts Problem 2 Show that cid 80 n Answer i 1 ik is nk 1 5 pts cid 18 cid 19 n cn 1 log log n n lim n lim n Hence cn o log log n n c log log n 0 2 We have ik 1k 2k nk cid 16 n cid 17 k 2 n cid 88 i 1 n cid 88 n cid 88 i 1 i 1 nk ik n nk nk ik n nk nk ik nk 1 cid 17 k 2 i 1 n cid 88 cid 17 k cid 16 n cid 17 cid 16 n cid 16 n cid 17 k 1 cid 16 n n cid 88 2 2 2 i 1 ik nk 1 5 4 Problem 4 10 pts Problem Problem 7 4 2 p 184 Text Show that quicksort s best case running time is n log n Answer We ll use the substitution method to show that the best case running time is n log n Let T n be the best case …
View Full Document
Unlocking...