CS502
Assignment No. 3
Solution no. 1
Activity
|
Start time
|
Finish time
|
A
|
1
|
4
|
B
|
3
|
5
|
C
|
1
|
6
|
D
|
5
|
7
|
E
|
3
|
8
|
F
|
5
|
9
|
G
|
6
|
10
|
H
|
8
|
11
|
I
|
8
|
12
|
Let starting time of second activity = U
Finish time of first activity = V
HENCE selected activity which starts first
U >= V
First we B activity
3 >= 4
We can’t select this activity
because that is not satisfied.
Check next activity C
1 >= 5
We can’t select this activity
because that is not satisfied.
Check next activity D
5 >= 4
Activity selected because of
satisfaction.
Check next activity E
3 >= 7
We can’t select this activity
because that is not satisfied.
Check next activity F
5 >= 7
We can’t select this activity
because that is not satisfied.
Check next activity G
6 >= 7
We can’t select this activity
because that is not satisfied.
Check next activity H
8 >= 7
Activity selected because of
satisfaction.
Check next activity I
8 >= 11
We can’t select this activity
because that is not satisfied.
We checked every activity one by
one and the selected activities are:
Activity
|
Start Time
|
Finish Time
|
A
|
1
|
4
|
D
|
5
|
7
|
H
|
8
|
11
|
Solution
No. 2
(a)
Adjacency List format
|
|
|
|
|
|
|
2
|
|
5
|
|
6
|
|
1
1
|
|
3
|
|
7
|
|
2
2
|
|
4
|
|
3
3
|
|
5
|
|
7
|
|
4
1
|
|
4
|
|
6
|
|
7
|
|
5
1
|
|
5
|
|
6
2
|
|
4
|
|
5
|
|
7
(b)
Graph
Post a Comment
Don't Forget To Join My FB Group VU Vicky
THANK YOU :)