ContextQMD
Back to Clrs

1.1

C01-The-Role-of-Algorithms-in-Computing/1.1.md

latest2.5 KB
Original Source

Exercises 1.1-1

Give a real-world example in which one of the following computational problems appears: sorting, determining the best order for multiplying matrices, or finding the convex hull.

Answer

  • 用到排序的应用很多，比如电商网站对商品按价格进行排序
  • The multiplication process in computers are time consuming than addition process. If we have three or more matrices to multiply, then we should check the order in which to multiply to reduce the number of multiplications.
  • [From Wiki]The problem of finding convex hulls finds its practical applications in pattern recognition, image processing, statistics, geographic information system, game theory, construction of phase diagrams, and static code analysis by abstract interpretation. It also serves as a tool, a building block for a number of other computational-geometric algorithms such as the rotating calipers method for computing the width and diameter of a point set. also application in CV.

Exercises 1.1-2

Other than speed, what other measures of efficiency might one use in a real-world setting?

Answer

内存使用，资源占用（网络，磁盘等） Memory requirement, Degree of parallelism, Resource use( cpu or gpu cycles, Disk IO etc), Accessibility(Cloud/local)

Exercises 1.1-3

Select a data structure that you have seen previously, and discuss its strengths and limitations.

Answer

数组，访问速度快，不能动态调整大小.

Exercises 1.1-4

How are the shortest-path and traveling-salesman problems given above similar? How are they different?

Answer

  • 相同点：都是在图中找一条路径
  • 不同点：最短路径只是求2个点之间的路径，但是旅行商问题要遍历全部点并且回到起点，是一个全排列问题.
  • In travelling salesman problem we want to know an order of delivery of stops that yields "lowest overall distance" travelled .
  • This "lowest overall distance" is similar to shortest path finding situation .
  • Shortest path is polynomially solvable but travelling -salesman is NP-Complete

Exercises 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

这题好抽象 0 0 求根如果是无理数近似就行了找不到最优的.

Follow @louis1992 on github to help finish this task.