CS502 Fundamentals of Algorithms Assignment no 2 Solution

           

CS502                    Assignment No: 2

Question 1:

Step 1: sort the activities as per finishing time in ascending order

Sorted activity	G	D	M	F	B	N	C	I	E	O	A	J	K	H
Start time	1	1	2	3	4	5	6	5	6	7	2	6	7	8
End time	2	3	3	5	5	6	7	8	8	8	9	9	9	9

                   ↑           ↑

                     i           j

Step 2: select the first activity

Sorted activity	6
Start time	1
End time	2

Step 3: Select the next activity whose start time is greater than or equal to the finish  time of the previously selected activity

Previously selected activity=i

Sorted activity	G	M
Start time	1	2
End time	2	3

                                              ↑      

                                                I

Now newly selected activity i

Previously selected activity =i

Next activity=j

Start time of j=3

Finish time of i=3

Start time of j>=finish time of i

3>=3

Yes, select this activity

Sorted activity	G	M	F
Start time	1	2	3
End time	2	3	5

                                                         ↑           

                                                                        i

Step 4: Select the next activity whose start time is greater than or equal to the finish  time of the previously selected activity

Previously selected activity=i

Next activity=j

start time of j=1

finish time of i=2

1>=2

No, so we move to the next activity

start time of j=2

finish time of i=2

2>=2

Yes, so we select the activity

Now newly selected activity i

Previously selected activity=i

Next activity=j

Start time of j=4

Finish time of i=5

Start time of j>=finish time of i

4>=5

No, move to the next activity

Start time of j=5

Finish time of i=5

Start time of j>=finish time of i

5>=5

Yes, select this activity

Sorted activity	G	M	F	N
Start time	1	2	3	5
End time	2	3	5	6

↑                                                                          

                                                                                    i

Now newly selected activity i

Previously selected activity=i

Next activity=j

Start time of j=6

Finish time of i=6

Start time of j>=finish time of i

6>=6

Yes, select this activity

Sorted activity	G	M	F	N	C
Start time	1	2	3	5	6
End time	2	3	5	6	7

↑                                                                                                  

                                                                                            i

now newly selected activity i

previously selected activity =i

next activity =j

start time of j=5

finish time of i=7

start time of j>=finish time of i

5>=7

No, so move to the next activity

Next activity=j

Start time of j=6

Finish time of i=7

Start time of j>=finish time of i

6>=7

No, so move to the next activity

start time of j=7

finish time of i=7

start time of j>=finish time of i

7>=7

Yes, select this activity

Sorted activity	G	M	F	N	C	O
Start time	1	2	3	5	6	7
End time	2	3	5	6	7	8

                                                                                           ↑                     

                                                                                                                    i

now newly selected activity i

previously selected activity =i

next activity =j

start time of j=2

finish time of i=8

start time of j>=finish time of i

2>=8

No, so move to the next activity

start time of j=6

finish time of i=8

start time of j>=finish time of i

6>=8

No, so move to the next activity

start time of j=7

finish time of i=8

start time of j>=finish time of i

7>=8

No, so move to the next activity

start time of j=8

finish time of i=8

start time of j>=finish time of i

8>=8

Yes, select this activity

We have the required activity

Sorted activity	G	M	F	N	C	O	M
Start time	1	2	3	5	6	7	8
End time	2	3	5	6	7	8	9

                                                                End