The Algorithm Design Manual Exercise Chapter 1

1-1. [3] Show that a + b can be less than min(a, b).

a = -2 , b = -3

1-2. [3] Show that a × b can be less than min(a, b).

a = -2, b = 3

1-3. [5] Design/draw a road network with two points a and b such that the fastest route

between a and b is not the shortest route.

  a ----------- c ----------- b
   \                         /
    \--------- d ---------- /

a->c->b 只要三十分鐘。距離比較遠。

a->d->b 比較近，但因為塞車，花35分。

1-5. [4] The knapsack problem is as follows: given a set of integers S = {s1, s2, . . . , sn}, and a target number T, find a subset of S which adds up exactly to T. For example, there exists a subset within S = {1, 2, 5, 9, 10} that adds up to T = 22 but not T = 23. Find counterexamples to each of the following algorithms for the knapsack problem.

That is, giving an S and T such that the subset is selected using the algorithm does not leave the knapsack completely full, even though such a solution exists.

(a) Put the elements of S in the knapsack in left to right order if they fit, i.e. the

first-fit algorithm.

S = {1,2,3,4}, T = 7 永遠只會選{1,2,3}

(b) Put the elements of S in the knapsack from smallest to largest, i.e. the best-fit

algorithm.

S = {1,2,3,4}, T = 7 永遠只會選{1,2,3}

(c) Put the elements of S in the knapsack from largest to smallest.

S = {5,4,2}, T = 6

1-6. [5] The set cover problem is as follows: given a set of subsets S1, ...,Sm of the

universal set U = {1, ...,n}, find the smallest subset of subsets T ⊂ S such that ∪ti∈T ti = U. For example, there are the following subsets, S1 = {1, 3, 5}, S2 = {2, 4}, S3 = {1, 4}, and S4 = {2, 5} The set cover would then be S1 and S2.

Find a counterexample for the following algorithm: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered.

U = {1,2,3,4}, S1 = {1,2,3} S2 = {1,2}, S3 = {3,4} 

Interview Problems

1-28. Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.

void division(int a, int b){

    int cnt = 0;

    while(a >= b){

        a -= b;

        cnt++;
    }

    return cnt;

}

1-29. [5] There are 25 horses. At most, 5 horses can race together at a time. You must determine the fastest, second fastest, and third fastest horses. Find the minimum number of races in which this can be done.

七次。

25隻馬，分成五個群組各比一次，之後每個群組派最快的出來比就知道這當中的1,2,3名，此第一名為整題第一，其中2,3並非整體的排名。接著要拿原先第一名群組的其他馬、和第二名的其他馬(包括第二名)與第三名那隻馬比較。

打嘴砲

1-31. [3] How many gas stations are there in the Taiwan?

假設台灣有200000部車，每部車一個禮拜要加一次油，

加油站開12小時，及加油站每一小時可以加十部車。12*10 = 120

因此200000 / 120 約等於 1700個加油站。

1-33. [3] How many miles of road are there in the Taiwan?

假設台灣為長方形，長400km、寬200km，台灣大多為山，扣掉一半因此可以看成，長200km和寬100km的長方形，在假設每個網格為1km圍成的正方形道路，因此會有，200條100km的道路和100條200km的道路，故道路長為100*200 + 200*100 =40000 km

※台灣公路遍及台灣及澎湖地區各鄉鎮，公路系統依公路法規定分為國道、省道、縣道/市道、鄉道/區道、專用公路共五級，總長度41,475公里（2014年止）。除以上五級公路外，其餘為一般道路，道路又分由水土保持局管理的農路、由林務局管理的林道、位於都市計劃區內的市區道路（含市區快速道路、巷弄）和其它普通產業道路及私人道路。 Wiki