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

Sum it upnbspplease respond to the followingwrite a speech

" Sum It Up "  Please respond to the following: Write a speech that you would give to a friend in an elevator summing up the contents of this course. You have 30 to 90 seconds to inform your friend of the most important ...

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 ...

Create a project for a census bureau to obtain and analyze

Create a project for a census bureau to obtain and analyze household income survey data within the Cincinnati area (including Northern Ky). Data Collected: • Home identification code (4 alphanumeric characters) - require ...

1 both acls and c-list entries use owners users rather than

1: Both ACLs and C-List entries use "owners" (users) rather than individual processes. Why? 2: Alice can read and write to the file x, can read the file y, and can execute the file z. Bob can read x, can read and write t ...

This chapter covered network management whereas the

This chapter covered network management, whereas the previous chapter covered network security. Note that network design tasks are often interwoven, however, and shouldn't be considered discrete just because a book is di ...

Your task is to design a general program for managing board

Your task is to design a general program for managing board games with two players. Your program should be flexible enough to handle games such as tic-tac-toe, chess, or the Game of Nim of Project 6.2. Design an interfac ...

1 given a binary tree of size 76 what is the minimum number

1. Given a binary tree of size 76, what is the minimum number of levels it can contain? What is the maximum number of levels? 2. Draw all possible binary trees that contain 12 nodes.

In a survey of couples in the us city of san francisco

In a survey of couples in the US city of San Francisco, Catania et al. [65] recorded, among other things, the ethnicity of their interviewees and calculated the fraction of couples whose members were from each possible p ...

Compose a safety policy statement for your current

Compose a safety policy statement for your current organization (or an organization for which you previously worked), following the guidelines in the course textbook. Be certain it is specific to the organization and not ...

In a typical vector adt the size of the underlying array

In a typical Vector ADT, the size of the underlying array decreases after a sufficient number of items have been removed. Devise a strategy for decreasing the size of the array as items are removed. Modify your implement ...

  • 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