+ 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)Please Discuss here about this assignment.Thanks
Our main purpose here discussion not just Solution
We are here with you hands in hands to facilitate your learning and do not appreciate the idea of copying or replicating solutions. Read More>>
Discussed & be touched with this discussion. After discussion a perfect solution will come in a result at the end.
Note:-
For Important Helping Material related to this subject (Solved MCQs, Short Notes, Solved past Papers, E-Books, FAQ,Short Questions Answers & more). You must view all the featured Discussion in this subject group.
For how you can view all the Featured discussions click on the Back to Subject Name Discussions link below the title of this Discussion & then under featured Discussion corner click on the view all link.
Or visit this link
&
.•°How to Download past papers from study groups°•.
Please Click on the below link to see…
somebody discuss about the 1st question how can we select the activities with respect to time....
the activities that start at or after the finish time of the previous activity, we have to schedule them.
i cannot understand by these statements
sort the activities according to start time in first.
sort the activities according to finish time in second.
schedule both
it means that we only sort these according to start and finish time and then select activities.
sort with increasing start times in 1.
sort with increasing finish times in 2.
schedule and select separately.
thanks
welcome
CS502 Assignment#02 Idea Solution
this idea is fir question 1 part 2
© 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