false

Textbook Notes
(368,501)

United States
(206,054)

Northeastern University
(1,768)

Computer Science
(2)

CS 5800
(2)

Karl Lieberherr
(2)

Chapter

Unlock Document

Computer Science

CS 5800

Karl Lieberherr

Fall

Description

CS5800 - Yaxin.Huang.HWM10- Solution
Q1(Exercise 22.1-5.)
Solution:
(1) The algorithm for the adjacency-list:
Assuming that the input of the algorithm is an array A[1..n], which contains |V|
elements. Each index represents a node in the graph, and each element is a pointer
to the list of nodes which is the end of edges from the node of this index. (So this
adjacency-list is exactly the same as the one described in section 22.1.)
The algorithm designed below will output the square of the directed graph in the
form of adjacency-list.
SQUARE-GRAPH-ADJ-LIST(A)
let B[1..n] be a new array
n = A.length
for i = 1 to n
adj-node-ptr = A[i] //A pointer to travel the list of
//nodes adjacent to node i.
while adj-node-ptr != NIL
if (*adj-node-ptr) not in the adj-list of B[i]
//linear search
add (*adj-node-ptr) to the head of list B[i]
//(*adj-node-ptr) denotes the node index
adj-adj-ptr = A[(*adj-node-ptr)]
//the next while-loop explores the nodes adjacent
//to node (*adj-node-ptr)
while adj-adj-ptr != NIL
if (*adj-adj-ptr) not in the adj-list of B[i]
add (*adj-adj-ptr) to the head of list B[i]
adj-adj-ptr = adj-adj-ptr.next
adj-node-ptr = adj-node-ptr.next
return B
Running time analysis:
The graph has |V| nodes and |E| edges. The for loop needs to examine |V| nodes.
The first while loop examines the nodes adjacent to node i and the second while loop
examines the nodes adjacent to the nodes that are adjacent to node i. Therefore,
each directed edge is at most examined twice. Because the insertion always
happens at the head of the list, we only need O(1) time to finish the insertion.
The two bold if need to do searching in the adjacency list. In the worst case, when
the graph is fully connected, all together you need to search O(|V| * |E|) times. CS5800 - Yaxin.Huang.HWM10- Solution
∴ The running time of this algorithm is O(|V| * |E|) .
(2) The algorithm for the adjacency-matrix:
Assuming that the input of the algorithm is a matrix A[1..n, 1..n]. If there is an edge
from node u to node v, then A[u,v] is 1, otherwise it is 0.
SQUARE-GRAPH-ADJ-MATRIX(A,n)
// 1 ... n is the indices of nodes
// A[u,v] denotes there is a directed edge (u,v) in G
let B[1..n, 1..n] be a new table
for i = 1 to n
for j = 1 to n
if A[i,j] == 1
B[i,j] = 1
for k = 1 to n
if A[j,k] == 1
B[i,k] = 1
return B
Running time analysis:
There are |V| nodes in graph G and |E| edges. The first for loop examines every
node in graph G. So this for loop has to execute |V| times. The second for loop also
needs to execute |V| times.
If there is an edge from the adjacent node to another adjacent-adjacent nodes, then
the third for loop needs to be executed. Thus, the third for loop in total needs to be
executed at most |E| times.
∴ The running time is O(2|V| + |E|).
Q2(Exercise 22.2-6.)
Solution: CS5800 - Yaxin.Huang.HWM10- Solution
Given the graph above, it can be represented by an adjacency-list as:
A B C (or C B)
B D E (or D E)
C D E (or D E)
C NIL
E NIL
For example we choose A as the source, then we may have these trees because the
different orders of vertices in the adjacency-list:
And here is one tree consisting of shortest paths and it has these edges:
(A B) (B D) (A C) (C E), you can see that non of the trees produced by BFS starting
from A is the tree with shortest paths to each vertices.
Q3(Exercise 22.2-7.) There are two types of professional wrestlers: “babyfaces”
(“good guys”) and “heels” (“bad guys”). Between any pair of professional wrestlers,
there may or may not be a rivalry. Suppose we have n professional wrestlers and we
have a list of r pairs of wrestlers for which there are rivalries. Give an O.n C r/-time
algorithm that determines whether it is possible to designate some of the wrestlers as
babyfaces and the remainder as heels such that each rivalry is between a babyface and
a heel. If it is possible to perform such a designation, your algorithm should produce CS5800 - Yaxin.Huang.HWM10- Solution
it.
Solution: The rivalries between the wrestlers can be represented by an undirected
graph. If there is a rivalry between wrestler u and wrestler v, then there exists an
edge (u,v) in the graph G. And so this problem can be solve by doing some
modifications on BFS.
The input A is an array, and each index denotes a vertex. It is the same
representation as the adjacency-list introduced in section 22.1. Each element in A is
an object, which has the fields : color, d, π and adj. (adj is the pointer to the
adjacency-list).
BFS-DESIGNATION(A)
n = A.length
let B[1..n] be a new array
//B is to store the result of the designation.
//true is babyface, false is heel.
for i from 1 to n
A[i].color = WHITE
A[i].d = ∞
A[i].π = NIL
B[i] = NIL // NIL represents no designation
s = the index of the node with the most out-edges
//here we need θ(|V|) time to search s.
A[s].color = GRAY
A[s].d = 0
A[s].π = NIL
B[s] = true //assign it as the babyface
let Q be a new queue(empty).
ENQUEUE(Q,s)
while Q is nonempty
u = DEQUEUE(Q)
for each vertex index v in the list
that A[u].adj points to:
if A[v].color == WHILE
A[v].color = GRAY
A[v].d = A[u].d + 1
A[v].π = u
if B[v] == NIL
B[v] = not B[u]
elseif B[v] == false
if B[u] == false
return false //no way to designate
else
if B[u] == true
return false CS5800 - Yaxin.Huang.HWM10- Solution
return B //B is the final designation
Q4(Exercise 22.3-7.) Rewrite the procedure DFS, using a stack to eliminate
recursion.
Solution:
The input of the algorithm below is a graph G, who has the
DFS-STACK-VERSION(G)
let S be a new empty stack
let Q be a new empty set
//here we use a set to maintain the unvisited vertices
//so we don’t need coloring
for each vertex u belongs to G.V
u.π = NIL
add u to Q
time = 0
while Q is nonempty
time = time + 1
if EMPTY(S) == true
u = pick one vertex from Q
u.d = time
u.π = NIL
PUSH(S, u)
else
v = TOP(S) //This will only return the value
// of the top element
if G.Adj[v] is nonempty
for each vertex u belongs to G.Adj[v]
kick out u from Q //need to do searching here
u.d = time
u.π = v
PUSH(S, u)
time = time + 1
else
time = time + 1
v.f = time
POP(V)
Q5(Exercise 22.3-10.)Modify the pseudocode for depth-first search so that it prints
out every edge in the directed graph G, together with its type. Show what
modifications, if any, you need to make if G is undirected.
Solution: CS5800 - Yaxin.Huang.HWM10- Solution
DFS-directed-print-edge(G)
for each vertex u belongs to G.V
u.color = WHITE
u.π = NIL
time = 0
for each vertex u belongs to G.V
if u.color == WHITE
DFS-VISIT-directed-print-edge(G,u)
DFS-VISIT-directed-print-edge(G,u)
time = time + 1
u.d = time
u.color = GRAY
for each v belongs to G.Adj[u]
if v.color == WHITE
v.π = u
print “(u,v)|tree edge “
DFS-VISIT-directed-print-edge(G,v)
elseif v.color == GRAY
print “(u,v)|back edge “
else // v.color == BLACK
if u.d < v.d
print “(u,v)|forward edge “
else
print “(u,v)|cross edge”
u.color = BLACK
time = time + 1
u.f = time
If given an undirected graph, the code in the blue box should be modified into this
one:
for each v belongs to G.Adj[u]
if v.color == WHITE
v.π = u
prin

More
Less
Related notes for CS 5800

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.