전체 글
-
[Introduction to Algorithms, CLRS] Exercises 2.3-6알고리즘 2018. 4. 20. 16:41
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.3-6Observe that the while loop of lines 5–7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[1 . . j - 1]. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to Θ..
-
[Introduction to Algorithms, CLRS] Exercises 2.3-5알고리즘 2018. 4. 13. 18:37
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.3-5 Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the r..
-
[Introduction to Algorithms, CLRS] Exercises 2.3-4알고리즘 2018. 2. 10. 18:38
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.3-4 We can express insertion sort as a recursive procedure as follows. In order to sort A[1 . . n] , we recursively sort A[1 . . n] and then insert A[n] into the sorted array A[1 . . n-1] . Write a recurrence for the running time of this recursive version of insertion sort. Answer: There are two ste..
-
[Introduction to Algorithms, CLRS] Exercises 2.3-3알고리즘 2018. 1. 27. 20:57
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.3-3 Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrenceis T(n) = nlgn. Answer: For base case, when n = 2, T(2) = 2lg2 = 2 When we suppose there's a n=2^k, such that k > 1, and it holds this equation, if n=2^(k+1) holds the equation too, then we can s..
-
[Introduction to Algorithms, CLRS] Exercises 2.3-2알고리즘 2017. 12. 30. 20:11
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.3-2 Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A. Answer: MERGE(A, p, q, r) 1 n1 = q - p + 1 2 n2 = r - q 3 let L[1..n1 + 1] and R[1..n2..
-
[Introduction to Algorithms, CLRS] Exercises 2.2-4알고리즘 2017. 12. 24. 20:05
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.2-4How can we modify almost any algorithm to have a good best-case running time? Answer:We can design any algorithm to treat its best-case scenario as a special case and return a predetermined solution. For example, for selection sort, we can check whether the input array is already sorted and if it..
-
[Introduction to Algorithms, CLRS] Exercises 2.2-3알고리즘 2017. 12. 23. 17:51
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.2-3 Consider linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case runni..