國立中興大學應用數學系

演算法 Algorithms

111-02 學期 Final-term Exam

日期: 2022.06.08

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

地點: U414

學號:________________________

姓名:________________________

1
1 (20%)

2 (20%)

3 (20%)

4 (20%)

5 (20%)

6 (20%)

7 (20%)

8 (20%)

總分

2
1. Red-Black Tree: Insertion (20%)

Insert node 1 (pointer z points to) with RED in the RBTree T.

T 11

T 2
11 14
Black node z

1 3
3 14
Red node 15

2 7 y 7
y
15
z

1
5 8 5 8

1-(c) Answer

3
2. Red-Black Tree: Deletion (20%)

Case 1: x’s sibling w is red

Case 2: x’s sibling w is black, and both of w’s children are black

Case 3: x’s sibling w is black, w’s left child is red, and w’s right child is black

Case 4: x’s sibling w is black, and w’s right child is red

E
Red
node

D F

Delete 19 from the following RB tree.

2-(a) (2%): What case of this deletion? Case 3, Case 4

2-(b) (6%)(6%)(6%): Draw the three results while performing the deletion?

16

2
4

4
3. B-tree (20%)

dedelete
delete

3-(a) (3%): What case of deleting 2 from the above B tree? Case 1. Since

there are enough keys in the node, just delete it.

3-(b) (7%): Draw the result of the deletion.

3-(c) (3%): What case of deleting 52 from the above B tree? Case 2b. Borrow

the successor.

3-(d) (7%): Draw the result of the deletion.

5
4. Minimal Spanning Tree (MST)

MST-PRIM(G, w, r)

1 for each u ∈ G.V

2 u.key = ∞;

3 u. 𝜋= NIL

4 r.key = 0

5 Q= G.V
6 while Q ≠ ∅
7 u = EXTRACT-MIN(Q)
8 for each v ∈ G.Adj[u]
9 if v ∈ Q and w(u, v) < v.key
10 V.𝜋 =U
11 v.key = w(u, v)
12 Change-Priority (Q, v, v.key)

Do MST-PRIM(G, w, r) to fill in the following table.

6
# Extract- Key/𝝅 Root
for- Min(u) of P.Q.
a b c d e f g h i
each
0 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ a
nil nil nil nil nil nil nil nil nil
1 a 4 ∞ ∞ ∞ ∞ ∞ 8 ∞ b
a nil nil nil nil nil a nil
2 b 8 ∞ ∞ ∞ ∞ 8 ∞ c
b nil nil nil nil a nil
3 c 7 ∞ 4 ∞ 8 2 i
c nil c nil a c
4 i 7 ∞ 4 6 7 f
c nil c i i

5 f 7 10 2 7 g

c f f i
6 g 7 10 1 h
c f g
7 h 7 10 d
c f
8 d 9 e
d

7
5. Direct Acyclic Graph (DAG) (20%)
r 3
0
G
5

Draw the DAG of Graph G if starting vertex r.

5-(a)(10%) Show the result of doing DFS(G), like figure (a). That is a DFS forest. Show
the starting and finishing time stamp beside each vertex.
(2%)

1/12
r 3 3/10 4/5 1/12
0 r 3 3/10 4/5
G 0
G
5
5 Tree edge
-2
Back edge
2/11
2/11 Forward edge
2
Cross edge

6/9 7/8 6/9 7/8

5-(b) (10%) Show the result of DAG(G) by the answer of question 5-(a).
5
3
-4

0     7 
5 6 8 9
r s t y z x

7 -3

8
6 Shortest-Path: Bellman-Ford for DAG (20%)

Do Bellman-Ford (G, w, r) for the DAG in Question 5 and fill in the following Table.
Choose vertex by ascending (A to Z) alphabetical order.

BELLMAN-FORD(G, w, s)
DAG-SHORTEST-PATHS(G, w, s)
1. INITIALIZE-SINGLE-SOURCE (V, s)
2. for i ← 1 to |G.V| - 1 1. topologically sort the vertices of G
3. do for each edge (u, v)  G.E 2. INI TIALIZE-SIN GLE-SOURCE (G, s)
4. do RELAX(u, v, w)
5. for each edge (u, v)  G.E 3. for each vertex u, taken in topologically sorted order
6. do if d[v] > d[u] + w (u, v) 4. for each vertex v  G.Adj[ u]
7. then return FALSE
8. return TRUE 5. RELAX(u, v, w)

(u, v) r s t x y z
r s 0 5 ∞ ∞ ∞ ∞
nil r nil nil nil nil
t 𝟎 5 3 ∞ ∞ ∞
nil r r nil nil nil
s t 𝟎 5 3 ∞ ∞ ∞
nil r r nil nil nil
y 𝟎 5 3 ∞ 12 ∞
nil r r nil s nil
t x 𝟎 5 3 8 12 ∞
nil r r t s nil
y 𝟎 5 3 8 11 ∞
nil r r t t nil
z 𝟎 5 3 8 11 -1
nil r r t t t
y x 𝟎 5 3 8 11 -1
nil r r t t t
z 𝟎 5 3 8 11 -1
nil r r t t t
z x 𝟎 5 3 6 11 -1
nil r r z t t

9
7. Shortest-Path: Bellman-Ford for Graph with Negative weights (20%)

Do Bellman-Ford (G, w, r) for G with negative weights and fill in the following tables for
pass 1 - 4.
PASS1 s t y x z
(t, x) 0 ∞ ∞ ∞ ∞
5 nil nil nil nil nil
(t, y) 0 ∞ ∞ ∞ ∞
8 nil nil nil nil nil
(t, z) 0 ∞ ∞ ∞ ∞
-4 nil nil nil nil nil
(x, t) 0 ∞ ∞ ∞ ∞
-2 nil nil nil nil nil
(y, x) 0 ∞ ∞ ∞ ∞
-3 nil nil nil nil nil
(y, z) 0 ∞ ∞ ∞ ∞
9 nil nil nil nil nil
(z, x) 0 ∞ ∞ ∞ ∞
7 nil nil nil nil nil
(z, s) 0 ∞ ∞ ∞ ∞
2 nil nil nil nil nil
(s, t) 0 6 ∞ ∞ ∞
6 nil s nil nil nil
(s, y) 0 6 7 ∞ ∞
7 nil s s nil nil

10
PASS 2 s t y x z
(t, x) 0 6 7 11 ∞
5
nil s s t nil
(t, y) 0 6 7 11 ∞
8
nil s s t nil
(t, z) 0 6 7 11 2
-4
nil s s t t
(x, t) 0 6 7 11 2
-2
nil s s t t
(y, x) 0 6 7 4 2
-3
nil s s y t
(y, z) 0 6 7 4 2
9
nil s s y t
(z, x) 0 6 7 4 2
7
nil s s y t
(z, s) 0 6 7 4 2
2
nil s s y t
(s, t) 0 6 7 4 2
6
nil s s y t
(s, y) 0 6 7 4 2
7
nil s s y t

11
PASS 3 s t y x z
(t, x) 0 6 7 4 2
5
nil s s y t
(t, y) 0 6 7 4 2
8
nil s s y t
(t, z) 0 6 7 4 2
-4
nil s s y t
(x, t) 0 2 7 4 2
-2
nil x s y t
(y, x) 0 2 7 4 2
-3
nil x s y t
(y, z) 0 2 7 4 2
9
nil x s y t
(z, x) 0 2 7 4 2
7
nil x s y t
(z, s) 0 2 7 4 2
2
nil x s y t
(s, t) 0 2 7 4 2
6
nil x s y t
(s, y) 0 2 7 4 2
7
nil x s y t

12
PASS 4 s t y x z
(t, x) 0 2 7 4 2
5
nil x s y t
(t, y) 0 2 7 4 2
8
nil x s y t
(t, z) 0 2 7 4 -2
-4
nil x s y t
(x, t) 0 2 7 4 -2
-2
nil x s y t
(y, x) 0 2 7 4 -2
-3
nil x s y t
(y, z) 0 2 7 4 -2
9
nil x s y t
(z, x) 0 2 7 4 -2
7
nil x s y t
(z, s) 0 2 7 4 -2
2
nil x s y t
(s, t) 0 2 7 4 -2
6
nil x s y t
(s, y) 0 2 7 4 -2
7
nil x s y t

13
8. Shortest-Path- Dijkstra (20%)
Do Dijkstra (G, w, s) to fill in the following Table. Choose vertex by ascending (A to Z)
alphabetical order.

t x
G 1
10  
9
2 3 4 6
s 0
7
5
 2 
y z
1. INITIALIZE-SINGLE-SOURCE (V, s)
2. S← 
3. Q ← V[G]
4. while Q  
5. do u ← EXTRACT-MIN(Q)
6. S ← S  {u}
7. for each vertex v  Adj[u]
8. do RELAX(u, v, w)
9. Update Q (DECREASE_KEY)

RELAX(u, v, w)
1. If d.v > d.u + w(u, v)
2. d.v = d.u+ w(u,v)
3. .v = u

14
EXTRACT- s t y x z Root of P.Q
MIN.Q

s t 0 10 ∞ ∞ ∞ t
nil s nil nil nil
y 0 10 5 ∞ ∞ y
nil s s nil nil
y t 0 8 5 ∞ ∞ t
nil y s nil nil
x 0 8 5 14 ∞ t
nil y s y nil
z 0 8 5 14 7 z
nil y s y y
z s 0 8 5 14 7 t
nil y s y y
x 0 8 5 13 7 t
nil y s z y
t x 0 8 5 9 7 x
nil y s t y
y 0 8 5 9 7 x
nil y s t y
x z 0 8 5 9 7
nil y s t y

15