[B][size=10]CS502 Fundamentals of Algorithms Assignment No 3 Spring Semester June 2013
Mr. Rashid is a visiting Lecturer by profession and he has several teaching opportunities available for the coming session. A number of educational institutes have offered him salary per day with number of hours for which his lecturing services are required. These institutes have flexible time scheduling for lectures but have restrictions on the total hours per day teaching requirement. For example, if offer is of 5 hours per day then teaching schedule for Mr. Rashid can be set at any time in the daybut he must has to give 5 hours each day to that institute. Mr. Rashid can work for total of 12 hours in day at maximum. Below is the list of his teaching opportunities with per day working hours and payments in Rs. for the next session.
Offer No (o)
Work Hours (h)
Payment (p) in Rs.
o1
2
1500
o2
3
2500
o3
5
3000
o4
7
5000
o5
8
6000
You need to apply 0/1-Knapsack problem optimization for Mr. Rashid for selection of offers to maximize his income per day.
What is the maximum payment (in Rs.) he can get using Dynamic programming approach on 0/1-Knapsack problem?
Note: Show each step of table filling. You have to tell the best possible profit only and need not to tell the corresponding offer selection i.e. no need to maintain “keep []” matrix.
Solution:
Question No.2: (8 Marks)
Suppose teaching opportunities (in number of hours) are same as above case but all these institutes offer Rs. 700 per hour fix rate payment for teaching. Also suppose that services at all institutes are required to be for continuous hours and have restriction of time schedules of teaching as below;
Offer No (o)
Start time (s)
Finish time (f)
o1
16:00
18:00
o2
18:00
21:00
o3
14:00
19:00
o4
08:00
15:00
o5
09:00
17:00
In these circumstances, you are required to apply Greedy approach of Activity Selection problem to select maximum number of possible options for Mr. Rashid among these teaching opportunities in order to maximize his earning.
What will be the selected offers of teaching by Mr. Rashid according to Activity Selection optimization?
Note: Show the process of Greedy Activity Selection. Using of drawing bars for showing teaching activities arrangement is optional, instead you are allowed to do re-arranging/sorting/selection in the table simply
Mr. Rashid is a visiting Lecturer by profession and he has several teaching opportunities available for the coming session. A number of educational institutes have offered him salary per day with number of hours for which his lecturing services are required. These institutes have flexible time scheduling for lectures but have restrictions on the total hours per day teaching requirement. For example, if offer is of 5 hours per day then teaching schedule for Mr. Rashid can be set at any time in the daybut he must has to give 5 hours each day to that institute. Mr. Rashid can work for total of 12 hours in day at maximum. Below is the list of his teaching opportunities with per day working hours and payments in Rs. for the next session.
Offer No (o)
Work Hours (h)
Payment (p) in Rs.
o1
2
1500
o2
3
2500
o3
5
3000
o4
7
5000
o5
8
6000
You need to apply 0/1-Knapsack problem optimization for Mr. Rashid for selection of offers to maximize his income per day.
What is the maximum payment (in Rs.) he can get using Dynamic programming approach on 0/1-Knapsack problem?
Note: Show each step of table filling. You have to tell the best possible profit only and need not to tell the corresponding offer selection i.e. no need to maintain “keep []” matrix.
Solution:
Question No.2: (8 Marks)
Suppose teaching opportunities (in number of hours) are same as above case but all these institutes offer Rs. 700 per hour fix rate payment for teaching. Also suppose that services at all institutes are required to be for continuous hours and have restriction of time schedules of teaching as below;
Offer No (o)
Start time (s)
Finish time (f)
o1
16:00
18:00
o2
18:00
21:00
o3
14:00
19:00
o4
08:00
15:00
o5
09:00
17:00
In these circumstances, you are required to apply Greedy approach of Activity Selection problem to select maximum number of possible options for Mr. Rashid among these teaching opportunities in order to maximize his earning.
What will be the selected offers of teaching by Mr. Rashid according to Activity Selection optimization?
Note: Show the process of Greedy Activity Selection. Using of drawing bars for showing teaching activities arrangement is optional, instead you are allowed to do re-arranging/sorting/selection in the table simply
0300-9520262
Get solution in 24 hour |cpmputer & internet
mileys81:[SIZE="4"][SIZE="3"]....[/SIZE][/SIZE]