+ Link For Assignments, GDBs & Online Quizzes Solution |
+ Link For Past Papers, Solved MCQs, Short Notes & More |
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:
Instructions:
Please read the following instructions carefully before solving & submitting the assignment:
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:
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:
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:
combined frequency.
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
Tags:
+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)
+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)
+ Click Here to Search (Looking For something at vustudents.ning.com?) + Click Here To Join (Our facebook study Group)koyi question 1 or 2 part k solution upload kr day
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
Start time of j>= finish time of i
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 |
How to create Huffman tree and find variable length .. Watch this Video
© 2021 Created by + M.Tariq Malik.
Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
We are user-generated contents site. All product, videos, pictures & others contents on site don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com Page with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List | Moderators Group
All Members | Featured Members | Top Reputation Members | Angels Members | Intellectual Members | Criteria for Selection
Become a Team Member | Safety Guidelines for New | Site FAQ & Rules | Safety Matters | Online Safety | Rules For Blog Post