CS502 - Fundamentals of Algorithms Assignment 3 due date Feb 09, 2015

CS502 Fundamentals of Algorithms Fall 2014

Assignment No.3

Deadline Your assignment must be uploaded/submitted at or before 09 Feb. 201 5

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 Multipl
• 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

Character Frequency

a                 79

b                 54

c                 40

e                 120

u                150

space           20

h                 88

i                   130

o                  35

m              200

Dear students ! Assignment 3 has been uploaded. You are now in challenging phase how you apply your learnt lessons. 

The dead line is 09th Feb. 2015 . Start your efforts to increase your professional visions.

All the best.