Assignment No.2 CS502 Solution (Fundamentals of Algorithms)
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.
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:
I.
Sorted Activities
II.
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.
3. 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
0 comments:
Post a Comment
Please Share Your Queries!