Implement the dynamic-set operation insert

Assignment Help Data Structure & Algorithms
Reference no: EM131097317

Question 1:

Can you implement the dynamic-set operation INSERT on a singly linked list in O(1) time? How about DELETE?

Question 2:

Suppose we have stored n keys in a hash table of size m, with collisions resolved by chaining, and that we know the length of each chain, including the length L of the longest chain. Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time O(L . (1 + 1/α)).

Question 3:

Give a nonrecursive algorithm that performs an inorder tree walk. (Hint: An easy solution uses a stack as an auxiliary data structure. A more complicated, but elegant, solution uses no stack but assumes that we can test two pointers for equality.)

Question 4:

Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.

Question 5:

Give a recursive version of the TREE-INSERT procedure.

Question 6:

Why don't we allow a minimum degree of t = 1?

Question 7:

As a function of the minimum degree 1, what is the maximum number of keys that can be stored in a B-tree of height h?

Question 8:

Explain how to find the minimum key stored in a B-tree and how to find the prede-cessor of a given key stored in a B-tree.

Below is the TREE-DELETE procedure

TREE-DELETE(T, Z)

1 if z.left == NIL

2       TRANSPLANT(T, z, z. right)

3 elseif z.right == NIL

4       TRANSPLANT(T, z, z. left)

5 else y = TREE-MINIMUM (z. right)

6       if y.p ≠ z

7       TRANSPLANT(T, y, y. right)

8       y.right = z.right

9       y.right.p = y

10     TRANSPLANT(T, z, y)

11     y.left = z.left

12     y. left. p = y

Exercise A1

Follow the TREE-DELETE procedure described in Chapter 12, show step-by-step output of each of the following operations applied on the binary search tree below.

2292_figure2.jpg

a) Delete node 3.

b) Based on output from step a), delete node 7.

c) Based on output from step b), delete node 18.

Note: Strictly speaking, node i in the question should be interpreted as "a node that is represented by its key value of i".

B-TREE-INSERT (T, k)
1 r = T. root
2 if r.n==2t - 1
3 s = ALLOCATE-NODE 0
4 T. mot = s
5 s.leaf = FALSE
6 s.n = 0
7 s.c, = r
8 B-TREE-SPLIT-CHILD(S, 1)
9 B-TREE-INSERT-NoNFuLL(s,k)
10 else B-TREE-INSERT-NONFULL (r, k)

Exercise A2

Follow the B-TREE-INSERT procedure described in Chapter 18, show step-by-step output of each of the following operations applied on the B-tree below. Note that the B-tee has a minimum degree r=3 and the values inside each node show the key values stored in that node.

246_figure1.jpg

a) Insert key 13.

b) Based on output from step a), insert key 37.

c) Based on output from step b), insert key 34.

d) Based on output from step c), insert key 45.

Verified Expert

The work is done on explaining the algorithm of every question and the reasoning for different questions which are for the inorder, preorder traversal. The work is done in MS word.

Reference no: EM131097317

Questions Cloud

Present worth of the machine is closest : A certain machine will cost $50,000 to purchase, will have a six-year life, and $5,000 salvage value. It will be updated in year 4 at a cost of $15,000. Its annual operating cost is expected to be $30,000 per year. At an inflation rate of 5% per year..
Assume there are two players in an oligopoly : Assume there are two players in an oligopoly, playing repeated Cournot competition (that is, they compete on quantity). The demand in each year is p= A-by. Each player has discount rate r. Find strategies that lead to a sub-game perfect equilibrium w..
What happens to total market supply as n goes to infinity : Demand is linear: p= A-by; cost is cy (marginal cost is c). What is oligopoly price and quantity when there are players? What happens to the total market supply as n goes to infinity?
A commission - personal and professional goals : Here are two collectives subject I need to work on and I need this for an application packs for officer program in the NAVY 1-all applicants, including Nurse Corps, use the space provided to describe the following in detail (Limit your statement f..
Implement the dynamic-set operation insert : Can you implement the dynamic-set operation INSERT on a singly linked list in O(1) time? How about DELETE - what is the maximum number of keys that can be stored in a B-tree of height h?
Policy make difference in the market : Assume the government now imposes a (binding) maximum legal price for physician office visits (i.e. a price ceiling on the physician office visits). Under what condition would such a policy make a difference in the market (i.e. cause a market distort..
What may be your stereotypes explain fully : We studied stereotypes which may be either positive or negative and, furthermore, may be accurate or unfounded in reality based on the individual or the culture or group. What are your observations, beliefs and what may be your stereotypes? Explai..
What is the sound power incident on the eardrum : What is the sound power (energy per second) incident on the eardrum at the threshold for pain?
Macroeconomic variables is affected : Draw a fully labeled figure of the FE line, the LM curve and the IS curve. Label the point where all three curves intersect E. Show in the figure how the curves move in response to a positive supply shock (i.e. an increase in A). Then answer how each..

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  What are the different types of query optimization algorithm

Describe three data fragmentation strategies. Give some examples of each.

  Performance of two distinct sorting algorithms

This lab assignment requires you to compare the performance of two distinct sorting algorithms to obtain some appreciation for the parameters to be considered in selecting an appropriate sort.

  Polytime algorithm to determine whether this is possible

Give a poly(n, 2^k)-time algorithm to determine whether this is possible, and if so, which steps you should take in order to achieve this. Note that an n O(k) algorithm is trivial

  Write an algorithm and draw a flow chart diagram

Write an algorithm and draw a flow chart diagram to produce the sum and average of first n odd natural numbers. For example, the sum of first 5 odd natural numbers, 1+3+5+7+9 = 25, so their average is 25/5 = 5

  Difference between a problem and an opportunity

What was the problems and/or opportunities facing Delta in late 1997? What is the difference between a problem and an opportunity

  Huffmancodes

You will turn in one file: HuffmanCodes.java, which can encode and decode files using Huffman codes. The program has the following command-line interface:

  Develop an algorithm that will work with any combination

Given the above scenario, develop an algorithm (final design presented as a flow chart) that will work with any combination of items. Your algorithm shou4 generate some form of packing instructions for staff to follow, which should include at leas..

  Evaluate algebraic expression by code with three-operand

Evaluate a short algebraic expression using code with three-operand instructions. The expression should have a minimum of three operands and 2 operators.

  Prove correctness of the given algorithm

Prove correctness of the following algorithm which is used to determine if a list numbers is a part of other list of numbers. For example for inputs List1=[1,2,3] and List2=[5,6,1,7,2,5,6,3], the algorithm will return "List1 is part of List2" and ..

  Recurrence-worst case running time-recursive binary search

Provide a recurrence for worst case running time of recursive Binary Search function in terms of n, the size of the search array. Solve the recurrence.

  What is the minimum number of attendants

A nursing home employs attendants who are needed around the clock. Each attendant is paid the same, regardless of when his or her shift begins. Each shift is 8 consecutive hours.

  Microsoft project file work breakdown structure

Update the Microsoft Project file you created in Assignment 1: VoIP Part 2 (Work Breakdown Structure) with the following changes

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