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

  Construct a magic square using a genetic algorithm

Construct a magic square using a genetic algorithm. First, generate an initial population of magic squares with random values. The fitness of each individual square is calculated based on the "flatness", that is, the degree of deviation in the sum..

  Discuss the business problem

Provide a clear statement of the aims and objectives of the data analytics study and the possible outcomes in terms of discovered knowledge and its potential application towards solution of the problem. In this section you need to discuss the busi..

  Design binary tree in ascii mode

Design the binary tree that the following allocations create. List the nodes in the order of their visit for an NLR scan.

  Description a long time ago in a galaxy far far away the

description a long time ago in a galaxy far far away the country mafghanistan had n cities and m old roads where each

  Analogue of max flow min cut theorem-capacitated network

Explain how to define the s-t cut on node capacitated network as opposed to edge capacitated network, and how would one illustrate that analogue of the max flow min cut theorem.

  Explain the three types of relationships

Provide an example of a one to one relationship and an example of a many-to-many relationship in a newspaper, magazine, book, or everyday situation you encounter.

  Discuss fault tolerance approaches that systems managers use

Discuss fault tolerance approaches that systems managers use to assure continuity of operations

  Give a recursive algorithm for finding the number of one''s

Give a recursive algorithm for finding the number of one's in a bit string, name the algorothm count-ones.

  What step in the proof fails if messages can be duplicated

Show that the relationship in Lemma 6. 19 also holds if mes­ sages can get lost in the channel pq, but not if messages can be duplicated. What step in the proof fails if messages can be duplicated?

  What is difference between a state graph and a search tree

Describe how the problem of traveling from one city to another could be framed as a production system. What are the states? What are the productions?

  Single binary search tree

You must store the words and the counts of the words in a single binary search tree and each word occurring in the text can only be stored once in the tree

  What is largest permissible magnitude of an integer constant

1 Typically, what is the largest permissible magnitude of an integer constant? State your answer in decimal, octal and hexadecimal.

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