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

Looking For Something at vustudents.ning.com? Click Here to Search

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

Fundamentals of Algorithms
CS502-Fall 2014
ASSIGNMENT #3
Deadline
Your assignment must be uploaded/submitted at or before 09 Feb. 2015
Uploading instructions
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.)
McGraw Hill; and your course lectures will help you to solve.
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
depends upon your sheer concentration and devotion towards your lecture
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

+ Click Here To Join also Our facebook study Group.

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

See Your Saved Posts Timeline

Views: 1138

.

+ 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

Nimra Sohail posted a status
"Mere Zindagi Hijr O Wisaal Ka Rangeen Fasana Hai"
31 minutes ago
49 minutes ago
♦_"Tooba"_♦ liked ++"STrAnGeR"++'s discussion #تحریرضرورپڑھیں!!!!
2 hours ago
♦_"Tooba"_♦ liked 2.O's discussion Allah ka hona hi bhut bahter hay
2 hours ago
♦_"Tooba"_♦ liked + M.Tariq Malik's discussion Important Announcement
2 hours ago
♦_"Tooba"_♦ updated their profile
2 hours ago
2 hours ago
♦_"Tooba"_♦ liked ++"STrAnGeR"++'s blog post نقطہ اور نکتہ
2 hours ago

## Today Top Members

1

2

3

### ++"STrAnGeR"++

© 2019   Created by + M.Tariq Malik.   Powered by