1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Nastasia [14]
3 years ago
8

Recall the problem of finding the number of inversions. As in the text, we are given a sequence of n numbers a1, . . . , an, whi

ch we assume are all distinct, and we define an inversion to be a pair i < j such that ai > aj.
We motivated the problem of counting inversions as a good measure of how different two orderings are. However, one might feel that this measure is too sensitive. Let’s call a pair a significant inversion if i < j and ai > 2aj. Give an O(n log n) algorithm to count the number of significant inversions between two orderings.
Computers and Technology
1 answer:
Kay [80]3 years ago
5 0

Answer:

The algorithm is very similar to the algorithm of counting inversions. The only change is that here we separate the counting of significant inversions from the merge-sort process.

Algorithm:

Let A = (a1, a2, . . . , an).

Function CountSigInv(A[1...n])

if n = 1 return 0; //base case

Let L := A[1...floor(n/2)]; // Get the first half of A

Let R := A[floor(n/2)+1...n]; // Get the second half of A

//Recurse on L. Return B, the sorted L,

//and x, the number of significant inversions in $L$

Let B, x := CountSigInv(L);

Let C, y := CountSigInv(R); //Do the counting of significant split inversions

Let i := 1;

Let j := 1;

Let z := 0;

// to count the number of significant split inversions while(i <= length(B) and j <= length(C)) if(B[i] > 2*C[j]) z += length(B)-i+1; j += 1; else i += 1;

//the normal merge-sort process i := 1; j := 1;

//the sorted A to be output Let D[1...n] be an array of length n, and every entry is initialized with 0; for k = 1 to n if B[i] < C[j] D[k] = B[i]; i += 1; else D[k] = C[j]; j += 1; return D, (x + y + z);

Runtime Analysis: At each level, both the counting of significant split inversions and the normal merge-sort process take O(n) time, because we take a linear scan in both cases. Also, at each level, we break the problem into two subproblems and the size of each subproblem is n/2. Hence, the recurrence relation is T(n) = 2T(n/2) + O(n). So in total, the time complexity is O(n log n).

Explanation:

You might be interested in
Who were 4 major people that attended the constitutional convention
postnew [5]
Alexander Hamilton, George Washington, James Madison, and Benjamin Franklin
7 0
3 years ago
________ is an encryption standard used for secure transactions such as credit card processing and online banking. TLS DMZ White
Fynjy0 [20]

Answer:

TLS

Explanation:

In the field of computer security, TLS refers to Transport Layer Security it is closely related to the Secure Sockets Layer (SSL) although TLS is more commonly used these days. They are both techniques in cryptography that provides for the safe transfer of information between two parties (servers, systems and user applications)

TLS particularly provides a balance between transmission speed and data security through the use of symetric and asymmetric cryptography and the encryption and decryption key is the session key at both ends (sender and reciever), as such TLS has found usage in most advanced data exchange systems like credit card processing and online banking.

8 0
3 years ago
PLZ HELP !!!!! <br> plzzzz
kozerog [31]

Answer:

Producers

Explanation:

Producers manufacture and provide goods and services to consumers.

7 0
3 years ago
Please name the OOP term that allows children classes to have methods with the same names as methods in their parents.
RSB [31]

Answer:

Inheritance

Explanation:

3 0
3 years ago
[20 pts] Write the function rectangle(perimeter, area), which takes two positive integers, perimeter and area. It returns an int
MrRissso [65]

Hi, you haven't provided the programing language in which you need the code, I'll explain how to do it using Python, and you can follow the same logic to make a program in the programing language that you need.

Answer:

import math

def rectangle(perimeter, area):

   l1_1 = (perimeter+math.sqrt((perimeter**2)-(16*area)))/4

   l1_2 = (perimeter-math.sqrt((perimeter**2)-(16*area)))/4

   l2_1 = area/l1_1

   l2_2 = area/l1_2

   print(l1_1,l2_1)

   print(l1_2,l2_2)

   if l1_1.is_integer() and l2_1.is_integer() and l1_1>0 and l2_1>0:

       return(int(max(l1_1,l2_1)))

   elif l1_2.is_integer() and l2_2.is_integer() and l1_2>0 and l2_2>0:

       return(int(max(l1_2,l2_2)))

   else:

       return(None)

Explanation:

  • We import math to make basic operations
  • We define the rectangle function that receives perimeter and area
  • We calculate one of the sides (l1_1) of the rectangle using the quadratic equation to solve 2h^2 - ph + 2a = 0
  • We calculate the second root of the quadratic equation for the same side (l1_2)
  • We calculate the second side of the rectangle using the first root on w = a/h
  • We calculate the second side of the rectangle using the second root on w= a/h
  • We verify that each component of the first result (l1_1, l2_1) is an integer (using the build-in method .is_integer) and greater than 0, if True we return the maximum value between them (using the max function) as w
  • If the first pair of sides evaluate to False we check the second root of the equation and if they meet the specification we return the max value
  • if all the if statements evaluate to false we return None to indicate that not positive or integer sides were found

7 0
3 years ago
Other questions:
  • Joshua is creating his résumé, in which section will he add projects and trainings he was involved in?
    10·1 answer
  • When programming in Scratch, to make our Sprite walk across the background, in which category would we find the programming bloc
    7·1 answer
  • Your program is going to compare the distinct salaries of two individuals for the last 5 years. If the salary for the two indivi
    15·1 answer
  • Can you give me a long list of anime
    6·2 answers
  • An instruction book or program that takes users through a prescribed series of steps to learn how to use a program is called (a)
    10·1 answer
  • Assume that a function with this header: function amountSaved(price, discountRate, salesTaxRate) already exists. Write a single
    14·1 answer
  • Referat noaptea la școala cu sfârșit de groază​
    10·1 answer
  • A keyboard, mouse, and microphone are examples of ________.
    9·2 answers
  • LIST THE 7 BEST PROGRAMMING MOVIES 2020-2021.
    9·1 answer
  • A company creates a ______by using a wireless access point (WAP) and an Internet connection. Select the two correct answers, the
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!