Solutions
-
[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.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-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..