Fundamentals of Algorithms CS502-Fall2010

Fundamentals of Algorithms
CS502-Fall2010
ASSIGNMENT #2
Deadline
Your assignment must be uploaded/submitted at or before 25th November 2010
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 open or run.
oThe assignment is copied.
Objectives
This assignment will help you to understand the concepts of linear radix sort and dynamic
programming applications and edit distance problem solution using dynamic technique.
Guidelines
1. In order to attempt this assignment you should have full command on Lecture # 15 to
Lecture # 18
2. In order to solve this assignment you have strong concepts about following topics
􀀹 Radix sort
􀀹 Dynamic programming technique and Edit distance problem
Books to read for solution
Cormen, Leiserson, Rivest, and Stein (CLRS) 2001, Introduction to Algorithms, (2nd ed.)
McGraw Hill.
Estimated Time 4 hours
Your concepts and logics will take actual measure of time ;however first question
should not take more than 1.5 hour and for question 2 you may solve in 2.5 hours
It all depends upon your sheer concentration.
Question# 1 (10)
Perform radix sort step wise on the following data and briefly describe the worst
case complexity and big O notation at end.
Input data
55141,65545,56125,65126,22111,11225,31121,56814,11252,23541
Question# 2 (10)
Use the following dynamic programming based recurrence edit distance to find the possible edit
scripts while converting “ACTUAL “to “VIRTUAL”.