算法导论第三版 第1章答案
1.The role of Algorithm in Computing
1.1 Algorithms
1.Give a real-world example that requires sorting or a real-world example that requires computing a convex hull.
An example of a data set that might need sorting is an online store's sale items by largest discount. An example of a convex hull that would need computing is a set of co-ordinates in which we want to find the shortest travel time to.
2.Other than speed, what other measures of efficiency might one use in a real-world setting?
Memory usage and other resources such as I/O consumption, network consumption, disk consumption, power consumption, etc.
3.Select a data structure that you have seen previously, and discuss its strengths and limitations.
Let's take the singly-linked list.
Strengths:
- It does not need sequential space in memory
- We can insert a new element at any place with O(1)
Limitations:
- Random access is O(n)
- It takes additional memory for the links
4.How are the shortest-path and traveling-salesman problems given above similar? How are they different?
They are similar, because each of then has to walk a graph and find a path in them.
The difference is the constraint on the solution. The shortest-path requires just a path between two points, while the traveling salesman requires a path between more points that returns to the first point.
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.
Sorting a catalog is a problem, where only the best solution will do. An "approximately" sorted catalog won't be that useful.
Finding the shortest path between two points in a city is a problem, where good-enough will do. It might not be the fastest way, but you will still get there.
1.2 Algorithms as a technology
1.Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.
Google Maps when finding a route between two places.The algorithms are an essential part of this use case, since the route is what the user cares for the most.
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 steps, while merge sort runs in 64nlgn steps. For which values of n does insertion sort beat merge sort?
When n < 44, insertion sort beats merge sort. When , merge sort beats insertion sort.
3.What is the smallest value of n such that an algorithm whose running time is runs faster than an algorithm whose running time is
on the same machine?
When n >14, the first algorithm runs faster.
Problems
1.Comparison of running times:For 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.
Note: lgn is the best while the n! is the worst.