Skip to content

Latest commit

 

History

History
73 lines (50 loc) · 3.57 KB

1.1.md

File metadata and controls

73 lines (50 loc) · 3.57 KB

Exercises 1.1-1

Give a real-world example that requires sorting or a real-world example that requires computing a convex hull

给出现实生活中需要排序的一个例子或者现实生活中需要计算凸壳的一个例子。

Answer

  • Amazon: Sort by price.
  • [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.

中文解答

  • 用到排序的应用很多，比如电商网站对商品按价格进行排序
  • 关于凸包，比如可以用来解决这个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

Array. Fast access; but it's slow to check if the array contains a specific element since we need to iterates the whole array.

中文解答

数组，访问速度快; 但是无法快速查询有没有某一个元素，需要遍历所有元素。

Exercises 1.1-4

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

前面给出的最短路径与旅行商问题有哪些相似之处？ 又有哪些不同

Answer

  • 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

中文解答

  • 相同点：都是在图中找一条路径
  • 不同点：最短路径只是求2个点之间的路径，但是旅行商问题要遍历全部点并且回到起点，是一个全排列问题.

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

  • only the best solution will do: You have 5 apples and you need to give those 5 apples to 5 people and everyone should have an apple.
  • a solution that is “approximately” the best is good enough: Calculate square root of 2.

中文解答

  • 最佳解：我们有5个苹果，分给5个人；最佳解只能是一人一个。
  • 次优解：比如说计算根号2，因为是无理数，没有一个完全的准确值。

Follow @louis1992 on github to help finish this task. You can also subscribe my youtube channel.