Latest Activity In Study Groups

Join Your Study Groups

VU Past Papers, MCQs and More

CS502 Assignment No.2

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

Views: 12251

Attachments:

Replies to This Discussion

0las6d9xugehgPermalink Reply by 0las6d9xugehg on January 10, 2018 at 6:47pm

koyi question 1 or 2 part k solution upload kr day

Permalink Reply by Rose on January 10, 2018 at 7:33pm

final select activity table m kesy fill hoga??

starting or finish dono m aik hi conditon hogi?? S>=f

is it right?

plzzz reply dildar bhai

Permalink Reply by Atif Hafeez Khan on January 10, 2018 at 8:13pm

Start time of j>= finish time of i

Permalink Reply by Dildar Hussain on January 10, 2018 at 9:00pm

part 1 table start time k hisab s or final select activity ka table wohi hay jo finish time activity ka hay

Activity

G

D

M

A

F

B

L

N

I

C

E

J

O

K

H

Start

Time

1

1

2

2

3

4

4

5

5

6

6

6

7

7

8

Finish Time

2

3

3

9

5

5

8

6

8

7

8

9

8

9

9
Permalink Reply by + M.Tariq Malik on January 10, 2018 at 9:48pm

How to create Huffman tree and find variable length .. Watch this Video 

Permalink Reply by + M.Tariq Malik on January 10, 2018 at 9:49pm
Permalink Reply by + M.Tariq Malik on January 10, 2018 at 9:49pm

Solution 

Attachments:

Permalink Reply by + M.Tariq Malik on January 10, 2018 at 9:49pm

Solution 

Attachments:

Permalink Reply by ++ACHJ-- on January 10, 2018 at 9:59pm

Complete Solution of this assignment#[LINK]

https://www.youtube.com/watch?v=Zv__bqvmSbY

Assignment

RSS

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

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