전체 글
-
[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:
-
[Introduction to Algorithms, CLRS] Problems 1.1알고리즘 2017. 8. 26. 17:07
This is a solution for Introduction to Algorithms. I write this for my study purpose. Problems 1-1 Comparison of running timesFor each function f .n/ and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f .n/ microseconds. Answer:We assume a 30 day month and 365 day year. I use '^' for 't..
-
[Introduction to Algorithms, CLRS] Exercise 1.2-3알고리즘 2017. 8. 15. 12:31
This is a solution for Introduction to Algorithms. I write this for my study purpose. 1.2-3 What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine? Answer: A (quadratic time complexity) will run much faster than B (exponential time complexity) for very large values of n. Let’s start checking fr..