🐶The Role of Algorithms in Computing

1.1 exercise

1.1-1 Describe your own real-world example that requires sorting. Describe one that requires finding the shortest distance between two points.

1.1-2 Other than speed, what other measures of efficiency might you need to consider in a real-world setting?

1.1-3 Select a data structure that you have seen, and discuss its strengths and limitations.

1.1-4 How are the shortest-path and traveling-salesperson problems given above similar? How are they different?

1.1-5 Suggest a real-world problem in which only the best solution will do. Then come up with one in which “approximately” the best solution is good enough.

1.1-6 Describe a real-world problem in which sometimes the entire input is available before you need to solve the problem, but other times the input is not entirely available in advance and arrives over time.

1.2 exercise

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.

1.2-2 Suppose that for inputs of size n on a particular computer, insertion sort runs in $8n^2$steps and merge sort runs in $64n lg n$ steps. For which values of $n$ does insertion sort beat merge sort?

1.2-3 What is the smallest value of n such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$on the same machine?

Problems1-1

对于下表中的每个函数 $f(n)$ 和时间 $t$，确定在时间 $t$ 内可以解决的问题的最大大小 $n$，假设解决问题的算法需要 $f (n)$ 微秒。