solution
-
[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..
-
[Introduction to Algorithms, CLRS] Exercise 1.1-4알고리즘 2017. 8. 14. 13:44
This is a solution for Introduction to Algorithms. I write this for my study purpose. 1.1-4 How are the shortest-path and traveling-salesman problems given above similar? How are they different? Similarity: They are similar in the sense that both traverses a graph and tries to find out the path with minimum sum of the weights. Difference: The TSP requires one to find the simple cycle covering ev..