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

.

+ 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

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. Read More>>

Discussed & be touched with this discussion. After discussion a perfect solution will come in a result at the end.

 

Note:-

For Important Helping Material related to this subject (Solved MCQs, Short Notes, Solved past Papers, E-Books, FAQ,Short Questions Answers & more). You must view all the featured Discussion in this subject group.

For how you can view all the Featured discussions click on the Back to Subject Name Discussions link below the title of this Discussion & then under featured Discussion corner click on the view all link.

Or visit this link 

Click Here For Detail.

&

.•°How to Download past papers from study groups°•.

 

Please Click on the below link to see…

.... How to Find Your Subject Study Group & Join .... 

somebody discuss about the 1st question how can we select the activities with respect to time....

the activities that start at or after the finish time of the previous activity, we have to schedule them.

i cannot understand by these statements

  • Select the activities that start first and schedule them
  • Select the activities that finish first and schedule them


sort the activities according to start time in first. 

sort the activities according to finish time in second.

schedule both

it means that we only sort these according to start and finish time and then select activities.

sort with increasing start times in 1.

sort with increasing finish times in 2.

schedule and select separately.

thanks

welcome

aoa plz share q1 solution ?

CS502 Assignment#02 Idea Solution

Attachments:

this idea is fir question 1 part 2

RSS

Latest Activity

Azhar Sagar liked Azhar Sagar's discussion quiz main kese 10/10 mark la saktay hain cheating ka asan tareeqa
7 minutes ago
Azhar Sagar liked Azhar Sagar's discussion Subscribe my youtube channel for assignment solution and final year project help
7 minutes ago
M IDREES replied to + M.Tariq Malik's discussion CS403 Assignment No 01 Fall 2019 Solution & Discussion Due Date: 13-11-2019 in the group CS403 Database Management Systems
8 minutes ago
Azhar Sagar posted discussions
8 minutes ago
M IDREES replied to + M.Tariq Malik's discussion CS403 Assignment No 01 Fall 2019 Solution & Discussion Due Date: 13-11-2019 in the group CS403 Database Management Systems
10 minutes ago
M IDREES replied to + M.Tariq Malik's discussion CS403 Assignment No 01 Fall 2019 Solution & Discussion Due Date: 13-11-2019 in the group CS403 Database Management Systems
12 minutes ago
M IDREES joined + M.Tariq Malik's group
12 minutes ago
M IDREES replied to + M.Tariq Malik's discussion CS502 Fundamentals of Algorithms Assignment No 01 Fall 2019 Solution & Discussion in the group CS502 Fundamentals of Algorithms
18 minutes ago
Profile IconM IDREES, Abdul Ghaffar and Umair ali joined + M.Tariq Malik's group
18 minutes ago
+ AiM replied to 彡Tweety彡 ❤️'s discussion .... Mera Pakistan... :x:p
21 minutes ago
Siddiq khan kakar joined + M.Tariq Malik's group
27 minutes ago
+ M.Tariq Malik replied to +¢αяєℓєѕѕ gιяℓ's discussion CS202 - Fundamentals of Front End Development Assignments No. 1 Due Date Nov 14, 2019 in the group CS202 Fundamentals of Front End Development
39 minutes ago
+ M.Tariq Malik replied to +¢αяєℓєѕѕ gιяℓ's discussion CS202 - Fundamentals of Front End Development Assignments No. 1 Due Date Nov 14, 2019 in the group CS202 Fundamentals of Front End Development
40 minutes ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion MGT211 GDB Fall 2019 Solution & Discussion in the group MGT211 Introduction To Business
40 minutes ago
Mian Ali added a discussion to the group MCM520 Contemporary Mass Media
45 minutes ago
Mian Ali joined + M.Tariq Malik's group
47 minutes ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion EDU302 Human Development and Learning Assignment No 01 Fall 2019 Solution & Discussion in the group EDU302 Human Development and Learning
47 minutes ago
Mian Ali joined + M.Tariq Malik's group
49 minutes ago
+ M.Tariq Malik replied to + M.Tariq Malik's discussion CS508 Assignment No 01 Fall 2019 Solution & Discussion Due Date: 12-11-2019 in the group CS508 Modern Programming Languages
50 minutes ago
+ !! SARAH replied to Rana Ali's discussion Tell some words in the Shan of Hazart Muhammad (S.A.W)
52 minutes ago

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

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