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
What are the specifications of mine shaft head gear​
svetlana [45]

Answer:

the depth of the shaft,

the carrying load of the skip and the mass of the counterweight,

the approximate size of the winding drum,

the approximate height of the headgear and the sheave wheel

4 0
3 years ago
Read 2 more answers
"In about 100 words, describe the idea behind software as a service (SaaS). In your answer, include at least three examples of e
Mama L [17]

Answer:

Explanation:

Saas refers to software as a service and can also be called software on demand .

It Isa software that is deployed over the internet rather than requiring to install an application .It offers different devices such as pay as you go , subscription model and service on demand model .

Only a compatible browser is needed to access the software .

Electronic packages or components that aree offered as an Saas

1)Shopify

2)Big commerce

3)Slack

3 0
3 years ago
What cold, hard facts support your position?
Sladkaya [172]
Idk what is it?
a computer?
plz mark me as brainliest
6 0
3 years ago
What would be the output of system.out.println("fun\tny");
netineya [11]

Answer:

use google

Explanation:

8 0
3 years ago
Write a Python function that takes a positive integer N and returns the factorial of N, i.e., N! The factorial of N, denoted N!,
sesenic [268]

Answer:

The python function is as follows:

def fact(N):

   factorial = 1

   for i in range(1,N+1):

       factorial = factorial * i

   return(factorial)

Explanation:

This line defines the function

def fact(N):

This line initializes the product of 1 to N to 1

   factorial = 1

This line iterates through 1 to N

   for i in range(1,N+1):

This line calculates the product of 1 to N i.e. factorial

       factorial = factorial * i

This line returns the factorial

   return(factorial)

6 0
3 years ago
Other questions:
  • If a gas gosts 3.60 per gallon how much doe sit cost to drive 500 miles in the city
    5·1 answer
  • A/An ___ is a series of instructions or commands that computer follows used to create software
    10·2 answers
  • You've decided to use a subnet mask of 255.255.192.0 with your 172.17.0.0 network to create four separate subnets. The network I
    13·1 answer
  • 5. Pins on Pinterest can be linked to
    8·1 answer
  • The smallest building block of a wireless lan is a ______.
    5·1 answer
  • How to connect xbox one controller
    5·1 answer
  • Anthony is responsible for tuning his organization's intrusion detection system. He notices that the system reports an intrusion
    8·1 answer
  • Claire wants to include animations in her presentation slides. Which element of the presentation programs interface will have th
    11·2 answers
  • What are some of these new iPad extras? One is the iMarker. Crayola teamed up with another company to make it. It costs $29.99.
    8·1 answer
  • How do i stop my computer from automatically connecting to a wireless network
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!