1.1-1 Give a real-world example that requires sorting or a real-world example that requires computing a convex hull. Solution: Finding the median of a set of values requires sorting. Finding a convex hull would be required to determine the small amount of fencing required to enclose a set of points (trees?) with a circular (or shape x) fence.
1.1-2 Other than speed, what other measures of efficiency might one use in a real-world setting? Solution: memory cost, bandwidth, etc.
1.1-3 Select a data structure that you have seen previously, and discuss is strengths and limitations. Solution: An array, dictionary, matrix, linked list
1.1-4 How are the shortest-path and traveling-salesman problems given above similar? Solution: The shortest path problem asks for a shortest route between two points on a graph. The travelling salesman asks for the shortest path that visits all points on the graph and returns to the starting point. The difference is that the first problem involves only two points whereas the second involves all points.
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. Solution: Calculating landing speed for an airplane, the trajectory of a missile or satellite, and the key to a crypto-system all require an exact solution. Approximate: statistics.
Introduction to Algorithms, 3rd
Cormen, Leiserson, Rivest, Stein
1.1 Exercises
No comments:
Post a Comment