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
emmasim [6.3K]
3 years ago
11

Let A be an array of n numbers. Recall that a pair of indices i, j is said to be under an inversion if A[i] > A[j] and i <

j. Design a divide-and-conquer based algorithm to count the number of inversions in an array of n numbers. You can start by splitting into two subproblems. Answer clearly how you do the merge step, then obtain a recurrence relation that captures the run time of the algorithm. Solve the recurrence relation. Write the complete pseudocode.

Computers and Technology
1 answer:
AysviL [449]3 years ago
5 0

Answer:

Check the explanation

Explanation:

#include <stdio.h>

int inversions(int a[], int low, int high)

{

int mid= (high+low)/2;

if(low>=high)return 0 ;

else

{

int l= inversions(a,low,mid);

int r=inversions(a,mid+1,high);

int total= 0 ;

for(int i = low;i<=mid;i++)

{

for(int j=mid+1;j<=high;j++)

if(a[i]>a[j])total++;

}

return total+ l+r ;

}

}

int main() {

int a[]={5,4,3,2,1};

printf("%d",inversions(a,0,4));

  return 0;

}

Check the output in the below attached image.

You might be interested in
Which Boolean operator enables you to exclude a search term?
Marysya12 [62]

Boolean Operators are simple words (AND, OR, NOT or AND NOT) used as conjunctions to combine or exclude keywords in a search.

The NOT Boolean operator enables you to exclude a search term. Correct answer: A  The NOR operator excludes words from the search  and by doing that it narrows the search, telling the database to ignore some concepts.

7 0
3 years ago
Read 2 more answers
Complete the following function to create a deep-copy on the heap of the argv array. Set the result pointer to point to your arr
irga5000 [103]

Answer:

Following are the code in the C programming Language.

//define function

void duplicate(char*argv, char**result) {

//set and initialize the variable to 0

int c = 0;

//set and initialize the char type pointer variable

char** t = argv;

//set the while loop

while(t){

//increment by 1

c++;

//increment by 1

t++;

}

//set malloc function in the pointer variable

result= malloc(sizeof(char)*(c+1));

//set the for loop

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

//set malloc function in the pointer

(*result)[i] = malloc(strlen(argv[i])+1);

//copy the character from memory

memcpy(argv[i], (*result)[i], strlen(argv[i])+1) ;

}

//initialize null in the pointer

(*result)[i] = NULL;

}

Explanation:

In the following code, we define function "duplicate()" and pass two character type pointer arguments "*argv" and "**result" and inside the function.

  • Set an integer type variable "c" and initialize to 0.
  • Set character type pointer variable "t" and initialize the value of pointer variable "argv".
  • Set the while loop and increment in the variable "c" and "t" by 1.
  • Set the malloc function in the pointer variable "result".
  • Set the for loop to copy the character from the memory.
  • Finally, initialize the pointer variable "result" to NULL.
8 0
3 years ago
If we are using an 4-character password that contains only lowercase English alphabetic characters (26 different characters), ho
Trava [24]

Answer:

11,424,400 possible passwords

Explanation:

Since all characters are letters and only lowercase

we have 26∧4 = 456,976 possibilities

For a 5-character password which is still lower case sensitive.

we have 26∧5 = 11,881,376 possibilities

Many more possible passwords = (11881376-456976)

= 11,424,400 possible passwords

6 0
3 years ago
Read 2 more answers
Can someone write me a design brief about a stadium​
Delicious77 [7]

Btw..which dtadium do u want cricket or football!?

3 0
3 years ago
Read 2 more answers
One acre of land is equivalent to 43,560 square feet. Write a program that asks the user to enter the total square feet in a tra
lana [24]

Answer:

Explanation:

Using Python programming language:

def get_number_acres(square_feet):

   return square_feet / 43560

sq_feet = input('Enter the number of square feets >>> ')

number_acres = get_number_acres(sq_feet)

7 0
3 years ago
Other questions:
  • Can someone can help me am dont know how much RAM do i need. I use my pc for work and to watch yt vid. Thanks​
    10·1 answer
  • What New England industry quickly collapsed with the discovery of oil in Pennsylvania?
    11·2 answers
  • The Internet of Things (IoT) is a global information architecture that could contain
    12·1 answer
  • ____ assigns a risk rating or score to each information asset. Although this number does not mean anything in absolute terms, it
    8·1 answer
  • What is an example of an attribute for a screen object
    14·1 answer
  • What is MS-Word? Write some versions of MS-Word.
    8·2 answers
  • Please tell fast plzzzzzz​
    6·1 answer
  • Spoderman memes<br> im scared-
    15·2 answers
  • Why is UPS necessary to connect with the computer​
    11·1 answer
  • WAP to find the area of cuboid​
    13·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!