CSCE629 Analysis of Algorithms
Spring
2019
Instructor:
Dr. Jianer Chen
Teaching Assistant:
Qin Huang
Office:
HRBB 315C
Office:
HRBB 315A
Phone:
8454259
Phone:
4026216
Email:
[email protected]
Email:
[email protected]
Office Hours:
T,Th 11:00 am–12:30 pm
Office Hours:
MWF 3:00 pm–4:00 pm
Solutions to Assignment #3
(Prepared with TA Qin Huang)
1.
1. Suppose that we have a sequence of MakeSetFindUnion operations in which no Find
appears before any Union. What is the computational time for this sequence?
2.
(Question 24.15, Textbook, p. 655) Let
G
= (
V, E
) be a weighted directed graph. Develop
an
O
(
nm
)time algorithm that finds the value
δ
(
v
) for every vertex
v
, which is defined as:
δ
(
v
) = min
w
∈
V
{
the length of the shortest path in G from
w
to
v
}
.
1
Algorithm 1. Pseudocode for Problem 2
Input:
G
= (
V, E
)
1.
for
(each vertex
v
∈
V
)
D
[
v
] = 0;
2.
for
(
i
= 1 to

V
 
1)
3.
for
(each edge (
u, v
)
∈
E
)
if
(
D
[
u
] +
wt
(
u, v
)
< D
[
v
])
return (“negative cycles exist.”);
4. return
D
[
·
];
Assume the graph
G
contains no negative cycles. For any two vertices
u
and
w
in the graph
G
, denote by