Login

***Vuhelper*** · 01-03-2012, 09:11 PM

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

Login
Username:
Password:	Lost Password?
	Remember me

Possibly Related Threads…
Thread		Author	Replies	Views	Last Post
	CS301 Assignment # 4 Due Date: 02-Feb-2016	Vuhelper	0	2,380	02-03-2016, 05:38 PM Last Post: Vuhelper
	CS703 – Advanced Operating Systems Assignment No.3 solution January 2016	Vuhelper	0	5,972	01-23-2016, 09:58 PM Last Post: Vuhelper
	CS601 Data Communication Assignment No. 03 Solution 23rd January 2016	Vuhelper	1	2,008	01-23-2016, 06:09 PM Last Post: Vuhelper
	CS403 Assignment No. 03 Solution 23rd January 2016	Vuhelper	2	1,252	01-23-2016, 03:18 PM Last Post: Vuhelper
	CS506 Web Design and Development Assignment no 3 Solution 3rd January 2016	Vuhelper	0	2,310	01-23-2016, 03:16 PM Last Post: Vuhelper
	CS724 Software Process Improvement Assignment No 01 Solution 20th January 2016	Vuhelper	0	2,036	01-20-2016, 06:26 PM Last Post: Vuhelper
	CS711 Software Design Assignment No 01 Solution Due Date Feb 12, 2016	Vuhelper	0	1,730	01-20-2016, 06:24 PM Last Post: Vuhelper
	CS709 Formal Methods for Software Engineering Assignment No 01 Solution January 2016	Vuhelper	0	1,866	01-20-2016, 06:22 PM Last Post: Vuhelper
	cs703 assignment no 3 Solution 20th January 2016	Vuhelper	0	1,766	01-20-2016, 06:20 PM Last Post: Vuhelper
	CS704 Assignment No. 01 Solution January 2016	Vuhelper	0	4,867	01-20-2016, 06:19 PM Last Post: Vuhelper