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
If you wish to include a header or footer on all pages in a publication, you will need to insert this by navigating to the _____
Marina86 [1]
If you wish to include a header or footer on all pages in a publication, you will need to insert this by navigation to the master page.
7 0
3 years ago
Read 2 more answers
What are the main components of a desktop PC and briefly describe their purposes.​
Norma-Jean [14]

Answer:

8 Standard Computer Components and What They Do

Explanation:

Motherboard. The motherboard is an important computer component because it’s what everything else connects to!

Power Supply. True to its name, the power supply powers all other components of the machine.

Central Processing Unit (CPU)

Random-access Memory (RAM)

Hard Disk Drive / Solid State Drive.

Video Card.

Optical Drives.

6 0
2 years ago
The ____ line for any e-mail messages you write should clearly state the intention of the e-mail..
KatRina [158]

The <u>subject </u>line for any e-mail messages you write should clearly state the intention of the e-mail.

Electronic mail (e-mail) is a method of digital communications in which messages are exchanged through the internet. The messages are sent from a sender to one or more receivers.  Depending on user’s perspective, every user uses e-mail differently.  Communicating via e-mail requires e-mail platforms such as G*mail, Ya*hoo! Mail, Hot*mail, and Out*look etc. In the every e-mail, there is a subject line that clearly state the intention of the e-mail.

Subject line is an important element of an e-mail. Through the subject line, the message written in the e-mail is briefly summarized in six to eight words. A clearly written subject line provides the recipient a clear understanding that why the email has been sent. When recipient replies back to the e-mail, the subject line is changed accordingly.

This is the subject line of the e-mail that convince the receiver whether to open and read the e-mail. So, it should be written in the way that gives clear intention of the e-mail. We can say that the subject line of the e-mail is the most significant few words in the whole e-mail to convey the main purpose of the e-mail.

You can learn more about subject line at

brainly.com/question/14572730

#SPJ4

3 0
1 year ago
Sam's take-home pay is $743. His deductions are $25 for OASDI, $5 for Medicare, and $27 for income tax. What is his gross pay? A
Katarina [22]

<u>Answer:</u>

A. $686.00

<u>Reasoning:</u>

25+5+27=57 So the total amount of the deductions is $57

Subtract 57 from 743

743 - 57 = 686

So he is left with 686

5 0
3 years ago
One interesting application of computers is to display graphs and bar charts. Write an application that reads five numbers betwe
Nezavi [6.7K]

Answer:

The answer to this question can be given by program that  are as follows

import java.util.*;

//import package for taking input from user.

public class Main   //define class

{

public static void main (String ag[] )   //define main function

{

 int number;

 Scanner input = new Scanner(System.in);

 for (int i = 0; i < 5; i ++)                       //loo for input.

 {

  System.out.print ("Enter a number between 1 - 30:  ");

  number = input.nextInt();          //input number by the user.

 

 }

 asterisk();           //calling function.

 }

public static void asterisk()          //defination of function.

{

    //body of function.

    int n;                   //local variable.

 for (n= 0; n <= 30; n++)                  //using loop for print asterisk

 {

 if (n !=0)

 //printf used for print value.

 System.out.printf("*", n );                  //print value.

 }

 

  for (n= 0; n <= 30; n++)         //using loop for print asterisk

  {

 if (n !=0)

 //printf used for print value.

 System.out.printf("*", n );     //print value.

 }

 

  for (n= 0; n <= 30; n++)          //using loop for print asterisk

  {

 if (n !=0)

 //printf used for print value.

 System.out.printf("*", n );          //print value.

 }

  for (n= 0; n <= 30; n++)            //using loop for print asterisk

 

 {

 if (n !=0)

 //printf used for print value.

 System.out.printf("*", n );               //print value.

 }

 

  for (n= 0; n <= 30; n++)             //using loop for print asterisk

  {

 if (n !=0)

 //printf used for print value.

 System.out.printf("*", n );             //print value.

 }

}

}

Output:

Enter a number between 1 - 30: 2

Enter a number between 1 - 30: 2

Enter a number between 1 - 30: 1  

Enter a number between 1 - 30: 3

Enter a number between 1 - 30: 4

*******************************************************************************

Explanation:

In this program we take 5 time input from the user and print the value in the form of (*) that can be explain in above output section.In that program we use printf method that is also used for print the value.

3 0
3 years ago
Other questions:
  • Which two fields in an Ethernet frame help synchronize device communica- tions but are not counted toward the frame’s size?
    11·1 answer
  • EDVAC stands for? on which theory it is made on?
    15·1 answer
  • A(n) ______ system is a set of programs that coordinates all the activities among computer or mobile device hardware. a. managem
    10·1 answer
  • What is one of the benefits of using templates for your email marketing campaigns?
    10·1 answer
  • What kind of app or technology would you like to create?  Why ? <br><br><br>​
    11·1 answer
  • Two system administrators who work in two different buildings for the same company want to open a communication channel between
    8·1 answer
  • . ____________is/are the JSP ImplicitObject(s).sessionapplicationconfigAll of GivenNone of Given
    9·1 answer
  • Which components must all tasks have? Check all that apply.
    10·1 answer
  • El botón de layout se usa para <br>​
    8·1 answer
  • Quick I need help ASAP
    7·2 answers
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!