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

Write an application that retrieves a student name and

Write an application that retrieves a student name and three scores per line from a text file. Process the values by calculating the average of the scores per student. Write the name and average to a different text file. ...

1 igs need dc-ac ac-dc and ac-ac converters describe one

1. IGs need dc-ac, ac-dc, and ac-ac converters. Describe one application, relevant for IG-based energy system, for each of those power conversions. 2. Where are dc-dc converters used in IG systems?

1 your job is to cook 3 cakes as efficiently as possible

1. Your job is to cook 3 cakes as efficiently as possible. Assuming that you only have one oven large enough to hold one cake, one large bowl, one cake pan, and one mixer, come up with a schedule to make three cakes as q ...

Now calculate the relative performance of adders assume

Now calculate the relative performance of adders. Assume that hardware corresponding to any equation containing only OR or AND terms, such as the equations for pi and gi on page B-40, takes one time unit T. Equations tha ...

Assignmenttopic the effect of virtual achievements on

Assignment Topic :The Effect of Virtual Achievements on Student Engagement For this task, I need help in developing a narrative about my topic (above), and an outline of the collegiate dissertation process, to submit for ...

1 who is ultimately responsible for managing a technology

1. Who is ultimately responsible for managing a technology? Who is responsible for enforcing policy that affects the use of a technology? 2. What is contingency planning? How is it different from routine management plann ...

Calculate the total number of bits required for the cache

Calculate the total number of bits required for the cache listed above, assuming a 32-bit address. Given that total size, find the total size of the closest direct-mapped cache with 16-word blocks of equal size or greate ...

What roughly is the time complexity ofa vacuuming a carpet

What (roughly) is the time complexity of: a) Vacuuming a carpet if the size of the input to the operation is the number n of square feet of carpet? b) Finding a word in a (paper) dictionary if the size of the input is th ...

1 what are the types of password attacks what can a systems

1. What are the types of password attacks? What can a systems administrator do to protect against them? 2. What is the difference between a denial-of-service attack and a distributed denial-of-service attack? Which is mo ...

1 why is it important for organizations to have a business

1. Why is it important for organizations to have a business continuity plan in place? 2. Why is important for organizations to have a disaster recovery plan? 3. If companies have both a BCP and a DRP in place do they nee ...

  • 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