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.

Sam Fredrick , Thank you for your question.

It is against my policy to do homework questions. I can help you with work that you have already done, but I cannot give you full answers.

Please attempt to do part of the work, and then ask a specific question when you get stuck.

Learning can be difficult, but doing your own work will repay your effort with good grades in school and success in your career.

You ask whether this material will be useful when you become a software engineer. The answer is yes. These topics are basic to writing many different kinds of programs. More importantly, working on these topics will help you to start thinking like an engineer.

David Spector

Questioner's Rating
 Rating(1-10) Knowledgeability = 10 Clarity of Response = 10 Politeness = 10 Comment Thanks for your Help After looking over the code a little more indepth, I figured out what the problem was. Sometimes my mind gets tired and I miss something that is simple Thanks Kurt

C++

Volunteer

#### David Spector

##### Expertise

Highly knowledgeable in the C++ language, Visual C++ (MSVC), Windows API, documentation and other quality-assurance techniques, and debugging. Knowledgeable in MFC, COM, GUI design, and object-oriented design.

##### Experience

I have been a software engineer since 1965. I have been published. My specializations have been: biomedical programming, compiler implementation, and many kinds of Windows programming. I don't do Databases or other business-oriented stuff.

Publications
Windows?/DOS Developer's Journal, ACM SIGPLAN Notices, and Computer Science Press.

Education/Credentials
ICCP Systems Programming Certification
Master's degree equivalent in Computer Science