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
Best practices and trends for technology integration
cluponka [151]

Answer:

Technology use must be aligned to the standards. Technology must be integrated into daily learning,

Explanation:

Technology use must be aligned to the standards. Technology must be integrated into daily learning, not used as an add-on to instruction to match personal learning needs. Students need opportunities to use technology collaboratively. Technology must support project based learning and include real-world simulations.

3 0
2 years ago
Let's revisit our lucky_number function. We want to change it, so that instead of printing the message, it returns the message.
maksim [4K]

Answer:

Replace the first blank with:

message = "Hello " + name + ". Your lucky number is " + str(number)

Replace the second blank with:

return message

Explanation:

The first blank needs to be filled with a variable; we can make use of any variable name as long as it follows the variable naming convention.

Having said that, I decided to make use of variable name "message", without the quotes

The next blank is meant to return the variable on the previous line;

Since the variable that was used is message, the next blank will be "return message", without the quotes

3 0
3 years ago
Write six causes of data lost
just olya [345]
<span>1. Deleting files accidentally
</span>

2. Viruses and damaging malware

3. Mechanical damages of hard drive

4. Power failures

5. Theft of computer

6. Spilling coffee, and other water damages

7. Fire accidents and explosions

<span>Hope this helps.</span>
3 0
3 years ago
Write a program that records high-score data for a fictitious game. the program will ask the user to enter five names, and five
Harman [31]

Scores.cpp

#include <iostream>

#include <string>

using namespace std;

void initializeArrays(string names[], int scores[], int size);

void sortData(string names[], int scores[], int size);

void displayData(const string names[], const int scores[], int size);

int main()

{

   string names[5];

   int scores[5];

   //reading names and scores

   initializeArrays(names, scores, 5);

   //sorting the lists based on score.

   sortData(names, scores, 5);

   //displaying the contents of both arrays

   displayData(names, scores, 5);

 

  return 0;

}

void initializeArrays(string names[], int scores[], int size){

   for(int i=0; i<size; i++){

       cout<<"Enter the name for score #"<<(i+1)<<": ";

       cin >> names[i];

       cout<<"Enter the score for score #"<<(i+1)<<": ";

       cin >> scores[i];

       }

}

void sortData(string names[], int scores[], int size){

   

       int temp = 0;

       string tempStr = "";

       

       for(int i=0; i < size; i++){

               for(int j=1; j < (size-i); j++){

                      //checking max score and sorting based on it.

                       if(scores[j-1]< scores[j]){

                               //swap the elements!

                           //swapping scores

                               temp = scores[j-1];

                               scores[j-1] = scores[j];

                               scores[j]=temp;

                               

                               //swapping names

                               tempStr = names[j-1];

                               names[j-1] = names[j];

                               names[j]=tempStr;

                       }

                       

               }

       }

}

void displayData(const string names[], const int scores[], int size){

   cout<<"Top Scorers:"<<endl;

       //printing the elements up to the size of both arrays.

       for(int i=0; i<size; i++){

           cout<<names[i]<<": "<<scores[i]<<endl;

       }

}

3 0
3 years ago
1. According to the Department of Commerce, _________ percent of single moms in the US qualified as poor.​
Allisa [31]

Answer:

. According to the Department of Commerce, 34.0% percent of single moms in the US qualified as poor.​

Explanation:

8 0
3 years ago
Other questions:
  • Clifford created a table using OpenOffice Writer and entered some information into the table. Later, he needed to add more rows
    15·2 answers
  • Which of the following best explains why some people invest their saving in the stock market and others put their saving in bank
    5·2 answers
  • Write a class named Episode. An instance of this episode class will represent a single episode of a TV show, with a title, a sea
    12·1 answer
  • Consider the following code segment.
    12·1 answer
  • How do you customize Track Changes in a text document?
    11·1 answer
  • Explain how the use of Git and a shared public Git repository simplifies the process of managing opensource development when man
    8·1 answer
  • Qwertyuiopasdfghjklzxcvbnm??
    14·2 answers
  • One of the functions of an IDE is to check for: flowchart errors. Syntax errors. memory errors X input and output.​
    12·2 answers
  • (25 POINTS)Which statement best reflects the importance of following safety guidelines?
    8·2 answers
  • After you log in to PowerPoint Online, what is the first thing you need to do to start creating a presentation?
    12·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!