# Algorithm Design Manual Chapter 1

## Book Notes

### Combinatorial Objects

• Permutations - arrangements, or orderings, of items (“arrangement” “tour” “ordering” or “sequence” )
• Subsets - selections from a set of items (“cluster” “collection” “committee” “group” “packaging” or “selection”)
• Trees - hierarchical relationships between items (“hierarchy” “dominance relationship” “ancestor/descendant relationship” or “taxonomy”)
• Graphs - relationships between arbitrary pairs of objects (“network” “circuit” “web” or “relationship”)
• Points - locations in some geometric space (“sites” “positions” or “locations.)
• Polygons - regions in some geometric spaces (“shapes” “regions” or “boundaries”)
• Strings - sequences of characters or patterns. (“text” “characters” “patterns” or “labels”)

### Recursive Objects

Big things that are made from smaller things of exactly the same type as the big thing. A decomposition rule describes how to get smaller things from big things.

As all combinatorial objects above are recursive objects here are a few possible decompositon rules for them:

• Permutations - Deleting the first/last element of a permutation
• Subsets - Deleting an element n if present
• Trees - Deleting the root (results in a set of subtrees), deleting a leaf (a smaller tree)
• Graphs - Deleting a vertex, dividing vertices to groups
• Point - divide them to groups
• Polygons - Inserting any internal chord between two nonadjacent vertices
• Strings - Deleting a character (first or last)

## Exercises

### 1-28.

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

void DivideCore(int m, int n, int *quot, int *rem) {
rem = m;
quot = 0;
while (rem >= n) {
rem -= n;
quot++;
}
}

void Divide(int m, int n, int *quot, int *rem) {
int mult_n = 0;
int last_n;
while (m % n == 0) {
last_n = n;
n = n + n;
mult_n++;
}
DivideCore(m, n, quot, rem);
for (int i = 0; i < mult_n; ++i) {
quot = quot + quot;
}
}


### 1-29.

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.

7 次。

1. 5 次：25 匹分成 5 组，比赛 5 次，得到前 5 名。
2. 6 次：前 5 名比赛一次。因为只要得到前 3 名，这里剔除 5 名中的 2 名，剩下的 3 匹按比赛排名所在组为 G1，G2，G3。
3. 7 次：G3 组只能去角逐第 3 名，派第一名 G31,G2 组只能去角逐第 2,3 名，派第一，二名，G21 和 G22。G1 组 G11 已经是第一名，去角逐第 2,3 名，派 G12,G13。最后 G12,G13，G21，G22 和 G31，得到第二，三名。

### 1-30.

How many piano tuners are there in the entire world?

1. 世界的人口。
2. 拥有钢琴的人口比例。
3. 拥有钢琴的学校，教堂等场所的数量。

1. 每架钢琴平均多久需要调音一次。
2. 对钢琴调音需要多长时间。
3. 调音师的工作时间。
4. 世界人口 70 亿，70×109
5. 人口中弹奏乐器的人约占 10%（肯定大于 1%,小于 100%），其中最多 10%的人弹奏钢琴，而其中拥有钢琴的比例为 2%-3%，约人口总数 2×10-3 。每 5000-10000 个人有一座教堂，每座教堂有一架钢琴，每 500-1000 个学生有一所学校，每所学校有一架钢琴，每人大约拥有 3×10-3 架钢琴，所以钢琴数 70×109 × 3×10-3 = 2.1 * 108
6. 钢琴调音的频率低于每月一次但多于 10 年一次，估计为一年一次。
7. 调音所需时间多余 30 分钟，少于 1 天，估计为 2 小时。或钢琴有 88 个键，如果每个键花 1 分钟，需要 1.5 小时，若需 2 分钟，则需要 3 小时。
8. 每天工作 8 小时，每周 5 天，每年工作 50 周，得出 8×5×50=2000 小时。2000 小时能调音大学 1000 架钢琴。
9. 2.1 * 108 / 1000 = 2.1 × 105 个调音师。

### 1-31.

How many gas stations are there in the United States?

1. 每天大约有多少辆汽车去加油。
2. 每天一个加油站能给多少辆汽车加油。
3. 美国人口总数约 300×106 , 一家平均有 2 辆车左右，所以一共有车辆 150×106 ，每辆汽车每 5 天加油一次，一天有 30×106 辆车去加油。
4. 一个加油站平均每小时最少为 1 辆，最多 100 多辆汽车加油，取平均 20-30 辆每小时，一个加油站工作时间大概 14 小时（7am-9am），每个加油站每天平均大约为 280 辆车加油。
5. 30×106 / 280 = 1.07 × 105 个加油站。

### 1-32.

How much does the ice in a hockey rink weigh?

1. 冰的体积。
2. 冰的密度。

V = 70 * 30 * 0.1 = 210 m3 W = 210 *1000 = 210，000kg

### 1-33.

How many miles of road are there in the United States?

### 1-34.

On average, how many times would you have to flip open the Manhattan phone book at random in order to find a specific name?