Introduction to Algorithms
-
[Introduction to Algorithms, CLRS] Problems 2.1알고리즘 2018. 4. 20. 18:47
This is a solution for Introduction to Algorithms. I write this for my study purpose. Problems 2-1 Insertion sort on small arrays in merge sort Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n^2) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the l..
-
[Introduction to Algorithms, CLRS] Exercises 2.3-7알고리즘 2018. 4. 20. 18:10
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.3-7 Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is x. Answer:To make the answer a Θ(n lg n)-time algorithm, we need to sort the set S, otherwise, we cannot achieve Θ(n lg n). If we just..
-
[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-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..