Algorithms
-
[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
-
[Introduction to Algorithms, CLRS] Exercise 1.1-1알고리즘 2017. 8. 14. 12:14
This is a solution for Introduction to Algorithms. I write this for my study purpose. 1.1-1 Give a real-world example that requires sorting or a real-world example that re- quires computing a convex hull. Answer: 1) Sorting: - Contact list in my smart phone, alphabetically sorted. - Email list in Gmail app, sorted in time. 2) Convex Hull: (I think this is the most interesting answer that I found..