Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Computer Engineering Expert

problem 1: Suppose we implement a priority queue as a heap. Assume the queue has thousands of elements. Suppose further that we have four different priorities (1-4, highest to lowest). The heap typically has 5% of priority 1 elements, 10% priority 2 elements, 15% priority 3 elements, and 70% of priority 4 elements. The probability of the newly arriving element at priority i, P(i)  is  P(1) = 0.05, P(2) = 0.10, P(3) = 0.15 and P(4) = 0.7.

a) Find the average complexity of an enqueue operation.
b) Find the average complexity of the dequeue (remove) operation.

problem 2: Let's analyze the Heap enqueue/dequeue operations with different assumptions. Imagine that the elements already in the queue were put into a sequence with the head element at the front at the lowest priority elements toward the end. Then assume that any new element to be enqueued is equally likely to be placed anywhere into that sequence. You can assume that the heap contains n = 2k-1 elements for simplicity.

a) Find the average complexity of an enqueue operation.
b) Find the average complexity of the dequeue (remove) operation.

problem 3
: We considered building a balanced (or full) BST from a sorted array. Assume that the array has n = 2k-1 elements in sorted order. We will insert the array middle element first (as the root), then insert the middle element of the left half, then the middle element of the right half, and so on recursively. Since the array has n elements, the actual work at each level is the insert into the BST. Define the model (using a summation ) for the total number of comparisons to insert all the elements into the BST.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M92983

Have any Question? 


Related Questions in Computer Engineering

Reorganize the bank account classes as follows in the bank

Reorganize the bank account classes as follows. In the Bank Account class, introduce an abstract method end Of Month with no implementation. Rename the add Interest and deduct Fees methods into end Of Month in the subcla ...

In distance-vector routing good news decrease in a link

In distance-vector routing, good news (decrease in a link metric) will propagate fast. In other words, if a link distance decreases, all nodes quickly learn about it and update their vectors. In Figure 20.33, we assume t ...

Assignment designing ferpa technical safeguardsimagine you

Assignment: Designing FERPA Technical Safeguards Imagine you are an Information Security consultant for a small college registrar's office consisting of the registrar and two assistant registrars, two student workers, an ...

This problem concerns a traffic light placed on a stretch

This problem concerns a traffic light placed on a stretch of road where there is no cross traffic, but where pedestrians often cross. There are two sets of lights, one facing each direction of traffic, and two pedestrian ...

1 in the game of life can you construct a glider gun of

1. In the Game of Life, can you construct a glider gun of glider emission period 15? Period 20? Save your configurations as buttons in the Life model in the NetLogo models library. 2. A methuselah is a small pattern that ...

The 2-d array described in chapter 2 is a simple

The 2-D array described in Chapter 2 is a simple rectangular structure consisting of the same number of elements in each row. Other layouts are possible and sometimes required by problems in computer science. For example ...

Select a new shape for the turtles from the shapes editor

Select a new shape for the turtles from the shapes editor, and then create a " cloud " of turtles (a bunch of turtles in the same local area) using your new shape. Create some green patches. Make the turtles follow the m ...

1 you know that the domain name of a computer is

1. You know that the domain name of a computer is "aBusiness.com". Write a statement in Java to create an InetAddress object associated with that computer. 2. You know that the IP address of a computer is "23.14.76.44". ...

1 find at least two new coin denominations that make the

1. Find at least two new coin denominations that make the greedy algorithm for coin changing shown in the chapter produce suboptimal results. 2. Using a "commercial" compression program, such as WinZip, compress a small ...

Matlabs fft command computes the dft of a vector x assuming

MATLAB's fft command computes the DFT of a vector x assuming that the first sample occurs at time n = 0. Given that X = fft(x) has already been computed, derive a method to correct X to reflect an arbitrary starting time ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro