We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

www.vustudents.ning.com

 www.bit.ly/vucodes + Link For Assignments, GDBs & Online Quizzes Solution www.bit.ly/papersvu + Link For Past Papers, Solved MCQs, Short Notes & More

Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

# CS502 - Fundamentals of Algorithms.........Assignment No 3.......

Fundamentals of Algorithms
CS502-Fall 2014
ASSIGNMENT #3
Please view the assignment submission process document provided to you by
the Virtual University to upload the assignment. And develop solution in
“.doc/docx” file.
Rules for Marking
It should be clear that your assignment will not get any credit if:
oThe assignment is submitted after due date.
oThe submitted assignment does not compile or run.
oThe assignment is copied.
Objectives
This assignment will help you to understand the “Chain Matrix Multiplication” problem
in the paradigm of “Dynamic Programming”. And will also make your vision clear for
Huffman encoding using “Greedy Technique”
Guidelines
1. In order to attempt this assignment you should have full command on Lecture # 18 to
Lecture # 25
2. In order to solve this assignment you have strong concepts about following topics
 Chain Matrix Multiplication
 Huffman encoding
Recommended book for solving assignment
Cormen, Leiserson, Rivest, and Stein (CLRS) 2001, Introduction to Algorithms, (2nd Ed.)
Estimated Time 4 hours
To understand the theme of both questions: 90 minutes.
Question1 solution and implementation’s maximum time is 90 minutes and for
Question2 solution and implementation’s maximum time is one hour. It all
listening.
Strict Observations: If any person make cheating from any source will be graded “F” in this
course.
Question# 1 (10 marks)
Consider the chain matrix multiplication for 4 matrices:
A1 . A2 . A3 . A4
(5×8) (8×9) (9×7) (7×6)
Compute the cost table m in the dynamic programming algorithm for the chain
matrix multiplication.
Question# 2 (10 marks)
Compute the Huffman encoding for the following frequencies of the characters in
Table1.1. Draw the binary tree and also produce Huffman codes for the given
frequencies of characters.
Note: Consider “space” as single character.
Table 1.1
Think for your professional skills and that will be only possible if you perform task
with your own efforts and thinking. Today’s efforts are your life time asset.
All the best
Character Frequency
a 79
b 54
c 40
e 120
u 150
space 20
h 88
i 130
o 35
m 200

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?

Views: 1172

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

Attachments:

### Replies to This Discussion

Assignment is easy but conceptual...

very easy assignment.... In ques 1 just replace the values and compute accordingly of example on page#87. Just listen lecture 26 of data structure u can solve Ques 2 very easy....

Aslamoa lekum

yar dost me ny try kiya he or thnks yar btany ka but i thnik k ye thora mushkil he baki me wait kar raha hon ap k new reply ka

Doctor_CS

How to solve ?

m[1, 2] = 360

m[2, 3] = 504

m[3, 4] = 378

m[1, 3] = 675

m[2, 4] = 810

m[1, 4] = 885

ye 1st question kk ans hain bs mje koi ye ta de k ham k ki values ko kese find kerte hain.

pls send me complete solution

## Latest Activity

+ + + Haniya + + + updated their profile
37 minutes ago
1 hour ago
1 hour ago
1 hour ago
Rana Ali replied to + + + Haniya + + +'s discussion KUCH LOG
1 hour ago
Rana Ali liked + + + Haniya + + +'s discussion KUCH LOG
1 hour ago
1 hour ago
1 hour ago
+ıllıllı \$µǥąя ǥ€ɲɨµ\$ ıllıllı+ liked + + + Haniya + + +'s discussion KUCH LOG
1 hour ago
1 hour ago
1 hour ago

1

2

3