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


+ Link For Assignments, GDBs & Online Quizzes Solution


+ 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



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.

















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)

















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: 10786


+ 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)


Replies to This Discussion

Thnk u  M.Tariq Malik bhai... pa g tusi gr8 oooooooooooooooooOOOOOOOooooo....

2nd question kis ma banana hai picture bany ge????/

g picture bny gi.....

enjoy the taste of 2nd question. i hope u all understand this solution easily :-)

i think ye solution wrong hy.. kiu k isay sequence me lane ki zarurt hy he nahe,, jse timing schedule given hy wse he solve krn ge,. n suppose hum ye solution krn bhe,, to bh without interfrnc to ata he ni hy solution,, 04 and 01 k bech me 05 intrfre kr rha hy...

just 1 banday ne theek solution btya hy !!

CS502 Fundamentals of Algorithms Assignment SOLUTION

there is no rule for arranging the activities.


See the attached file 



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

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