Expert: Narendra - 6/20/2004

Question
Dear Sir,

Hope you must be fine and well. Sir! I am having great difficulty in understanding mathematical analysis of algorithms. My question is how much part this subject (algorithem analysis and design)plays in the future of a software engineer? And would u please please solve questions written below.I would be highly appreciated.Thanks a lot.

1. As an alternative to the insertion sorting method presented in class, you might consider using binarysearch to decide where each new element goes.a) Show that this will sort a list of n entries using O(n log n) comparisons.b) Does counting comparisons give a true idea of the running time of this algorithm?


2. The input consists of d sequences of elements such that each sequence is already sorted, and there is atotal of n elements. Design an O(n log d) algorithm to merge all the sequences into one sorted sequence.For example, in the case of merge sort, two (d = 2) are merged to form the final sorted sequence. Usesimple English to present your answer. Use pseudo code only if it explains the algorithm better. Hint:create min heap out of the elements of the sequences.

Programming questions.

1. Develop a C++ program that implements the Edit Distance algorithm. Your program should accepttwo strings and produce the value for the minimum edit distance value. It should also produce edit scriptthat converts one string into another. If there are more than one edit scripts, all such scripts should beproduced. Submit your C++ program.

2. Implement the DP 0-1 knapsack algorithm as a C++ program. It should accept as input the size of theknap sack and items along with their weights. For this problem, your program will work with integerweights only. The program should output the optimum weight and the items that go into the knapsack togive the optimum solution. Submit your C++ program.  

Answer
Data structures is a very important subject.
Algorithm Analysis is also important and will help in choosing a correct algorithm for a given problem.

But, right now I don't have time to analyze and give solutions to the problems/questions that you have posed. It will take lot of time to analyze.....
So, I suggest you to do it yourself.
If you have not understood the problem, then get hold of a good book on the subject and understand it properly.
It will definitely help you if you are going to pursue the software career.

-ssnkumar