For the following set of points, describe how the CLOSEST-PAIR algorithm finds a closest pair of points: (3) (3,2),(2,1)...
For the following set of points, describe how the
CLOSEST-PAIR algorithm finds a closest pair
of points: (3)
(3,2),(2,1),(2,3),(1,2),(3,1),(2,2),(1,3),(3,−1),(5,−2)
Homework Answers
![GCC 4.8.2] on linux Cormparing (3, 2) & (2. 1) Distance: 2 Updating rinimum distance as it is better. Conparing (3, 2) & (2,](http://img.homeworklib.com/images/c64900f4-7227-4e78-b8b1-f222a248151a.png?x-oss-process=image/resize,w_560)
Flow:
We keep a mindistance variable to hold the result for the minimum
distance found till now. We start making pairs of each point and
then find the distance between them. If the distance between them
is lower than the minDistance found till now, then they become our
result set.. Using this procedure, we keep improving our result
set.
Flow output:
Comparing (3, 2) & (2, 1) Distance: 2
Updating minimum distance as it is better.
Comparing (3, 2) & (2, 3) Distance: 2
Comparing (3, 2) & (1, 2) Distance: 4
Comparing (3, 2) & (3, 1) Distance: 1
Updating minimum distance as it is better.
Comparing (3, 2) & (2, 2) Distance: 1
Comparing (3, 2) & (1, 3) Distance: 5
Comparing (3, 2) & (3, -1) Distance: 9
Comparing (3, 2) & (5, -2) Distance: 20
Comparing (2, 1) & (2, 3) Distance: 4
Comparing (2, 1) & (1, 2) Distance: 2
Comparing (2, 1) & (3, 1) Distance: 1
Comparing (2, 1) & (2, 2) Distance: 1
Comparing (2, 1) & (1, 3) Distance: 5
Comparing (2, 1) & (3, -1) Distance: 5
Comparing (2, 1) & (5, -2) Distance: 18
Comparing (2, 3) & (1, 2) Distance: 2
Comparing (2, 3) & (3, 1) Distance: 5
Comparing (2, 3) & (2, 2) Distance: 1
Comparing (2, 3) & (1, 3) Distance: 1
Comparing (2, 3) & (3, -1) Distance: 17
Comparing (2, 3) & (5, -2) Distance: 34
Comparing (1, 2) & (3, 1) Distance: 5
Comparing (1, 2) & (2, 2) Distance: 1
Comparing (1, 2) & (1, 3) Distance: 1
Comparing (1, 2) & (3, -1) Distance: 13
Comparing (1, 2) & (5, -2) Distance: 32
Comparing (3, 1) & (2, 2) Distance: 2
Comparing (3, 1) & (1, 3) Distance: 8
Comparing (3, 1) & (3, -1) Distance: 4
Comparing (3, 1) & (5, -2) Distance: 13
Comparing (2, 2) & (1, 3) Distance: 2
Comparing (2, 2) & (3, -1) Distance: 10
Comparing (2, 2) & (5, -2) Distance: 25
Comparing (1, 3) & (3, -1) Distance: 20
Comparing (1, 3) & (5, -2) Distance: 41
Comparing (3, -1) & (5, -2) Distance: 5
Result: Closest pair: (3, 2) (3, 1)
I have written a python code, just in case you want it:
# though the distance is the square root of the difference
# but because we just want to compare and find closest pair,
# it is fine and simple
def pairDistance(p1, p2):
return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2
pairs = [(3,2),(2,1),(2,3),(1,2),(3,1),(2,2),(1,3),(3,-1), (5,-2)]
minDistance = None
index1 = None
index2 = None
for i in range(len(pairs)):
for j in range(i + 1, len(pairs)):
# compare point i and j.
dist = pairDistance(pairs[i], pairs[j])
print('Comparing', pairs[i], '&', pairs[j], 'Distance:', dist)
if minDistance is None or minDistance > dist:
print('Updating minimum distance as it is better.')
minDistance = dist
index1, index2 = i, j
print('Result: Closest pair: ', pairs[index1], pairs[index2])Add Answer to:
For the following set of points, describe how the CLOSEST-PAIR algorithm finds a closest pair of points: (3) (3,2),(2,1)...
Find all pure strategy Nash Equilibria in the following games a.) Player 2 b1 b2...
Find all pure strategy Nash Equilibria in the following games a.) Player 2 b1 b2 b3 a1 1,3 2,2 1,2 a2 2,3 2,3 2,1 a3 1,1 1,2 3,2 a4 1,2 3,1 2,3 Player 1 b.) Player 2 A B C D A 1,3 3,1 0,2 1,1 B 1,2 1,2 2,3 1,1 C 3,2 2,1 1,3 0,3 D 2,0 3,0 1,1 2,2 Player 1 c.) Player 2 S B S 3,2 1,1 B 0,0 2,3
Consider the following. (Assume that the dice are distinguishable and that what is observed are t...
Consider the following. (Assume that the dice are distinguishable and that what is observed are the numbers that face up.) HINT [See Examples 1-3.] Two distinguishable dice are rolled; the numbers add to 7. Describe the sample space S of the experiment. (Select all that apply.) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (1,1) (1,2)...
Calculate the probability of the following events A the first number is 2 or 3 or4...
Calculate the probability of the following events A the first number is 2 or 3 or4 B P(A) P(B) P(not A) P(not B) P(A or B) the second number is 1 or 2 or 3 P(A and B) P(A given B) 2 Dice Sample Space 1,6 1,5 2,5 3,5 4,5 5,5 1,4 1,1 2,1 3,1 4,1 5,1 6,1 1,2 2,2 3,2 4,2 5,2 6,2 1,3 2,3 3,3 4,3 5,3 6,3 2,6 3,6 4,6 2,4 3,4 4,4 5,4 6,4 5,6 6,5...
Calculate the probability of the following events A the first number is 2 or 3 or...
Calculate the probability of the following events A the first number is 2 or 3 or 4 E the second digit is 3 or less F the second digit is 4 or greater PIE or F) P(E and F) P(A) P( A and E) P( A and F) P( A and E)+P( Aand F) 2 Dice Sample Space 1,1 2,1 3,1 4,1 5,1 1,6 1,2 2,2 3,2 4,2 5,2 6,2 1,3 2,3 3,3 4,3 5,3 6,3 1,5 2,4 3,4 4,4...
Consider the algorithm to find the closest pair of points in the plane. Let's say you wanted to generalize the algorithm to find the two closest pairs of points in the plane given a set of (unsor...
Consider the algorithm to find the closest pair of points in the plane. Let's say you wanted to generalize the algorithm to find the two closest pairs of points in the plane given a set of (unsorted) points (p1, py. Give an algorithm for finding the two distances for this pair. In the step to conquer the two subproblems, you must explain why your algorithm is guaranteed to find the correct result. You do not need to specify the best...
Preferences J. There are two goods, I and 12, and the possible combinations (bundles) are X...
Preferences
J. There are two goods, I and 12, and the possible combinations (bundles) are X = {(1,1),(1,2), (1,3), (2.1). (2.2), (2,3)}. For the following two preferences fill in the set <= {(1, y) EX XX:13 y}. 1. Lexi's preferences, 3, over these goods can be described by "More of good 2 is always better than any amount of good 1, but given two bundles with the same amount of good 2, more of good 1 is better than less."...
Calculate the probability of the following events:
Calculate the probability of the following events: C = the sum of the digits is less than or equal to 6 D = the sum of the digits is greater than or equal to 7 P(C) P(D) P(C or D) P(C and D) 2 Dice Sample Space 1,11,21,31,41,51,62,12,22,32,42,52,63,13,23,33,43,53,64,14,24,34,44,54,65,15,25,35,45,55,66,16,26,36,46,56,6
1. First find all the closest pairs of points among this set of points. Then choose...
1.
First find all the closest pairs of points among this set of
points.
Then choose a pair of points below such that the first point is
in a closest pair, and the second point is NOT in a closest
pair.
a)
(12,8) and (12,1)
b)
(20,7) and (1,3)
c)
(1,3) and (27,8)
d)
(8,10) and (1,3)
(4.7)(8,10) (12.8) (16,10) (20,7) (27,8) (1,3) (8,4) (12,1) (16, 3) (20,1) (24,4)
Iculate the probability of the foltowing events G first digit 1, 2, or 3 P(F) P(G)...
Iculate the probability of the foltowing events G first digit 1, 2, or 3 P(F) P(G) | F-sum of digits-4 P(F and G) P(F given G) P(F and G)/P(G) 2 Dice Sample Space 1,6 2,6 3,6 1,5 1,1 2,1 3,1 4,1 5,1 1,2 2,2 3,2 4,2 5,2 6,2 1,3 2,3 3,3 4,3 5,3 6,3 1,4 2,4 3,4 4,4 5,4 6,4 2,5 3,5 4,5 4,6 5,5 5,6 6,5 6,6 6,1 25/2018 HW 2- Probability 1
S5. Consider the following game table: COLIN North South East West Earth 1,3 3,1 0,2 1,1...
S5. Consider the following game table: COLIN North South East West Earth 1,3 3,1 0,2 1,1 Water 1,2 1,2 2,3 1,1 ROWENA Wind 3,2 2,1 1,3 0,3 Fire 2,0 3,0 1,1 2,2 124 [CH. 4] SIMULTANEOUS-MOVE GAMES: DISCRETE STRATEGIES (a) Does either Rowena or Colin have a dominant strategy? Explain why or why not. (b) Use iterated elimination of dominated strategies to reduce the game as much as possible. Give the order in which the eliminations occur and give the...
Calculate the probability of the following events A the first number is 2 or 3 or4 B P(A) P(B) P(not A) P(not B) P(A or B) the second number is 1 or 2 or 3 P(A and B) P(A given B) 2 Dice Sample Space 1,6 1,5 2,5 3,5 4,5 5,5 1,4 1,1 2,1 3,1 4,1 5,1 6,1 1,2 2,2 3,2 4,2 5,2 6,2 1,3 2,3 3,3 4,3 5,3 6,3 2,6 3,6 4,6 2,4 3,4 4,4 5,4 6,4 5,6 6,5...
Calculate the probability of the following events A the first number is 2 or 3 or 4 E the second digit is 3 or less F the second digit is 4 or greater PIE or F) P(E and F) P(A) P( A and E) P( A and F) P( A and E)+P( Aand F) 2 Dice Sample Space 1,1 2,1 3,1 4,1 5,1 1,6 1,2 2,2 3,2 4,2 5,2 6,2 1,3 2,3 3,3 4,3 5,3 6,3 1,5 2,4 3,4 4,4...
Consider the algorithm to find the closest pair of points in the plane. Let's say you wanted to generalize the algorithm to find the two closest pairs of points in the plane given a set of (unsorted) points (p1, py. Give an algorithm for finding the two distances for this pair. In the step to conquer the two subproblems, you must explain why your algorithm is guaranteed to find the correct result. You do not need to specify the best...
Preferences
J. There are two goods, I and 12, and the possible combinations (bundles) are X = {(1,1),(1,2), (1,3), (2.1). (2.2), (2,3)}. For the following two preferences fill in the set <= {(1, y) EX XX:13 y}. 1. Lexi's preferences, 3, over these goods can be described by "More of good 2 is always better than any amount of good 1, but given two bundles with the same amount of good 2, more of good 1 is better than less."...
1.
First find all the closest pairs of points among this set of
points.
Then choose a pair of points below such that the first point is
in a closest pair, and the second point is NOT in a closest
pair.
a)
(12,8) and (12,1)
b)
(20,7) and (1,3)
c)
(1,3) and (27,8)
d)
(8,10) and (1,3)
(4.7)(8,10) (12.8) (16,10) (20,7) (27,8) (1,3) (8,4) (12,1) (16, 3) (20,1) (24,4)
Iculate the probability of the foltowing events G first digit 1, 2, or 3 P(F) P(G) | F-sum of digits-4 P(F and G) P(F given G) P(F and G)/P(G) 2 Dice Sample Space 1,6 2,6 3,6 1,5 1,1 2,1 3,1 4,1 5,1 1,2 2,2 3,2 4,2 5,2 6,2 1,3 2,3 3,3 4,3 5,3 6,3 1,4 2,4 3,4 4,4 5,4 6,4 2,5 3,5 4,5 4,6 5,5 5,6 6,5 6,6 6,1 25/2018 HW 2- Probability 1
S5. Consider the following game table: COLIN North South East West Earth 1,3 3,1 0,2 1,1 Water 1,2 1,2 2,3 1,1 ROWENA Wind 3,2 2,1 1,3 0,3 Fire 2,0 3,0 1,1 2,2 124 [CH. 4] SIMULTANEOUS-MOVE GAMES: DISCRETE STRATEGIES (a) Does either Rowena or Colin have a dominant strategy? Explain why or why not. (b) Use iterated elimination of dominated strategies to reduce the game as much as possible. Give the order in which the eliminations occur and give the...
Most questions answered within 3 hours.
-
Using Python:
A Prime number is an integer greater than 1 that cannot be
formed by...
asked 17 minutes ago -
Read about Cokes strategy in Africa in the article below and
discuss the ethics of selling...
asked 4 minutes ago -
What made of a 40.0% NaOH solution should be diluted to 1.00 L
with water to...
asked 4 minutes ago -
Draw and describe the results of the Meselson-Stahl experiments
showing that DNA replication followed the Semi-conservative...
asked 9 minutes ago -
Deeply Explain the Following Web Development Softwares Along
With the Reasons to Choose them For Development....
asked 6 minutes ago -
essay question: why was Hurricane Katrina so devastating? How
and why did the levees break in...
asked 11 minutes ago -
Why might it be necessary to reduce consumer spending in order
to attain faster economic growth?...
asked 20 minutes ago -
Express your answer with the appropriate units.
1. How many milliliters of oxygen gas at STP...
asked 26 minutes ago -
A
solution is prepared by mixing 0.12L of 0.11 M sodium chloride with
0.26 L of...
asked 27 minutes ago -
Difference between follicle and egg.
Where exactly are LH and FSH located on the ovaries?
What...
asked 28 minutes ago -
D8AC:
Discuss in 500 words or more why Oracle 12c has introduced two
new roles –...
asked 28 minutes ago -
1) Who is a Hispanic consumer?
2) Who is a Latin consumer?
3) Are Hispanic and...
asked 46 minutes ago