Question

Problem 3 (5 marks). Suppose elements a[i] and a[i+k] are in the wrong order and we...

Problem 3 . Suppose elements a[i] and a[i+k] are in the wrong order and we swap them. Prove that this will remove at least 1 inversion but at most 2k − 1 inversions. (This is textbook problem 7.3.) Further explain why both the lower bound of 1 and the upper bound of 2k − 1 can be attained for any i, k, where k > 0

Homework Answers

Answer #1

To prove that one inversion is required at 2k-1 inversion is shown as follows:
The inversion that existed between A[i] and A[i+k] is removed. This shows at least one inversion is removed. Now let's consider A[i],A[i+1],…,A[i+k−1],A[i+k], Suppose A[i] is greater than A[i+1],…,A[i+k] and A[i+k] is smaller than A[i],…,A[i+k−1]. In this case, by swapping A[i] and A[i+k], we fix 2k−1 inversions (−1 is that A[i] greater than A[i+k] and A[i+k] smaller than A[i] points to the same inversion).


Another way to think about 2k−1 is that for each of the k−1 elements A[i+1],A[i+2],…,A[i+k−1], at most two inversions can be removed by exchange. For instance, for A[i+1], two inversions are A[i] and A[i+1], and A[i+1] and A[i+k] (i.e. for sequence 10,4,3, by swapping 10 and 3, we remove inversion {10,4} and {4,3}). Thus, a maximum of 2(k−1)+1=2k−1.

--------------------------------------------------Please Upvote-------------------------------------------------------------------------------

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Problem 4 (5 marks). Hibbard’s gap sequence for Shellsort is defined as follows. 2 k −...
Problem 4 . Hibbard’s gap sequence for Shellsort is defined as follows. 2 k − 1, 2 k−1 − 1, 2 k−2 − 1, . . . , 7, 3, 1 where k is the largest number satisfying 2k − 1 < N. (b) Implement Shellsort with Hibbard’s gap sequence, with Shell’s gap sequence, and with a gap sequence of your own invention, and compare them on three input/output examples for duplicate-free arrays of size 10, 100, and 1000 (one...
(1) Using a generator for a binomial distribution, we will test the results of Example 3.8.2....
(1) Using a generator for a binomial distribution, we will test the results of Example 3.8.2. Using software generate 500 random deviates for X from a B(10, 0.3) distribution and 500 random deviates for Y from a B(5, 0.3) distribution. Add corresponding random deviates from each distribution to form an empirical W=X+Y. Then use the theoretical result of Example 3.8.2 and directly generate another 500 random deviates for W from a B(15, 0.3). Order the result of the sum of...
Biology Unit I Homework - Nutritional Analysis Worksheet Introduction In Chapters 3 and 4 of the...
Biology Unit I Homework - Nutritional Analysis Worksheet Introduction In Chapters 3 and 4 of the textbook, you learned that the body needs various macro and micronutrients in order to function properly. You also learned about cellular metabolism and what the human body uses as a fuel source. This all seems simple at first glance; however, it can be difficult to determine whether we are getting what our body needs. Even when we know what our body needs, it becomes...
Write a Python 3 program called “parse.py” using the template for a Python program that we...
Write a Python 3 program called “parse.py” using the template for a Python program that we covered in this module. Note: Use this mod7.txt input file. Name your output file “output.txt”. Build your program using a main function and at least one other function. Give your input and output file names as command line arguments. Your program will read the input file, and will output the following information to the output file as well as printing it to the screen:...
THIS IS THE GENERAL EQUILIBRIUM PROBLEM THAT I PROMISED. YOU FIRST SOLVE FOR THE INITIAL EQUILIBRIUM...
THIS IS THE GENERAL EQUILIBRIUM PROBLEM THAT I PROMISED. YOU FIRST SOLVE FOR THE INITIAL EQUILIBRIUM AS POINT A. WE CONSIDER TWO DIFFERENT AND SEPARATE SHOCKS (I CALL THEM SCENARIOS). THE FIRST SHOCK IS TO THE IS CURVE, THE SECOND SHOCK IS A ‘LM’ SHOCK. AGAIN, WE CONSIDER THESE SHOCKS SEPARATELY SO THAT AFTER YOU COMPLETE SCENARIO 1 (THE IS SHOCK), WE GO BACK TO THE ORIGINAL CONDITIONS AND CONSIDER THE SECOND SCENARIO WHICH IS THE ‘LM’ SHOCK. Consider the...
Read the case and answer the following Multiple choice questions. There are 5 questions total, where...
Read the case and answer the following Multiple choice questions. There are 5 questions total, where some of them might have more than one correct answers. You can choose more than one options where you think is suitable for the above question. PERFORMANCE MANAGEMENT Project Manager Oliver Caine skimmed his notes as he waited for Ben Robins to come to the meeting room. He hoped Ben would arrive soon, as he wanted to get the con-versation finished quickly. Ben walked...
We constantly seem to be pricing ourselves out of some markets and not charging enough in...
We constantly seem to be pricing ourselves out of some markets and not charging enough in others. Our pricing policy is pretty simple: we mark up our full manufacturing cost by 50%. That means a computer that costs us $2,000 to manufacture will sell for $3,000. Until now I thought this was a workable approach, but now I’m not so sure. Steve Works, CEO, Cortland Manufacturing, Inc. (CMI) Steve’s Controller, Sally Nomer, had just told him that she believed the...
Team 5 answer the questions What are 4 key things you learned about the topic from...
Team 5 answer the questions What are 4 key things you learned about the topic from reading their paper? How does the topic relate to you and your current or past job? Critique the paper in terms of the organization and quality. Incentive Systems             In this paper, we will focus primarily on financial rewards that companies use to attract, retain and motivate the brightest and most talented candidates in the labor market. By providing a reward system that...
In narrative essay format, I want you to address a business/organization case study using multiple concepts...
In narrative essay format, I want you to address a business/organization case study using multiple concepts from class. The case question and case text begin on page 5 of this document. You need to demonstrate their best understanding of management and organizational behavior theory, and the application of those ideas to improve the understanding of various issues. You need to clearly identify at least 3 distinct, substantive issues. For each issue you need to 1), identify evidence from the case...
Analysis: This section should include the issue register as a bare minimum, but may include also...
Analysis: This section should include the issue register as a bare minimum, but may include also why-why diagrams, a Pareto chart, a waste table and/or value-added analysis table. Flow analysis or simulation of this case study might be possible but might require making a lot of assumptions given the provided data. The first part of the project: Introduction    Walmart has continued to retain the top position on the Fortune 500 list for a consecutive fifth year. The brand has...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT