CS502-Fundamentals of Algorithms Assignment No. 03 Solution and Discussion Fall 2013 Total Marks: 20 Due Date: July 9th, 2014

Estimated Time 4 hours 

To understand the theme of both questions 90 minutes.Question1 solution 
implementation maximum time is 90 minutes and for Question2 solution 
implementation maximum time is one hour. It all depends upon your sheer 
concentration and devotion towards your lecture listening.

Fundamentals of Algorithms 
CS502-Spring 2014 
 ASSIGNMENT #3 
Deadline 

Your assignment must be uploaded/submitted at or before 9th July 2014 
Uploading instructions 

Please view the assignment submission process document provided to you by 
the Virtual University to upload the assignment. 
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 concepts of Knapsack Problem and edit 
distance problem in the paradigm of dynamic programming. 
Guidelines 
1. In order to attempt this assignment you should have full command on Lecture # 19 to 
Lecture # 27 
2. In order to solve this assignment you have strong concepts about following topics 
 Edit distance Problem 
 Chain Matrix Multiplication 





 Recommended book for solving assignment 
Cormen, Leiserson, Rivest, and Stein (CLRS) 2001, Introduction to Algorithms, (2nd ed.) 
McGraw Hill. 

Estimated Time 4 hours 

To understand the theme of both questions 90 minutes.Question1 solution 
implementation maximum time is 90 minutes and for Question2 solution 
implementation maximum time is one hour. It all depends upon your sheer 
concentration and devotion towards your lecture listening. 

Question# 2 (10) 
Use the following dynamic programming based recurrence edit distance to find the possible edit 
scripts while converting NEUROLOGIST TO PHRENOLOGIST 


Question# 2 (10) 

Consider the chain matrix multiplication for 4 matrices: 
 A1 . A2 . A3 . A4 
 (7×5) (5×4) (4×6) (6×8) 

Compute the cost table m in the dynamic programming algorithm for the chain matrix 
multiplication 

Happy Ramzan Ul Mobarak 

Think with peace souls in Ramzan Ul Mobarak