# 高等演算法 第 4 次作業
[PDF](https://ncueeclass.ncu.edu.tw/filedownload/999318)
> 備註：
> 1. 詳解可以用 <!-- (content) --> \<!-- (content) --> 註解起來
> 2. 寫在答案的盡量精簡 可以直接寫在試卷上？
> 3. 最好附上來源連結，用 [1](https://google.com) \!\[]() 語法
> 4. @cliffxzx 可以標注作者
1. For two points $p$ and $q$ in the plane, we say that $p$ dominates $q$ if both $x$ and $y$ coordinates of $p$ are no less than that of $q$ respectively. Given a set $S$ of $n$ points, the rank of a point $p$ in $S$ is the number of points in $S$ dominated by $p$. We want to find the rank of every point in $S$. A naïve algorithm needs $O(n^2)$ time. Design a faster algorithm for this problem. @cliffxzx
[Sweep line algorithm](https://web.ntnu.edu.tw/~algo/Point2.html) - [2D Rank Finding Problem](https://zerojudge.tw/ShowProblem?problemid=d847) | [1](https://lovenery.gitbooks.io/algorithm/content/ch3/3-divide-and-conquer.html), [2](https://github.com/c910335/2D-Rank-Finding-Problem), [3](http://blog.terrynini.tw/tw/Advance-Algorithm-homework4/)
- Step 1. Sort points by x-axis. If x-axis identity, compare y-axis.
- Step 2. Call `find_rank(p, 0, len(p))`
```=shell=
find_rank(p, l, r):
if r - l <= 1:
return [0]
i, li, ri = 0, 0, 0
pl = find_rank(p[:(r-l)/2])
pr = find_rank(p[(r-l)/2:])
while True:
if pl[li].y <= pr[ri].y:
p[i] = pl[li]
li += 1
if li >= len(pl):
for tmp in pr[ri:]:
rank[tmp.i] += li
p[i+1] = tmp
i += 1
break
else:
p[i] = pr[ri]
rank[pr[ri].i] += li
ri += 1
if ri >= len(pr):
p[i+1:] = pl[li:]
break
i += 1
return p
```
2. Assume there are $n$ supposedly identical VLSI chips that are capable of testing each other. There is a test jig that can accommodate two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the answer of a bad chip cannot be trusted. Show that the good chips can be identified with $O(n)$ pairwise tests, assuming that more than $n/2$ of the chips are good. @cliffxzx
[CLRS 4-5](https://walkccc.me/CLRS/Chap04/Problems/4-5/)
1. Pairwise test them, and leave the last one alone if the number of chips is odd.
- If the report says at least one of them is bad, throw both chips away;
- otherwise, throw one away from each pair.
2. Recursively find one good chip among the remaining chips. The recursion ends when the number of remaining chips is 1 or 2.
- If there is only 11 chip left, then it is the good chip we desire.
- If there are 2 chips left, we make a pairwise test between them. If the report says both are good, we can conclude that both are good chips. Otherwise, one is good and the other is bad and we throw both away. The chip we left alone at step 11 is a good chip.
3. A sequence $Z=z_1,z_2,...,z_k$ is a subsequence of $X=x_1,x_2,...,x_n$ if there exists a strictly increasing sequence $<i_1, i_2, ... , i_k>$of indices of X such that for all j = 1, 2,..., k, we have xij =zj. For example, Z = bcdb is a subsequence of X = abcbdab with corresponding index sequence <2, 3, 5, 7>. Design an algorithm that counts the number of occurrences of Z in X as a subsequence such that each has a distinct index sequence. @cliffxzx
[1](https://www.geeksforgeeks.org/count-distinct-occurrences-as-a-subsequence/), [2]()
```=shell=
solve(i, j, s, t) {
return 1 if j >= len(t)
return 0 if i >= len(s)
return f(i + 1, j + 1, s, t) + f(i + 1, j, s, t) if s[i] == t[j]
return f(i + 1, j, s, t);
}
```
4. Solve the edit distance and the alignment problems discussed in Unit-1. @cliffxzx
5. Given a sequence S of n nonnegative numbers x1, x2, ... , xn, and an integer k, partition S into k or fewer consecutive subsequences (i.e. substrings) such that the largest sum of these subsequences is minimized over all possible partitions.
6. Solve “Bitonic Euclidean traveling-salesman problem” in chapter 15 of the book [CLRS].
7. Solve “Printing neatly” in chapter 15 of the book [CLRS].
[考試推薦寫這個(簡短)](https://blog.csdn.net/wenlei_zhouwl/article/details/5992367)
[詳細](https://blog.csdn.net/yangtzhou/article/details/83451027?spm=1001.2101.3001.6650.8&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-8-83451027-blog-50647527.pc_relevant_aa2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7ERate-8-83451027-blog-50647527.pc_relevant_aa2&utm_relevant_index=16)
[CLRS](https://walkccc.me/CLRS/Chap15/Problems/15-4/)
[例題](https://davideliu.com/2019/12/22/print-neatly/)
8. Consider the activity-selection problem appears in p.42 of Unit-5. Now, assume that each given activity is associated with a positive weight. Design an algorithm to find an independent subset of activities (activities that can be allowed to use the same resource) whose sum of weights is maximized.
[weight activity-selection problem 中文](https://www.twblogs.net/a/5ef8e5b586592608d8f3a64c)
[weight activity-selection problem 英文](https://www.cs.princeton.edu/~wayne/cs423/lectures/dynamic-programming-4up.pdf)
9. Given a list of n positive integers d1, d2, ..., dn, we want to efficiently determine whether there exists a simple undirected graph whose nodes have degrees precisely d1, d2, ..., dn. Design an algorithm to solve this problem.
Step1:由大到小排序 dn ，選擇最大degree 的node當作x
Step2:x連結自己以外degree前幾大的點
Step3:去掉dn，d n-1當作x回到step2，直到沒有剩餘點
10. You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < ... < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination. You’d ideally like to travel 200 miles a day, but this may not be possible. If you travel x miles during a day, the penalty for that day is (200 - x)^2. You want to plan your trip so as to minimize the total penalty. Give an algorithm that determines the optimal sequence of hotels at which to stop.
P[i]紀錄從頭到ai的minimum total penalty
對所有j<i，利用P[i] = min(P[i], P[j] + (200 - (a[i] - a[j])) ** 2)更新最小值
```python
import sys
def hotel_stops_min_penalty(a):
# Let's define a0 = starting position = 0
a_ = a[:]
a_.insert(0, 0)
P = [ 0 for x in a_ ]
# Previous stop that minimizes the penalty at each mile stop
s = [ 0 for x in a_ ]
for i in range(1, len(a_), 1):
P[i] = sys.maxsize # initialize to infinity
for j in range(i):
# If we don't care about the actual stops, we can just use min as below
# P[i] = min(P[i], P[j] + (200 - (a[i] - a[j])) ** 2)
# Keep track of the previous stop that minimizes penalty at mile post i
p = P[j] + (200 - (a_[i] - a_[j])) ** 2
if p < P[i]:
s[i] = j
P[i] = p
stops = []
k = i
while k > 0:
stops.append(k)
k = s[k]
return (P[i], stops[::-1])
```
11. Find a way to implement the memory function discussed in the class. (See page 80 of Unit-5.)
[link text](https://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time)
12. Complete the branch-and-bound searching trees of DFS, BFS and Best-First Search methods for the TSP example in page 86 of Unit-5.
Sign in with Wallet
Connect another wallet