CS502 Assignment No.3 fall Semester fall 24 December 2011

[Vuhelper]

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 PHYSICIAN to STATISICIAN


Question# 2 (10)
You are the project manager in multi-national company and you are asked to deploy
the project for the firm to get the optimal solution and maximum profit in the given
constraints
There are six projects i.e. Tele -Communication Project (P1), Hardware Devices
Production Plant (P2), Software services for the educational institutes (P3), Distance
learning Software Development Centre (P4) , Virtual cell phone development centre
(P5) and Medical diagnoses devices enhancement centre (P6) .Your organization
has Rs.150 billions to invest .If the cost of P1 is Rs.50 billion and profit earned is
Rs.38 Billion, the cost of P2 is Rs.35 billion and profit earned is Rs.22 Billion, the
cost of P3 is Rs.40 billion and profit earned is Rs.25 Billion ,the cost of P4 is Rs.65
billion and profit earned is Rs.58 Billion ,cost of P5 is Rs.55 billion and profit earned
is Rs.45 Billion and the cost of P6 is Rs.60 billion and profit earned is Rs.47 Billion
Your role is to maximize the profit in given amount to launch the projects.
Determine the projects to be selected to earn the maximum profit using 0-1
Knapsack Show complete process.

[Vuhelper]

Code:

Question No.2: Use the following dynamic programming based recurrence edit distance to find the possible edit scripts while converting “INVENTION “to “CONVENTION”. ( ) ( ) ( ) ( ) [ ] [ ] ( ) [ ] [ ] 1, 1 , 1 1 , min 1, 1 1 1, 1 E i j E i j E i j E i j if A i B j E i j if A i B j  - +     - +  =  - - + ¹     - - =  Solution: ( ) ( ) ( ) ( ) [ ] [ ] ( ) [ ] [ ] 8,10 1 9,9 1 9,10 min 8,9 1 9 10 8,9 9 10 E E E E if A B E if A B  +     +  =  + ¹     =  Final table with all E [I, J] entries computed C O N V E N T I O N 0 ®1 ®2 ®3 ®4 ®5 ®6 ®7 ®8 ®9 ®10 I ¯ 1 ] 1 ]® 2 ]® 3 ]® 4 ]® 5 ]® 6 ]® 7 ]® 8 ]® 9 ]® 10 N ¯ 2 ] ¯ 2 ] 2 ] 2 ®3 ®4 ®5 ®6 ®7 ®8 ] 9 V ¯ 3 ] ¯ 3 ] 3 ] ¯ 3 ] 2 ®3 ®4 ®5 ®6 ®7 ®8 E ¯ 4 ] ¯ 4 ] ¯ 4 ¯4 ¯3 ] 2 ®3 ®4 ®5 ®6 ®7 N ¯ 5 ] ¯ 5 ] ¯ 5 ] ¯ 5 ¯4 ¯3 ] 2 ®3 ®4 ®5 ®6 T ¯ 6 ] ¯ 6 ] ¯ 6 ¯6 ¯5 ¯4 ¯3 ] 2 ®3 ®4 ®5 I ¯ 7 ] ¯ 7 ] ¯ 7 ] ¯ 7 ¯6 ¯5 ¯4 ¯3 ] 2 ®3 ®4 O ¯ 8 ] ¯ 8 ] ¯ 8 ] ¯ 8 ¯7 ¯6 ¯5 ¯4 ¯3 ] 2 ®3 N ¯ 9 ] ¯ 9 ] ¯ 9 ] ¯ 9 ¯8 ¯7 ¯6 ¯5 ¯4 ¯3 ] 2 ® shows insertion ¯ shows deletion ] shows match or substitution SOLUTION PATH: 1+ 1+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ 0+ = 2 MINIMUM DISTANCE S I M M M M M M M M I - N V E N T I O N C O N V E N T I O N

[Vuhelper]

PHYSICIAN to STATISICIAN
EDIT DISTANCE
1+ 1+ 1+ 1+ 0+ 1+ 0+ 1+ 1+ 1+ 1+ = 9Minimum.
S S S S M S M S S I I
P H Y S I C I A N
S T A T I S I C E A N

[WAAAG]

Thanks for the idea

[rabeel]

welcome welcome