Exercises
-
[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-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-2알고리즘 2017. 12. 9. 15:52
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.2-2Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1] . Then find the second smallest element of A, and exchange it with A[2] . Continue in this manner for the first n-1 elements of A. Write pseudocode for this algorithm..