Fundamentals of Algorithms

CS502-Spring 2011

ASSIGNMENT #2

Deadline

Your assignment must be uploaded/submitted at or before 6th May 2011

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:

• The assignment is submitted after due date.
• The submitted assignment does not open or run.
• The assignment is copied.

Objectives

This assignment will help you to understand the concept of recurrence relations and way

to solve then and writing asymptotic notation after analyzing and solving recurrences

.The other main focus is to learn dynamic programming applications and edit distance

problem solution using dynamic programming technique which will be ultimately

enhance your vision and logics to think critically and analytically.

Guidelines

1. In order to attempt this assignment you should have full command on Lecture #8 ,9 and Lecture # 17,18

2. In order to solve this assignment you have strong concepts about following topics

• Recurrence Relations and their solutions
• Dynamic programming technique and Edit distance problem

3. Normally these formulas are very handy:

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)

After analyzing the pseudo code for an algorithm following recurrence relation have been developed you are required to solve this recurrence relation using iterative method and make proper assumptions for final solution and give answer at end in asymptotic form.

Question# 2 (10)

Use the following dynamic programming based recurrence edit distance to find the possible edit

scripts while converting “INVENTION “to “CONVENTION”.