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
egoroff_w [7]
3 years ago
15

Design a data structure to support the following two operations for a set S of inte- gers, which allows duplicate values: • INSE

RT(S, x) inserts x into S. • DELETE-LARGER-HALF(S) deletes the largest d|S|/2e elements from S. Explain how to implement this data structure so that any sequence of m INSERT and DELETE-LARGER-HALF operations runs in amortized O(1) time per op- eration. Your implementation should also include a way to output the elements of S in O(|S|) time. Prove the running time of your implementation.
Computers and Technology
1 answer:
umka2103 [35]3 years ago
7 0

Answer and Explanation:

Note that we are free to use any data structure that allows for arbitrary insertion and deletion of data

As an underlying data structure, we’ll use an (unsorted) array. INSERT(S, x) will  simply append x to the array, increasing its length. This has a constant runtime,  so we’ll say its cost is 1.

DELETE-LARGER-HALF(S) will work as follows: first, use SELECT to find the  median. Next, use PARTITION around the median to make sure that the upper half is stored within the last [|S|/2] elements. Finally, we delete these elements,  reducing the size of the array.This has a linear running time, so we’ll say its cost is n.

To show that any m operations can run in O(m) time, we define a potential  function \phi(S) = 2|S|. The amortized cost of INSERT is thus 1 + \delta \phi = 1 + 1 = 1 ;  the amortized cost of DELETE-LARGER-HALF is n +\delta\phi\leq n-2(n/2) = 0. So the  amortized cost of any m operations is O(m).

This answer essentially captures the idea behind the problem. However, there  are some technical points to clear up. (Calling the real-time costs 1 and n are not among them; this underestimates the running time by at most a constant. Ignoring constants like that is necessary to make concise arguments about amortized costs.)

First, an array does not support arbitrary insertions. Possible remedies include:

(1) using a dynamic array along the lines of §17.4, or (2) using a different structure  like a linked list, and having DELETE-LARGER-HALF convert it to an array and  back in linear time so that the SELECT and PARTITION algorithms may be used.

Second, it’s important to know which median to partition around and how to  delete the upper half of the elements: a mistake could lead to incorrect behavior when the array has an odd size or repeated elements. We should select the lower median,[|S|/2], since that’s the number of elements we want in the lower set: as  written, the CLRS Partition function will put elements less than or equal to the

pivot in the left set, and strictly larger elements in the right set. (If the partition function is defined differently, the answer should be different as well. You generally  should give a brief description of how your partition function works.) After a call to Partition, it is safe simply to keep the first [|S|/2] elements and drop the rest. On the other hand, it is not safe to go around deleting every element with

a sufficiently large value—take an array of zeros as a drastic example. If you wish  to take that approach, you’ll have to count the number of elements equal to the  median and delete the correct number of them.

Finally, the argument only shows that the <em>amortized</em> cost with respect to \phi is  O(m). The conclusion we’re asked for requires a technical condition: the potential  \phi never drops below its initial value. This is true for the usual reason: initially,  \phi = 0 because S is empty; during execution, \phi \geq 0  by definition.

You might be interested in
(BRAINLIEST QUESTION!!!)
docker41 [41]

Answer:

Possible if hackers are not so intelligent.

Explanation:

Actually, hackers are intelligent

where they will change location code in different places every second. So end-user who is trying to trace it he or she has to use their intelligence to find the exact location of hackers.

Normally hackers will generate different location places and by using decipher it is possible to find the location codes.

Since hackers used encrypted message we need to decrypts the message and find it out and understand the decrypt and encrypt technology used by hackers.

It is possible to by using decipher to get uncovered locations

4 0
3 years ago
(Count positive and negative numbers and compute the average of numbers) Write a program that reads an unspecified number of int
Papessa [141]

Answer:

Explanation:

Sorry it  is in Java, though you can covert it using converter

public class Exercise {

public static void main(String[] args) {

 Scanner input = new Scanner(System.in);

 int positives = 0;  // Count the number of positive numbers

 int negatives = 0;  // Count the number of negative numbers

 int count = 0;   // Count all numbers

 double total = 0;  // Accumulate a totol

 // Promopt the user to enter an integer or 0 to exit

 System.out.print("Enter an integer, the input ends if it is 0: ");

 int number = input.nextInt();

 if (number == 0) { // Test for sentinel value

  System.out.println("No numbers are entered except 0");

  System.exit(1);

 }

 while (number != 0) {// Test for sentinel value

  if (number > 0)

   positives++; // Increase positives

  else

   negatives++; // Increase negatives

  total += number; // Accumulate total

  count++;    // Increase the count

  number = input.nextInt();

 }

 // Calculate the average

 double average = total / count;

 // Display results

 System.out.println(

  "The number of positive is " + positives +

  "\nThe number of negatives is " + negatives +

  "\nThe total is total " + total +

  "\nThe average is " + average);

}

}

7 0
3 years ago
A review of the sales, costs, and profit projections for anew product to find out whether these factors satisfy the company'sobj
soldier1979 [14.2K]

Answer: Business analysis

Explanation:

Business analysis is the review of the sales, costs, and profit projections for a new product to find out whether these factors satisfy the company's objectives.

Based on the business analysis a company is able to set a marketing strategy for a better promotion of its products. So this step is particularly very important.

7 0
3 years ago
What kind of information can be found in a ROM:
tester [92]
The answer is C, ROM often stores the basic instructions a computer needs when powering on, part if the BIOS.
3 0
3 years ago
Mr. Lee wants to show his class a presentation. Which device will display an enlarged view of his presentation?
Gnesinka [82]
A projector would make his presentation bigger.<span />
3 0
3 years ago
Other questions:
  • In three to five sentences, describe how technology helps business professionals to be more efficient. Include examples of hardw
    10·1 answer
  • ​Which SQL keyword is used to search for records?
    8·1 answer
  • Describe some advantages of a 64-bit versus 32-bit version of windows.
    9·1 answer
  • D. What is the work of the following features:<br>1. Foot note​
    10·1 answer
  • Create a new class MyArray_DE and copy and paste the previous program. Be sure to rename the class to MyArray_DE. Modify the pro
    14·1 answer
  • Assume there are two variables, k and m, each already associated with a positive integer value and further assume that k's value
    13·1 answer
  • Helppppppppppppppp me please Can i have help for a ggogle class room
    5·1 answer
  • Redesign the cover of science textbook using at least two different graphics​
    7·1 answer
  • While conducting routine maintenance, you discover a network server that needs to
    15·1 answer
  • Html is a markup language that lets you identify common sections of a web page
    8·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!