We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

Looking For Something at vustudents.ning.com? Click Here to Search

www.bit.ly/vucodes

+ Link For Assignments, GDBs & Online Quizzes Solution

www.bit.ly/papersvu

+ Link For Past Papers, Solved MCQs, Short Notes & More


Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

How to Add New Discussion in Study Group ? Step By Step Guide Click Here.

Assignment No. 03
Semester: Spring 2013

CS502-Fundamentals of Algorithms

Total Marks: 20

 

Due Date: 03/07/2013

 

Lectures Covered:  21 to 32

 

Objective

To solve daily life problems by Dynamic Programming techniques.

 

Uploading instructions:

Please view the Assignment Submission Process document provided to you by the Virtual University for uploading assignments.

 

  • Your assignment must be in .doc format. (Any other formats like scan images, PDF, Zip, rar, bmp etc. will not be accepted).
  • Save your assignment with your ID (e.g. bc020200786.doc).
  • No assignment will be accepted through email.

 

Rules for Marking:

It should be clear that your assignment will not get any credit if:

 

  • The assignment is submitted after due date.
  • The submitted assignment does not open or file is corrupted.
  • Your assignment is copied from internet, handouts or from any other student

      (Strict disciplinary action will be taken in this case).

 

Question No.1: 

(12 Marks)

 

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 day but 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.

 

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.

 

NOTE: Submit “.doc” file only. Every student should provide his/her own work, exact copying of the assignment (or some portion of the assignment) from the internet or other students will lead to copy case and zero marks will be awarded. Different softwares will be used to check plagiarism in assignments. Do not put any query on MDB about this assignment, if you have any query then  email at CS502@vu.edu.pk

 

 

 

+ How to Follow the New Added Discussions at Your Mail Address?

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?


See Your Saved Posts Timeline

Views: 10770

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

+ Click Here to Search (Looking For something at vustudents.ning.com?)

+ Click Here To Join (Our facebook study Group)

Attachments:

Replies to This Discussion

for Question no. 1 see page no 93-96 of handouts

thanks for sharing.

BFSS apka project konsa he..?

aur kya socha he ap ne ussy banany k lyee...?

Please Discuss here about this assignment.Thanks

Our main purpose here discussion not just Solution

We are here with you hands in hands to facilitate your learning and do not appreciate the idea of copying or replicating solutions.

discuss assignment fellows ...

BFSS page nbr 93-96 just see krna ya read b krna hy

Its up to U my dear +(((Zoy-e-Noor)))+

just chill..........BFSS

i think es me kuch problem he, plz ap check kr k bataen, is it true or not...?

but i think maximum value 9000 aani chahye thi, jo k nhi aa rahi...

plz comments

thanks

brother can u explain the values of V[5,10] ,V[4,8] and V[4,9]

my answer is laso 8501 but i have different values in these?

thanks you so much fors sharing the idea

Zubair bhai  top Row 1 aur 2nd column 1 ki smj  nai ai.

Top Row is liye k  first Row ma hour limit 2 ha aur payment 1500 which will be satisfy the condition on 3rd column in first Row.

aur 2nd colun is liye k..wha hour limit 1 ha and question ma koi option aisi nai jaha 2nd column ki  hour limit satisfy ho rai ho. tu aap ny waha 1 kyn likha.  please explain .

Zubair bhai one more thing, have you calculated for each cell of the table by putting the value in the above mentioned formula.

i have herd video lec sir filled up complete table just considering the best max value.

I can not understand how do you filled up the top most Row with all one.. as their is no 1.00 Rs mentioned in the payment options. then how ..... ??? 

RSS

Today Top Members 

© 2019   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service

.