1
(a)
def NumberInRange(A,p,q,i): n = len(A)
if i > n: return 0
count = 0
if A[i] >= p and A[i] <= q:
count = 1
return count + NumberInRange(A, p, q, i+1)
(b)
T(n) = T(n-1) + O(1) if(n > 0)
= O(1) if(n = 0)
# (c)
T(n) = T(n-1) + O(1)
= T(n-2) + O(1) + O(1)
= T(n-3) + O(1) + O(1) + O(1) …..
= n*O(1)
= O(n)
So the running time is O(n).
2.
(a)
V1
V2
V3
V4
V5
0
∞
∞
∞
0
∞
1
6
-5
-7
0
5
2
-6
-5
-7
0
-11
3
-6
-5
-9
0
-11
4
-7
-5
-9
0
-11
In iteration 0
we set V4 to 0 in line 1 and others to ∞ in line 2. In iteration 1
edge (v1, v4, 6) lead to
B[1,1] = 6 + B[0, 4] = 6 + 0 = 6 in line 8, edge (v2, v4, -5) lead to
B[1,2] = -5 + B[0, 4] = -5 + 0 = -5 in line 8, edge (v3, v4, -7) lead to
B[1,3] = -7 + B[0, 4] = -7 + 0 = -7 in line 8, edge (v5, v4, -5) lead to B[1,5]=5+B[0,4]=5+0= 5inline8,
In iteration 2
edge (v5, v2, -6) lead to
B[2,5] = -6 + B[2, 4] = -6 + (-5) = -11 in line 8
Other values copied from iteration 1 and doesn’t change.
In iteration 3
edge (v3, v5, 2) lead to
B[3,3] = 2 + B[2, 5] = 2 + (-11) = -9 in line 8
Other values copied from iteration 2 and doesn’t change.
In iteration 4
edge (v1, v3, 2) lead to
B[4,1] = 2 + B[3, 3] = 2+ (-9) = -7 in line 8
Other values copied from iteration 3 and doesn’t change.
(b)
No. Whether condition of Line 7 is true or not, the running time of line 7 and line 8 combined is O(1). Because line 8 is an assignment operation, it is in O(1).
(c)
If the negatively weighted cycle is reachable to the destination, then the value computed by BellmanFord algorithm is not the correct shortest path value, because there is no shortest path to
the destination from the vertex in the negatively weighted cycle, we can always add another cycle to the path to get smaller value.
(d)
change weight of edge (v1, v2) from -1 to -2. Now the table is as follows in which row 3 is different from row 2, but the same as row 4.
V1
V2
V3
V4
V5
0
∞
∞
∞
0
∞
1
6
-5
-7
0
5
2
-7
-5
-7
0
-11
3
-7
-5
-9
0
-11
4
-7
-5
-9
0
-11
(e)
BellmanFord(G, w, s, t):
(1) (2) (3) (4) (5) (6) (7)
B(0,t)←0
B(0,v)←∞ for each v ∈ V − {t} i←1
while(i < |V|)
over ← true foreachv ∈ V
B(i,v) ← B(i−1,v)
for each (v, u) ∈ E
if B(i, v) > w(v, u) + B(i − 1, u) then
B(i,v) ← w(v,u)+B(i−1,u)
over ← false if over then
break i← i + 1
return B(i, s)
Let V as the number of vertexes and E as the number of edges.
Worst case run time: O(VE)
Best case run time: O(E)
Line(1)(2) runs in O(V) time,
Line6-11 runs in O(E) time, because each edge computed once.
So the total time is O(iE), where i is the number of iterations the algorithm runs, i>=1 and i
3.
(a)
(b)
(c)
network with flow
residual graph
(d)
iteration 2: Residual Graph:
PathP: s->v3->v6->t
residual capacity x of bottleneck edge : 1 network’s flow after augmenting
iteration 3:
Residual Graph:
PathP: s->v2->v4->v1->v5->t residual capacity x of bottleneck edge : 1 network’s flow after augmenting
Now the residual graph is:
There is no augmenting path, the final network flow is:
(e)
The maximum matching got from above is: v1 –> v5 v2 -> v4 v3 -> v6