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 :)

Previous Post Next Post