Fundamentals
of Algorithms (CS502)
Assignment
# 02
Total marks = 20
Submission Deadline = 10-01-2018
Question # 1: 10
Marks (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 (using Greedy 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
|
|
|
|
|
|
|
|
|
Start
Time
|
|
|
|
|
|
|
|
|
Finish
Time
|
|
|
|
|
|
|
|
Solution:
1: Sorted Activities:
First we will sort the activities in
non-decreasing order with respect to their finish time so that we
always consider the next activity as minimum finishing time activity.
|
Activity
|
G
|
D
|
M
|
F
|
B
|
N
|
C
|
L
|
I
|
E
|
O
|
A
|
J
|
K
|
H
|
|
Start
Time
|
1
|
1
|
2
|
3
|
4
|
5
|
6
|
4
|
5
|
6
|
7
|
2
|
6
|
7
|
8
|
|
Finish
Time
|
2
|
3
|
3
|
5
|
5
|
6
|
7
|
8
|
8
|
8
|
8
|
9
|
9
|
9
|
9
|
2: Final Selected activities:
For
the selection of final activities we will see in the above table where
activities are given with their start time and finish time. We will select
those activities which start time is equal to or greater than finish time of
last activities. We will select them step by step.
Step 1:
|
Activity
|
G
|
|
Start
Time
|
1
|
|
Finish
Time
|
2
|
Step 2:
In step 2 we will choose that activity
which start time is greater than or equal to the finish time from the previous
activity.
|
Activity
|
G
|
M
|
|
Start
Time
|
1
|
2
|
|
Finish
Time
|
2
|
3
|
Step 3:
In step 3 we will choose that activity
which start time is greater than or equal to the finish time from the previous
activity.
|
Activity
|
G
|
M
|
F
|
|
Start
Time
|
1
|
2
|
3
|
|
Finish
Time
|
2
|
3
|
5
|
Step 4:
In step 4 we will choose that activity
which start time is greater than or equal to the finish time from the previous
activity.
|
Activity
|
G
|
M
|
F
|
N
|
|
Start
Time
|
1
|
2
|
3
|
5
|
|
Finish
Time
|
2
|
3
|
5
|
6
|
Step 5:
In step 5 we will choose that activity
which start time is greater than or equal to the finish time from the previous
activity.
|
Activity
|
G
|
M
|
F
|
N
|
C
|
|
Start
Time
|
1
|
2
|
3
|
5
|
6
|
|
Finish
Time
|
2
|
3
|
5
|
6
|
7
|
Step 6:
In step 6 we will choose that activity
which start time is greater than or equal to the finish time from the previous
activity.
|
Activity
|
G
|
M
|
F
|
N
|
C
|
O
|
|
Start
Time
|
1
|
2
|
3
|
5
|
6
|
7
|
|
Finish
Time
|
2
|
3
|
5
|
6
|
7
|
8
|
Step 7:
In step 7 we will choose that activity
which start time is greater than or equal to the finish time from the previous
activity.
|
Activity
|
G
|
M
|
F
|
N
|
C
|
O
|
H
|
|
Start
Time
|
1
|
2
|
3
|
5
|
6
|
7
|
8
|
|
Finish
Time
|
2
|
3
|
5
|
6
|
7
|
8
|
9
|
Our final selected activities are:
|
Activity
|
G
|
M
|
F
|
N
|
C
|
O
|
H
|
|
Start
Time
|
1
|
2
|
3
|
5
|
6
|
7
|
8
|
|
Finish
Time
|
2
|
3
|
5
|
6
|
7
|
8
|
9
|
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
|
Solution:
Output Binary Tree:
Variable-length codes
|
Letter to be encoded
|
A
|
B
|
C
|
D
|
E
|
F
|
|
Frequency
|
10
|
20
|
30
|
40
|
50
|
60
|
|
Variable-length code
|
100
|
101
|
110
|
111
|
00
|
01
|
