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
Your boss bought a new printer with a USB 3.0 port, and it came with a USB 3.0 cable. Your boss asks you: Will the printer work
Greeley [361]

Answer:

Yes, is should work

Explanation:

USB is widely adopted and supports both forward and backward compatibility. The USB 3.0 printer should work with the USB 2.0 computer. However, having a connection like this, the printer will only be able to work at the speeds of the computer’s USB 2.0. By default, USB is built to allow transfer speeds improvement with upgrades from previous generations while still maintaining compatibility between devices that are supported by them.

4 0
2 years ago
Liza works as a receptionist. Around the lunch hour, she has a difficult time hearing the callers due to employees talking near
Rashid [163]
c.<span>barriers to communication
 because the other employees are the ones causing the trouble</span>
6 0
3 years ago
The concept that allows certain professions to use copyrighted material without permission in their work is called _____.
lesantik [10]
C) fair use

Hope this helps... mark as Brainliest plz
4 0
3 years ago
A group of statisticians at a local college has asked you to create a set of functions that compute the median and mode of a set
Vanyuwa [196]

Answer:

from functools import reduce

def mean(mylist):

   score = reduce(lambda x,y: x + y, mylist)/ len(mylist)

   return score

def median(mylist):

   sorted(mylist)

   list_len = len(mylist) % 2

   i = round(len(mylist)/2)

   x = len(mylist)//2

   if list_len == 0:

       median = (mylist[x] + mylist[x+1]) / 2  

   else:

       median = mylist[i]

   return median

def mode(mylist):

   unique = set(mylist)

   unique = list(unique)

   collector = [mylist.count(key) for key in unique]

   maxi = max(collector)

   loc = collector.index(maxi)

   return unique[loc]

def main():

   scores = input( 'Enter list of numbers: ').split(",")

   scores = [int(score) for score in scores]

   

   operation = input('Enter operation: ')

   operator = ['mean', 'median', 'mode']

   

   for x in iter(list, 0):

       if operation in operator:

           break

       print("Invalid operation: ")

       operation = input('Enter operation')

   

   index_loc = operator.index(operation)

   

   if index_loc == 0:

       return mean(scores)

   elif index_loc == 1:

       return median(scores)

       #return np.median(scores)  can be used of the defined function

   elif index_loc == 2:

       #return stats.mode(scores)[0]  can be used of the defined function

       return mode(scores)

print( main( ) )

Explanation:

The main python function calls conditionally three statistical functions namely mean, median and mode. It prompts for user input for a list of integer numbers and a function name name to return the corresponding result.

8 0
2 years ago
One of the most common causes of fires in the home and workplace is: a. All of the answer choices b. Arson c. Candle d. Faulty e
solniwko [45]
Electricity is one of the most common causes of fire in homes and workplaces. Electrical accidents appear to be caused by a combination of two factors: 1. Unsafe equipment and/or installation; 2. Workplaces made unsafe by the environment

So the answer would be D)Faulty electricity
8 0
3 years ago
Other questions:
  • People who work the total hours for which they get paid have
    7·2 answers
  • What do you think of my profile picture
    8·2 answers
  • Hat are three machines or devices that depend on gravity to work?
    5·1 answer
  • Which option will automatically update copied data?
    12·2 answers
  • Giving Brainliest IFFF CORRECT
    9·1 answer
  • What are the four steps for planning a table?​
    10·1 answer
  • Which statement best describes the computers all around us
    9·1 answer
  • The most common markup language used with web pages is ___________ Question 4 options: A. HTML B. VRML C. Javascript
    13·2 answers
  • Who is your favorite person from squid game?
    13·2 answers
  • ________ take advantage of vulnerabilities in software. Group of answer choices Blended threats Bots Trojan horses Direct-propag
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!