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
The find_item functions uses binary search to recursively locate an item is the list, returning true if found, false otherwise.
bagirrra123 [75]

Answer:

def find_item(listed, item):

   listed.sort()

   #Returns True if the item is in the list, False if not.

   if len(listed) == 0:

       return False

   middle = int(len(listed)/2)

   #Is the item in the first half of the list?

   if item < listed[middle]:

   #Call the function with the first half of the list

       return find_item(listed[:middle], item)

   

   #Is the item in the center of the list?

   if listed[middle] == item:

       return True

   else:

   #Call the function with the second half of the list

       return find_item(listed[middle+1:], item)

   return False

list_of_names = ["Parker", "Drew", "Cameron", "Logan", "Alex", "Chris", "Terry", "Jamie", "Jordan", "Taylor"]

print(find_item(list_of_names, "Alex")) # True

print(find_item(list_of_names, "Andrew")) # False

print(find_item(list_of_names, "Drew")) # True

print(find_item(list_of_names, "Jared")) # False

Explanation:

The defined python function is used to implement a binary search, the function is recursively called in the function statement, but for it to work on the list ( ie, search for an item in the list), the list must be sorted in ascending order (default).

7 0
3 years ago
Breaking down a problem to find the solution is called:
velikii [3]
I would say B.......
7 0
3 years ago
A_________is a way for students to keep track of information during research.
Fudgin [204]
Note pad your welcome


4 0
3 years ago
When preparing the heading for an MLA Format Academic Report, which of the following shows the proper order of the for lines of
Sloan [31]

Answer:

A. Student Name, Instructor, Course, Date

Explanation:

Begin one inch from the top of the first page and flush with the left margin. Type your name, your instructor's name, the course number, and the date on separate lines, using double spaces between each. Double space once more and center the title

3 0
3 years ago
You are helping a friend in college with his network connection. He would like a high speed connection between his computers so
inna [77]

Solution :

Set up the router as follows:

On the Shelf, expand the Routers. And read the description for each of the devices. Drag the Ethernet $100/1000TX$ router with the firewall to the Workspace.

Connection of the router as follows:

Above the router, select the Back to switch to the back view of the router. Then select the cable currently connected to the wall plate and then drag it to a $LAN$ port on the router. Above the Dorm-$PC2$ computer, select $\text{back}$ to switch to the back view of the computer. On the Shelf, expand Cables. Select a Cat5e $RJ45$ cable. In the Selected Component window, drag the connector to the $LAN$ port on the computer. In the Selected Component window, drag the other connector to a $LAN$ port on the router. Select a Cat5e $RJ45$ cable. In the Selected Component window, drag a connector to the $WAN$ port on the router. In the Selected Component window, drag the other connector to the port on the wall plate.

Provide power to the router as follows:

On the Shelf, select the power adapter. In the Selected Component window, drag the DC power connector to the power port on the router. In the Selected Component window, drag the AC adapter connector to the surge protector. Above the router, select Front to switch to the front view to verify power and network activity lights.

Request new $TCP/IP$ information from the router for Dorm-PC as follows:

On the $\text{Dorm-PC}$ monitor, select Click to view $\text{Windows 10}$.In the Search field on the taskbar, enter command prompt. Under Best Match, select Command Prompt. Enter $\text{ipconfig}$ /renew and press $\text{Enter}$ to request new $TCP/IP$ information from the router. In the notification area, right-click the Network icon and select Open Network and Sharing Center. The network information map should indicate an active connection to the Firewall Network and the internet.

Configure Windows Firewall on $\text{Dorm-PC}$ as follows:

In Network and Sharing, select Windows Firewall. From the left menu, select Turn Windows Firewall on or off. Under Private network settings, select Turn on Windows Firewall. Under Public network settings, select Turn on Windows Firewall. Click OK.

4 0
3 years ago
Other questions:
  • Why did LISD had to block the game “among us”?
    8·2 answers
  • True false you cannot fill in a callout​
    14·1 answer
  • Select the correct answer.
    12·2 answers
  • In an oligopolistic market, consumer choice is?
    12·2 answers
  • Which of the following are documents that can help you to review and assess your organization’s status and state of security? Fi
    6·1 answer
  • Who distributes IP Address?
    10·1 answer
  • How does a author develop a character in a story?
    14·2 answers
  • Give a recursive algorithm that takes as input a string s, removes the blank characters and reverses the string. For example, on
    7·1 answer
  • A ___________ is a variable used to pass information to a method.
    11·2 answers
  • How will technology help people with disabilities become more transportation independent?.
    5·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!