Question

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

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-------------------------------------------------------------------------------

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. 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 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 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 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 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 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 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 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 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

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 17 minutes ago

asked 40 minutes ago

asked 40 minutes ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago

asked 3 hours ago

asked 3 hours ago

asked 3 hours ago