loading...

CS502 Fundamentals of Algorithms Assignment 2 Solution Fall 2017

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:

 Select the activities that start first and schedule them(5 marks)

  1. 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 

 

DOWNLOAD SOLUTION HERE
loading...