전체 글
-
[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..
-
[Introduction to Algorithms, CLRS] Exercise 1.2-2알고리즘 2017. 8. 15. 11:25
This is a solution for Introduction to Algorithms. I write this for my study purpose. 1.2-2 Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort? Answer: So the question is when the following will be....
-
[Introduction to Algorithms, CLRS] Exercise 1.2-1알고리즘 2017. 8. 15. 11:10
This is a solution for Introduction to Algorithms. I write this for my study purpose. 1.2-1 Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved. Answer: 1. Search engine requires algorithmic optimization of natural language processing (NLP) to determine the probability that someone will type 'give an ex..