Evaluate the average complexity of an enqueue operation

Assignment Help Data Structure & Algorithms
Reference no: EM135008

Question 1: Consider we implement a priority queue as a heap. Suppose the queue has thousands of elements. Consider 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 recently 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) Evaluate the average complexity of an enqueue operation.

b) Determine the average complexity of the dequeue (remove) operation.

Question 2: Let's analyze the Heap dequeue/enqueue operations with different assumptions. Suppose 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 consider that any new element to be enqueued is equally likely to be placed anywhere into that sequence. You can suppose that the heap contains n = 2k-1 elements for simplicity.

a) Evaluate the average complexity of an enqueue operation.

b) Determine the average complexity of the dequeue (remove) operation.

Question 3: We considered building a balanced (or full) BST from a sorted array. Suppose 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 for the total number of comparisons to insert all the elements into the BST.

Reference no: EM135008

Questions Cloud

Discuss technology as a mixed blessing in health care : All of this technology has not resulted in better clinical outcomes and better overall health of the population. Why is this the case? Discuss technology as a mixed blessing in American health care
Polymer diffusion-calibration of an optical tweezer : Modeling the optical trap as a Hookean spring, evaluate the trap stiffness using the Boltzmann distribution. Determine the sphere diameter by comparing the Stokes drag and the tweezer force that balances the drag.
What do you consider to be important challenges : Looking to the future, there are many challenges facing American health care providers. What do you consider to be important challenges
Benefits of aligning hrm activities : Find an article(s) through ProQuest which discusses the benefits of aligning HRM activities with key business initiatives and discuss the challenges and the opportunities of doing so
Evaluate the average complexity of an enqueue operation : Evaluate the average complexity of an enqueue operation. Determine the average complexity of the dequeue (remove) operation.
Hrm approach to recruitment and selection in organisation : Produce poster advertising and highlighting the essential's HRM approach to recruitment and selection in the organisation. This is to be undertaken individually.
What is the kendall notation for this system : Customer arrival rate as well as service time follows the Poisson and exponential distributions respectively. What is the Kendall notation for this system
Prepare the business income statement for the period : Prepare the business Income Statement for the period. Prepare the Statement of Changes in Equity for the period. Prepare the classified Balance Sheet at the end of the period.
What benefits of conducting performance discussions : What benefits will he or the organization realize from him investing his time to improve his skill at conducting performance discussions

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  Write the selection sort algorithm

Write the selection sort algorithm

  Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd