전체 글
-
[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..
-
[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..
-
[Introduction to Algorithms, CLRS] Exercises 2.2-1알고리즘 2017. 11. 25. 20:06
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.2-1 Express the function n3 / 1000 - 100n2 - 100n + 3 in terms of Θ notation. Answer: The answer’s going to be Θ(n^3). (n to the 3) Writing e for the original expression, Θ(e) = Θ(max(n^3/1000, −100n^2, −100n, 3)). This will equal to Θ(max(n^3 , n^2 , n, 1)). As Θ(1) < Θ(n) < Θ(n^2 ) < Θ(n^3 ), Θ(ma..