國立中興大學應用數學系

演算法 Algorithms

111-02 學期 Midterm Exam

日期: 2022.04.19

時間: 10:10-12:00~12:30

地點: U517

學號:________________________

姓名:________________________

1
1 (24%)

2 (10%)

3 (10%)

4 (10%)

5 (16%)

6 (10%)

7 (10%)

8 (10%)

總分

2
 1. Selection sort
(12%)
Fill answers in blanks in “Best case” column of the table.
Selection sort Cost Time complexity Best case
1 Input: an array A[0..n-1] of n items 0
output: A[0..n-1] sorted in descending
2 0
order
3 for i = 0 to n-2 c1 𝑛 𝑛
/* set current element as
4 0
minimum*/
5 min = i c2 𝑛−1 𝑛−1
/* check the element to be
6 0
minimum */
𝑛−2 𝑛−2

7 for j = i+1 to n-1 c3 ∑ 𝑡𝑗 ∑(𝑡𝑗 = 𝑛 − 1 − 𝑗 + 1)

𝑗=0 𝑗=0
𝑛−2 𝑛−2

8 if A[j] < A[min] then c4 ∑ 𝑡𝑗 ∑(𝑡𝑗 = 𝑛 − 1 − 𝑗)

𝑗=0 𝑗=0
𝑛−2 𝑛−2

9 min = j; c5 ∑ 𝑡𝑗 ∑(𝑡𝑗 = 0)
𝑗=0 𝑗=0

10 end if 0

11 end for 0
/* swap the minimum element with the
12 0
current element*/
13 swap A[min] and A[i] c6 𝑛−1 𝑛−1
14 end for 0

3
 (12%)
Fill answers in blanks in “worst case” column of the table.
Selection sort Cost Time complexity Worst case
1 Input: an array A[0..n-1] of n items 0
output: A[0..n-1] sorted in descending
2 0
order
3 for i = 0 to n-2 c1 𝑛 𝑛

/* set current element as

4 0
minimum*/
5 min = i c2 𝑛−1 𝑛−1

/* check the element to be

6 0
minimum */
𝑛−2 𝑛−2

7 for j = i+1 to n-1 c3 ∑ 𝑡𝑗 ∑(𝑡𝑗 = 𝑛 − 1 − 𝑗 + 1)

𝑗=0 𝑗=0
𝑛−2 𝑛−2

8 if A[j] < A[min] then c4 ∑ 𝑡𝑗 ∑(𝑡𝑗 = 𝑛 − 1 − 𝑗)

𝑗=0 𝑗=0
𝑛−2 𝑛−2

9 min = j; c5 ∑ 𝑡𝑗 ∑(𝑡𝑗 = 𝑛 − 1 − 𝑗)
𝑗=0 𝑗=0

10 end if 0

11 end for 0
/* swap the minimum element with the
12 0
current element*/
13 swap A[min] and A[i] c6 𝑛−1 𝑛−1
14 end for 0

4
2. Time complexity
(10%)
Use mathematical induction to show that when n is an exact power of 2, the solution of
the following recurrence is 𝑇(𝑛)=nlgn.
2 𝑖𝑓 𝑛 = 2,
𝑇(𝑛) = { 𝑛
2𝑇 ( ) + 𝑛 𝑖𝑓 𝑛 = 2𝑘 , 𝑘 ≥ 1
2
Answer:
• Basic step (1%):

𝑇(2) = 2 lg 2 = 2 ⋅ 1 = 2

• Assumption (2%):

𝑛 𝑛 𝑛
Suppose 𝑇 ( ) = lg , then 𝑇(𝑛) = 𝑛 lg 𝑛
2 2 2

• Induction (7%):

Method 1.
𝑛 𝑛 𝑛 𝑛
𝑇(𝑛) = 2𝑇 ( ) + 𝑛 = 2 ( lg ) + 𝑛 = 𝑛 lg + 𝑛 = 𝑛(lg 𝑛 − lg 2) + 𝑛
2 2 2 2
= 𝑛 lg 𝑛 − 𝑛 + 𝑛 = 𝑛 lg 𝑛

Method 2.
𝑛 𝑛 𝑛
Let 𝑛 = 2𝑘 . According to assumption 𝑇 ( ) = lg = 2𝑘−1 (𝑘 − 1)
2 2 2

𝑛
𝑇(𝑛) = 2𝑇 ( ) + 𝑛 = 2 (2𝑘−1 (𝑘 − 1)) + 2𝑘 = 2𝑘 ⋅ 𝑘 = 𝑛 lg 𝑛
2

5
3. Using changing variable method to solve the recurrence T (10%)

T(𝑛) = 2T(√𝑛) + lg n

Answer:
Let 𝑚 = lg 𝑛 , 𝑛 = 2𝑚 , then
𝑇(𝑛) = 2𝑇(√𝑛) + lg 𝑛 ⇒ 𝑇(2𝑚 ) = 2𝑇(2𝑚/2 ) + 𝑚
Let 𝑆(𝑚) = 𝑇(2𝑚 ), then
𝑚
𝑇(2𝑚 ) = 2𝑇(2𝑚/2 ) + 𝑚 ⇒ 𝑆(𝑚) = 2𝑆 ( ) + 𝑚
2
Solving 𝑆(𝑚):
𝑚 𝑚 𝑚
𝑆(𝑚) = 2𝑆 ( ) + 𝑚 = 22 𝑆 ( 2 ) + 2𝑚 = 23 𝑆 ( 3 ) + 3𝑚
2 2 2
𝑘=lg 𝑚 𝑚
= ⋯ = 2𝑘 𝑆 ( 𝑘 ) + 𝑘𝑚 = 𝑚𝑆(1) + 𝑚 lg 𝑚 ∈ Θ(𝑚 lg 𝑚)
2
Therefore,
𝑇(2𝑚 ) ∈ Θ(𝑚 lg 𝑚) ⇒ 𝑇(𝑛) ∈ Θ(lg 𝑛 ⋅ lg(lg 𝑛))

6
4. (10%)

Partition(A, p, r)
1 x  A[r]
2 i  p-1
3 for j p to r-1
4 do if A[j]  x
5 then i  i+1
6 exchange A[i]A[j]
7 exchange A[i+1]A[r]
8 return i+1
Fill in the following Table, while using above Algorithm to partition the list,

2, 8, 7, 1 ,3, 5,6, 4,

for the first round.

7
 i p,j r
(a)

(b) p,i j r

(c) p,i j r

(d) p,i j r

(e) p i j r

(f) p i j r

(g) p i j r

(h)
p i r
(i)
p i r

8
5. (16%)
2
To analyze the cost of the calls to insertion sort, let 𝑛𝑖 be the random variable denoting
the number of elements placed in bucket B[i]. The running time of bucket sort is
𝑛

𝑇(𝑛) = 𝜃(𝑛) + ∑ 𝑂(𝑛𝑖2 )

𝑖=1
Analyze the average-case running time of bucket sort, by computing the expected value of
the running time. That is, prove that E[T(n)] = 𝜃(𝑛).

𝐸[𝑇(𝑛)] = 𝐸[𝜃(𝑛) + ∑𝑛𝑖=1 𝑂(𝑛𝑖2 )]=𝜃(𝑛) + ∑𝑛𝑖=1 𝐸[𝑂(𝑛𝑖2 )] = 𝜃(𝑛) + ∑𝑛𝑖=1 𝑂(𝐸[𝑛𝑖2 ])
1
(1) Prove that 𝐸[𝑛𝑖2 ] = 2 − (10%)
𝑛
(2) Prove that E[T(n)] = 𝜃(𝑛) by (1) and 𝐸[𝑇(𝑛)] = 𝜃(𝑛) + ∑𝑛𝑖=1 𝑂(𝐸[𝑛𝑖2 ]). (6%)

Answer(1):
Method 1.
In average case, each bucket B[i] has the same value of 𝐸[𝑛𝑖2 ], since each value in input
array 𝐴 is equally likely to fall in any bucket. Define indicator random variable
𝑋𝑖𝑗 = 𝐼{𝐴[𝑗] fall in bucket 𝐵[𝑖]}
for 𝑖 = 0, … , 𝑛 − 1 and 𝑗 = 1, … , 𝑛.
Thus, 𝑛𝑖 = ∑𝑛𝑗=1 𝑋𝑖𝑗
To compute 𝐸[𝑛𝑖2 ], expand the square and regroup terms:
2
𝑛 𝑛 𝑛 𝑛 𝑛 𝑛

𝐸[𝑛𝑖2 ] = 𝐸 [(∑ 𝑋𝑖𝑗 ) ] = 𝐸 [∑ ∑ 𝑋𝑖𝑗 𝑋𝑖𝑘 ] = 𝐸 ∑ 𝑋𝑖𝑗2 + ∑ ∑ 𝑋𝑖𝑗 𝑋𝑖𝑘

𝑗=1 𝑗=1 𝑘=1 𝑗=1 1≤𝑗≤𝑛 1≤𝑘≤𝑛
[ 𝑘≠𝑗 ]
𝑛 𝑛 𝑛

= ∑ 𝐸[𝑋𝑖𝑗2 ] + ∑ ∑ 𝐸[𝑋𝑖𝑗 𝑋𝑖𝑘 ] (5.1)

𝑗=1 1≤𝑗≤𝑛 1≤𝑘≤𝑛
𝑘≠𝑗
1
Since probability that 𝐴[𝑗] is in bucket 𝐵[𝑖] is ,
𝑛
1 1 1
𝐸[𝑋𝑖𝑗2 ] = 12 ⋅ + 02 ⋅ (1 − ) =
𝑛 𝑛 𝑛
When 𝑘 ≠ 𝑗, the variables 𝑋𝑖𝑗 and 𝑋𝑖𝑘 are independent. Hence,
1 1 1
𝐸[𝑋𝑖𝑗 𝑋𝑖𝑘 ] = 𝐸[𝑋𝑖𝑗 ]𝐸[𝑋𝑖𝑘 ] = ⋅ = 2
𝑛 𝑛 𝑛
Substituting these two expected in equation (5.1),
𝑛 𝑛 𝑛
2
1 1 1 1 𝑛−1 1
𝐸[𝑛𝑖 ] = ∑ + ∑ ∑ 2 = 𝑛 ⋅ + 𝑛(𝑛 − 1) ⋅ 2 = 1 + =2−
𝑛 𝑛 𝑛 𝑛 𝑛 𝑛
𝑗=1 1≤𝑗≤𝑛 1≤𝑘≤𝑛
𝑘≠𝑗

9
Method 2.
Let 𝐴[𝑗] be 𝑗-th element in the input array, 𝑗 = 1, … , 𝑛.
Let 𝑝𝑖𝑗 be probability that 𝐴[𝑗] is in bucket 𝐵[𝑖]
1 , 𝑖𝑓 𝐴[𝑗] is in bucket 𝐵[𝑖]
Let 𝑋𝑖𝑗 ∼ 𝐵𝑒𝑟𝑛𝑜𝑢𝑙𝑙𝑖(𝑝𝑖𝑗 ), where 𝑋𝑖𝑗 = { .
0 , 𝑖𝑓 𝐴[𝑗] is not in bucket 𝐵[𝑖]
By definition, number of elements placed in bucket B[i] is 𝑛𝑖 = ∑𝑛𝑗=1 𝑋𝑖𝑗 .
1
In average case 𝑝𝑖𝑗 = , ∀𝑖, 𝑗. According to property of Bernoulli distribution,
𝑛
𝑛𝑖 = ∑𝑛𝑗=1 𝑋𝑖𝑗 ∼ 𝐵𝑖𝑛𝑜𝑚𝑖𝑎𝑙(𝑛, 1/𝑛 ). Hence,
2 2
1 1 2
1 2 1
𝐸[𝑛𝑖 ] = 𝑉𝑎𝑟[𝑛𝑖 ] + 𝐸[𝑛𝑖 ] = 𝑛 ( ) (1 − ) + 𝑛 ( ) = 2 −
𝑛 𝑛 𝑛 𝑛

Answer(2):
1
𝐸[𝑇(𝑛)] = 𝜃(𝑛) + ∑𝑛𝑖=1 𝑂(𝐸[𝑛𝑖2 ]) = 𝜃(𝑛) + 𝑛 (2 − ) = 𝜃(𝑛)
𝑛

10
6. (10%)
HEAPIFY takes O(h). It means that the cost of HEAPIFY on a node i is proportional
to the height of the node i in the tree. Prove that an asymptotically tight upper bound
𝑇(𝑛) = ∑ℎ𝑖=1 𝑛𝑖 ℎ𝑖 // Cost of HEAPIFY at level i  number of nodes at that level
where
ℎ𝑖 = ℎ − 𝑖: height of the heap rooted at level i, and
𝑛𝑖 = 2𝑖 ∶ number of nodes at level i.
Height Level No. of nodes

h0 = 3 (lgn) i=0 20

h1 = 2 i=1 21

h2 = 1 i=2 22

h3 = 0 i = 3 (lgn) 23

Prove that 𝑇(𝑛) = ∑ℎ𝑖=1 𝑛𝑖 ℎ𝑖 = ∑ℎ𝑖=1 2𝑖 (ℎ − 𝑖) = 𝑂(𝑛)

Answer:
Method 1.
ℎ ℎ ℎ ℎ−1
ℎ−𝑖 𝑘
𝑇(𝑛) = ∑ 𝑛𝑖 ℎ𝑖 = ∑ 2𝑖 (ℎ − 𝑖) = ∑ ℎ−𝑖 2ℎ = 2ℎ ∑ 𝑘 (6.1)
2 2
𝑖=1 𝑖=1 𝑖=1 𝑘=0

where 𝑘 = ℎ − 1. Since,
∞ 1 ∞ ∞
𝑘 𝑘 𝑘 1 3 3 𝑘 1
∑ 𝑘 = ∑ 𝑘 + ∑ 𝑘 ≤ + ∑ ( ) ≤ + 3 = 𝑂(1) (6.2)
2 2 2 2 4 4 2
𝑘=0 𝑘=0 𝑘=2 𝑘=0
𝑘+1
2𝑘+1 𝑘+1 3
where 𝑘 = ≤ 𝑖𝑓 𝑘 ≥ 2.
2𝑘 4
2𝑘
∞ ∞ ∞
(6.1) 𝑘 𝑘 𝑘 (6.2)
⇒ 𝑇(𝑛) = 2ℎ [∑ 𝑘 − ∑ 𝑘 ] ≤ 2ℎ ∑ 𝑘 = 𝑛 × 𝑂(1) = 𝑂(𝑛)
2 2 2
𝑘=0 𝑘=ℎ 𝑘=0

11
Method 2.
Let 𝑡 = ∑ℎ𝑖=1 2𝑖 (ℎ − 𝑖), then
ℎ+1 ℎ

2𝑡 − 𝑡 = ∑ 2𝑖 (ℎ − 𝑖 + 1) − ∑ 2𝑖 (ℎ − 𝑖)
𝑖=2 𝑖=1
ℎ ℎ ℎ

= 2ℎ+1 (ℎ − (ℎ + 1) + 1) + [∑ 2𝑖 (ℎ − 𝑖)] + [∑ 2𝑖 ] − [∑ 2𝑖 (ℎ − 𝑖)]

𝑖=2 𝑖=2 𝑖=1
ℎ

= [∑ 2𝑖 ] − 2(ℎ − 1) = 2ℎ+1 − 22 − 2(ℎ − 1) = 𝑂(2ℎ ) = 𝑂(𝑛)

𝑖=2

12
7. Draw the results in the step-by-step way while running the maximum-subarray algorithm
to array A = [20, -7, 12, -5, -22, 15, -4, 7]. The format is like as below Figure. (10%)

L MSS: Left maximum subarray sum

R MSS: Right maximum subarray sum
b: cross maximum sum
MSS: Maximum subarray sum

20 -7 12 -5 -22 15 -4 7

20 -7 12 -5 -22 15 -4 7

20 -7 12 -5 -22 15 -4 7

20 -7 12 -5 -22 15 -4 7

L MSS = 12 L MSS = -4
L MSS = 20 L MSS = -22
R MSS = -5
20 -7 12 -5 -22 15
R MSS = 7
-4 7
R MSS = -7 R MSS = 15
b=7 b=3
b = 13 b = -7
MSS = 12 MSS = 7
MSS = 20 MSS = 15

L MSS =15
L MSS = 20 20 -7 12 -5 -22 15 -4 7
R MSS = 7
R MSS = 12
b = 15 + 3 =18
b = 13 + 12 = 25
MSS = 18
MSS = 25
20 -7 12 -5 -22 15 -4 7
L MSS = 25

R MSS = 18

b = 20 + (-4) = 16

MSS = 25

13
8. Counterfeit currency problem (n coin problem) (10%)
Among the n coins with the same appearance, one of the n coins is a counterfeit coin, and
it is known that the counterfeit coin has a different weight from the real coin. Let the
counterfeit coin be lighter than the real coin.

(1) Using Divide and Conquer to devise the following recurrent algorithm for the problem.
Please fill out the blanks in the following table.

Inputs: An array of weights S indexed from 1 to n. S[j] indicates the weight of the jth coin
in the set of n coins

Outputs: the location of the counterfeit coin in the array S

1 int location (int l, int h) {

2 If ( h - l <= 1){

if( S[l] > S[h]) return h; else return l; }

3 else {

4 mid = ⌊(low+ high)/2⌋;

5 If ( WeightSum[l, mid] < WeightSum[mid+1, h])

6 location (l, mid );

7 else

8 location (mid+1, h);

9 }

10 }

11 int WeightSum(i, j){

12 return S[i]+…+S[j] }

(2) Show and solve the recurrence relation T(n) for above algorithm
Answer:
𝑐=Θ(1) 𝑘=lg 𝑛 𝑛
𝑇(𝑛) = 𝑇(𝑛/2) + Θ(1) = 𝑇(𝑛/2) + 𝑐 = 𝑇(𝑛/4) + 2𝑐 = ⋯ = 𝑇 ( 𝑘 ) + 𝑐𝑘
2
𝑇(1)=1
= 𝑇(1) + 𝑐 lg 𝑛 = 𝑂(lg 𝑛)

14