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
rewona [7]
4 years ago
7

Give an O(log m + log n)-time algorithm that takes two sorted lists of sizes m and n, respectively, as input and returns the ith

smallest element in the union of the two lists. Justify your algorithm and analyze its running time.
Computers and Technology
1 answer:
olga2289 [7]4 years ago
7 0

Binary search is used similarly. K'th element is found in more productive way.

<u>Explanation:</u>

arr1 and arr2 are the middle elements which are compared, let us compute as mid1 and mid2. Let us predict arr1 [mid1] k, the elements are not needed after mid2 elements.  arr2 are set as last element for arr2 [mid2].  New sub problems are defined. When one array is half the size.

C++ code for the algorithm.

#include <iostream>

using namespace std;    

int kth(int *arr1, int *arr2, int *end1, int *end2, int k)

{

if (arr1 == end1)

return arr2[k];

if (arr2 == end2)

return arr1[k];

int mid1 = (end1 - arr1) / 2;

int mid2 = (end2 - arr2) / 2;

if (mid1 + mid2 < k)

{

if (arr1[mid1] > arr2[mid2])

return kth(arr1, arr2 + mid2 + 1, end1, end2,

k - mid2 - 1);

else

return kth(arr1 + mid1 + 1, arr2, end1, end2,

k - mid1 - 1);

}

else

{

if (arr1[mid1] > arr2[mid2])

return kth(arr1, arr2, arr1 + mid1, end2, k);

else

return kth(arr1, arr2, end1, arr2 + mid2, k);

}    

int main()

{

int arr1[5] = {2, 3, 6, 7, 9};

int arr2[4] = {1, 4, 8, 10};    

int k = 5;

cout << kth(arr1, arr2, arr1 + 5, arr2 + 4, k - 1);

return 0;

}

You might be interested in
You've been hired by Maple Marvels to write a C++ console application that displays information about the number of leaves that
ELEN [110]

Answer:

#include <iostream>

#iclude <iomanip>

#include <algorithm>

using namespace std;

int main(){

int num1, num2, num3,

int sum, maxDrop, minDrop = 0;

float avg;

string end = "\n";

cout << " Enter the leaf drop for September: ";

cin >> num1 >> endl = end;

cout << "Enter the leaf drop for October: ";

cin >> num2 >> endl = end;

cout << "Enter the leaf drop for November: ";

cin >> num3 >> endl = end;

int numbers[3] = {num1, num2, num3} ;

string month[3] = { "September", "October", "November"}

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

 if (numbers[i] < 0) {

   cout << "Error: all leaf counts must be at least zero\n";

   cout << "End of Maple Marvels\n";

   cout << "Welcome to Maple Marvels";

   break;

 } else if (number[i] >= 0 ) {

     sum += number[i] ;

   }

}

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

 cout << month[i] << " leaf drop: " << numbers[i] << endl = end;

}

cout << "Total drop: " << sum << endl = end;

cout << setprecision(3) << fixed;

cout << "Average drop: " << sum / 3<< endl = end;

maxDrop = max( num1, num2, num3);

minDrop = min(num1, num2, num3);

int n = sizeof(numbers)/sizeof(numbers[0]);

auto itr = find(number, number + n, maxDrop);

cout << "Highest drop: "<< month[ distance(numbers, itr) ] << endl = end;

auto itr1 = find(number, number + n, minDrop);

cout << "Lowest drop: " << month[ distance(numbers, itr1) ] << endl = end;

cout << "End of Maple Marvels";

Explanation:

The C++ soucre code above receives three integer user input and calculates the total number, average, minimum and maximum number of leaf drop per month, if the input isn't less than zero.

6 0
3 years ago
Drag the tiles to the correct boxes to complete the pairs.
Mice21 [21]

Answer:

Operation open purpose

8 0
3 years ago
Read 2 more answers
Write a calculator program that keeps track of a subtotal like real calculators do. Start by asking the user for an initial numb
Taya2010 [7]

Answer:

num1 = float(input("Enter the first number: "))

while True:

   print("Add, Subtract, Multiply, Divide, or Quit ?")

   choice = input("Your choice is: ")

   if choice == "Quit":

       break

   num2 = float(input("Enter the second number: "))

   if choice == "Add":

       num1 += + num2

       print("The subtotal is: " + str(num1))

   elif choice == "Subtract":

       num1 -= num2

       print("The subtotal is: " + str(num1))

   elif choice == "Multiply":

       num1 *= num2

       print("The subtotal is: " + str(num1))

   elif choice == "Divide":

       num1 /= num2

       print("The subtotal is: " + str(num1))

print("The final result is: " + str(num1))

Explanation:

Ask the user for the first number

Create a while loop that iterates until specified condition occurs inside the loop

Ask the user for the operation or quitting

If the user chooses quitting, stop the loop. Otherwise, get the second number, perform the operation and print the subtotal

When the loop is done, the user enters Quit, print the final value result

8 0
3 years ago
(3 marks)
muminat

Answer: 1.5 : 1

Explanation:

The average of 92 marks for the test is a weighted average of the proportion of students in the class.

Assume boys are in the proportion, x.

(90 * x) + (95 * (1 - x)) = 92

90x + 95 - 95x = 92

-5x = 92 - 95

-5x = -3

x = -3/-5

x = 0.6

Boys are 0.6 of the class

Girls are:

= 1 - 0.6

= 0.4

0.6 : 0.4

1.5 : 1

3 0
3 years ago
A program that is used to view websites is called a​
Nookie1986 [14]

Answer:

A web browser

examples of this would be

Bing

6 0
3 years ago
Read 2 more answers
Other questions:
  • To move down one paragraph, press the ____ key(s).
    15·1 answer
  • The graphical user interface (GUI) was pioneered in the mid-1970s by researchers at:
    10·2 answers
  • Which step can most directly help your team follow up on decisions made during Web development meetings?This task contains the r
    6·1 answer
  • HURRY! The steps for printing mailing labels are available after you click which icon?
    15·1 answer
  • This toolbar can be used to change the way the text in your presentation looks. Drawing
    5·2 answers
  • Which of the following should you NOT do when using CSS3 properties to create text columns for an article element? a. make the c
    12·2 answers
  • Refer to the exhibit. If a hacker on the outside network sends an IP packet with source address 172.30.1.50, destination address
    11·1 answer
  • What is the final value for X ?<br><br> x= 1<br><br> x=13<br><br> x= x+3<br><br> x=0
    9·1 answer
  • 14 Copy a picture of a crane on the next page. Do not trace them. Make a freehand sketch. (2) 2 Look at the placed where the Mar
    11·1 answer
  • PLS HELP I GOT 30 MINS TO TURN THIS IN!!!
    7·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!