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

Research a company that has moved some of its operations

Research a company that has moved some of its operations overseas. Discuss how this has directly affected the American workforce.  Applying concepts you learned in the required readings, discuss who has benefited more fr ...

Consider the following case studymusicondemand is a new

Consider the following case study. MusicOnDemand is a new subscription-based service for on-demand Internet streaming audio media. There are three types of users for MusicOnDemand: 1. Standard users; 2. Premium users; 3. ...

1 determine the worst case time complexity for each method

1. Determine the worst case time complexity for each method of the Map ADT implemented in Section 3.2. 2. Modify the binary search algorithm to find the position of the first occurrence of a value that can occur multiple ...

1 if you could what would you do to help create a national

1. If you could, what would you do to help create a national "security culture" in which everyone is more knowledgeable and proactive about threats to information security? 2. There have been several incidents of data th ...

1 design and implement a function that reverses the order

1. Design and implement a function that reverses the order of the items in a queue. Your solution may only use the operations defined by the Queue ADT, but you are free to use other data structures if necessary 2. Implem ...

1 in chapter 1 we mentioned that the tcpip suite unlike the

1. In Chapter 1, we mentioned that the TCP/IP suite, unlike the OSI model, has no presentation layer. But an application-layer protocol can include some of the features defined in this layer if needed. Does HTTP have any ...

In this project you will enhance the bankaccount class and

In this project, you will enhance the BankAccount class and see how abstraction and encapsulation enable evolutionary changes to software. Begin with a simple enhancement: charging a fee for every deposit and withdrawal. ...

1 what do you get if you add -14 to itself 4 times what is

1. What do you get if you add -1/4 to itself 4 times? What is -1/4 × 4? Are they the same? What should they be? 2. Write down the bit pattern in the fraction of value 1/3 assuming a floating point format that uses binary ...

Mobile app part 3 riskreference the microsoft project file

Mobile App Part 3 Risk Reference the Microsoft Project file you created in Assignment 5(AT THE ATTACHED): Mobile App Part 2 (Gantt and PERT Charts) for the completion of this assignment. Write a two to three page paper i ...

A dual processor smp system includes an l1 data cache for

A dual processor SMP system includes an L1 data cache for each processor and employs the MESI protocol to maintain cache consistency.  Each cache is a 2-way set associative copy-back cache that contains a total of 8192 c ...

  • 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

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

Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen