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:
plz koi help kryn... Q.1 part 1 ka idea bh dy dyn??
starting time sort kr k us mese activity select kesy hogi?
bilkul. start time k inc order main sort karain phir normal procedure chalaen.
Check Respected Frnds Cs502 Q 2 Solution
And reply
arrange thek trah nai hy bs usy thek karen jo values bari hain wo right side py hongi
likhn mi n lecture suna hy woh to left side py ketha hy youtube se
https://www.youtube.com/watch?v=MXq9L5lstD4
watch this
thanksx
ap k kn sa semester hy
3rd mcs ka
1st question ho gya?????
yes kr rha hn us k solution ata hhy
© 2021 Created by + M.Tariq Malik.
Powered by
Promote Us | Report an Issue | Privacy Policy | Terms of Service
We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.
We are user-generated contents & non-commercial 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. All Contents on site are for personal & non-commercial use.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 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