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)
- 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:
- Sorted Activities
- 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:
- Consider all pairs: <frequency, symbol>.
- Choose the two lowest frequencies, and make them brothers, with the root having the combined frequency.
- 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