[B][SIZE="2"]CS502 Fundamentals of Algorithms Assignment No 3 Spring Semester June 2013View more random threads:
- Fin622 Solution 1 July 2010
- cs401 assignment no 1 spring may 2015 solution for idea
- Solution ORGANZIATIONAL BEHAVIOR MGT-502 Assignment No.1
- MGT602 Entrepreneurship Assignment No. 01 Solution Fall 2014
- Cocoa Production Supply Assignment April 2013
- CS304 Object Oriented Programming 5 Assignment 19 July 2010
- MTH301 assignment solution required plxx
- CS507 Information Systems Assignment 04 Spring 2014 Due...
- CS506 Web Design and Development Assignment No. 01 Solution...
- ENG201 Assignment 4 Deadline 27 July 2010
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
Sponsored Links
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
Last edited by Vuhelper; 06-28-2013 at 10:13 PM.
There are currently 1 users browsing this thread. (0 members and 1 guests)