알고리즘
-
[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..
-
[Introduction to Algorithms, CLRS] Exercise 1.1-5알고리즘 2017. 8. 15. 09:39
This is a solution for Introduction to Algorithms. I write this for my study purpose. 1.1-5 Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is “approximately” the best is good enough. Answer: Sorting a catalog is the problem, where only the best solution will do. An "approximately" sorted catalog won't be useful. Finding t..
-
[Introduction to Algorithms, CLRS] Exercise 1.1-4알고리즘 2017. 8. 14. 13:44
This is a solution for Introduction to Algorithms. I write this for my study purpose. 1.1-4 How are the shortest-path and traveling-salesman problems given above similar? How are they different? Similarity: They are similar in the sense that both traverses a graph and tries to find out the path with minimum sum of the weights. Difference: The TSP requires one to find the simple cycle covering ev..
-
[Introduction to Algorithms, CLRS] Exercise 1.1-3알고리즘 2017. 8. 14. 13:19
This is a solution for Introduction to Algorithms. I write this for my study purpose. 1.1-3 Select a data structure that you have seen previously, and discuss its strengths and limitations. Answer: I would like to introduce 2 data structures: singly linked list and array. Data structure Strengths Limitations Singly linked list - It does not need sequential space in memory. - We can insert a new ..
-
[Introduction to Algorithms, CLRS] Exercise 1.1-2알고리즘 2017. 8. 14. 12:40
This is a solution for Introduction to Algorithms. I write this for my study purpose. 1.1-2 Other than speed, what other measures of efficiency might one use in a real-world setting? - Memory (what if your application needs 2TB memory?) - Network Traffic - Database Access source: https://htrinity.wordpress.com/2015/07/10/clrs-chapter-1-solutions/ http://clrs.skanev.com/01/01/02.html