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

Fundamentals of Algorithms (CS502)

Assignment#02

Total marks = 20

 Submission Deadline =10-01-2018

Lectures Covered:Thisassignment covers Lecture # 23 to 26.

Objectives:

Objectives of this assignment are:

  • To implement Activity Selection Algorithm in real life problems
  • Generation of Variable-length codes using Huffman Coding Algorithm

 

Instructions:

Please read the following instructions carefully before solving & submitting the assignment:

  1. The assignment will not be accepted after due date.
  2. Zero marks will be awarded to the assignment that does not open or the file is corrupt.
  3. The assignment file must be an MS Word (.doc/.docx) file format; Assignment will not be accepted in any other format.
  4. Zero marks will be awarded to the assignment if copied (from other student or copied from handouts or internet).
  5. Zero marks will be awarded to the assignment if the Student ID is not mentioned in the assignment file.

 

For any query about the assignment, contact only at CS502@vu.edu.pk

Please do not post queries related to assignment on MDB.


 

Question # 1:                                                     10Marks (5+5)

 

 

In the context of Activity Selection Problem, consider the following set of activities:

 

Activity

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

Start

Time

2

4

6

1

6

3

1

8

5

6

7

4

2

5

7

Finish Time

9

5

7

3

8

5

2

9

8

9

9

8

3

6

8

 

 

You are required to find the optimal solution (usingGreedy Algorithm) for the following two greediness approaches:

 

  1. Select the activities that start first and schedule them(5 marks)
  2. Select the activities that finish first and schedule them(5 marks)

 

 

Note:

No need to provide any pseudo/working code. Just provide the results for each greediness approach of the following two steps in the below mentioned tabular form:

  1. Sorted Activities
  2. Final Selected Activities

 

Activity

 

 

 

 

 

 

 

StartTime

 

 

 

 

 

 

 

Finish Time

 

 

 

 

 

 

 

 

 

 

 

 

Question # 2:                                                               10 Marks

 

Consider the following scenario in which a set of Alphabets along with their frequencies is given.  You are required to generate the output binary tree and find the Variable-length codes for the given Alphabets using the provided Huffman Coding Algorithm.

 

Total File Length: 210

Frequency table:

A

B

C

D

E

F

10

20

30

40

50

60

 

Huffman Coding Algorithm:

  1. Consider all pairs: <frequency, symbol>.
  2. Choose the two lowest frequencies, and make them brothers, with the root having the

combined frequency.

 

  1. Iterate.

 

 

 

Note:

No need to provide all the steps of the binary tree generation.  Only mention the Final Binary Tree and the Variable-length codes for the given Alphabets in tabular form.

Your solution should be strictly according to the below-mentioned template.

 

Solution Template:

Alphabets: A, B, C, D, E, F

Total File Length: 100

Frequency table:

A

B

C

D

E

F

45

13

12

16

9

5

 

Output Tree:

Letter to be encoded

A

B

C

D

E

F

Frequency

45

13

12

16

9

5

Variable-length code

 0

 101

100 

 111

1101 

1100 

 

 

 

 

Good Luck

+ 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: 12080

.

+ 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

sir kindly share the idea of q 2 also

plz koi help kryn... Q.1 part 1 ka idea bh dy dyn??

starting time sort kr k us mese activity select kesy hogi?

There will be four tables;
 
1. Sorted activities on the basis of Start Time.
2. Final selected activities.
3. Sorted activities on the basis of Finish Time.
4. Final selected activities....in question :1
sir ne btaya

bilkul. start time k inc order main sort karain phir normal procedure chalaen.

Check Respected Frnds Cs502 Q 2 Solution

And reply

Attachments:

arrange thek trah nai hy bs usy thek karen jo values bari hain wo right side py hongi

likhn mi n lecture suna hy woh to left side py ketha hy youtube se

thanksx 

ap k kn sa semester hy 

3rd mcs ka

1st question ho gya?????

yes kr rha hn us k solution ata hhy

RSS

Latest Activity

+ Iuuoɔǝut+ posted discussions
2 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked 2.O's discussion Difference B/w Null and Undefined (Only Devs can understand) :P :P
50 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked Azhar Sagar's discussion Requirements of final year project and selection method
50 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + Adeeena's discussion sometimes......
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + Adeeena's discussion har shakhas muhabt krta hae !!!
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "AS"'s discussion Jo Ghair Thy..
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "AS"'s discussion Zabt Sabhi ...
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked +++STUDENT+++'s discussion YA Allah
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked +++STUDENT+++'s discussion Mja kun sy kr tu
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked Azhar Sagar's discussion Learn complete HTML IN 40 Minutes
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked +++STUDENT+++'s discussion poetry
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "AS"'s discussion Neelam Mat Karna ...
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked +++STUDENT+++'s discussion could your life change
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked +++STUDENT+++'s discussion true poetry
51 minutes ago
+ ! ! ! ! ! ! ! ! ! AG liked + "Jɨyą's discussion me esi hon...!
51 minutes ago
+ "Jɨyą replied to + "Jɨyą's discussion me esi hon...!
1 hour ago
sonio updated their profile
1 hour ago
Sher Ahmed Khan posted a status
"Assalam o Alaikum! Me ne 23rd sept ko form jama karaya tha lekin mujhe abhi tak student id wali mail nhi aaye he.........plz help"
2 hours ago
+++Mahoo+++ liked +++STUDENT+++'s discussion YA Allah
2 hours ago
+++Mahoo+++ liked +++STUDENT+++'s discussion YA Allah
2 hours ago

Today Top Members 

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

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