VU VICKY Virtual University Assignment Solution, Past Papers, Handouts and other material

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

	<<Download>>