알고리즘
-
[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..
-
[Introduction to Algorithms, CLRS] Exercises 2.1-4알고리즘 2017. 11. 25. 17:10
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.1-4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1)-element array C . State the problem formally and write pseudocode for adding the two integers. Answer: - Problem: Input: Two n..
-
[Introduction to Algorithms, CLRS] Exercises 2.1-3알고리즘 2017. 9. 16. 17:32
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.1-3 Consider the searching problem: Input: A sequence of n numbers A = and a value v. Output: An index i such that v = A[i] or the special value NIL if v does not appear in A. Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your..
-
[Introduction to Algorithms, CLRS] Exercises 2.1-2알고리즘 2017. 9. 3. 20:01
This is a solution for Introduction to Algorithms. I write this for my study purpose. Exercises 2.1-2 Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non- decreasing order. Answer: INSERTION-SORT (A) 1 for j = 2 to A.length 2 key = A[j] 3 // Insert A[j] into the sorted sequence A[1..j-1]. 4 i =j - 1 5 while i >0 and A[i]
-
[Introduction to Algorithms, CLRS] Exercises 2.1-1알고리즘 2017. 8. 28. 18:40
This is a solution for Introduction to Algorithms. I write this for my study purpose. Excercises 2.1-1 Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A = {31, 41, 59, 26, 41, 58}. Answer: