Skip to content

1.1 Algorithms

1.1-1

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

  • Sorting: browse the price of the restaurants with ascending prices on NTU street.
  • Convex hull: computing the diameter of set of points.

1.1-2

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

Memory efficiency and coding efficiency.

1.1-3

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

Linked-list:

  • Strengths: insertion and deletion.
  • Limitations: random access.

1.1-4

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

  • Similar: finding path with shortest distance.
  • Different: traveling-salesman has more constraints.

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.

  • Best: find the GCD of two positive integer numbers.
  • Approximately: find the solution of differential equations.