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