You are here:

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.

Hi,
1. (a) As the height of a binary tree with n nodes is log(n) hence inserting n elements would be
1 + 1 + 1 . log (2) + n log (n-1)
I am not sure if above comes to n log (n)

1 . (b) Not true, but one part of running time, other things come from lots of other issue like iteration/recurssion etc

Other problems are very hard for me to solve :--) now.

Thanks,
RaiD
Questioner's Rating
 Rating(1-10) Knowledgeability = 10 Clarity of Response = 10 Politeness = 10 Comment No Comment

C++

Volunteer

#### Dharmender Rai

##### Expertise

I can answer general and system level C/C++ questions.

##### Experience

I have 5 years of experience in C++.