SophiaPretty

(5)

$14/per page/Negotiable

About SophiaPretty

Levels Tought:
Elementary,Middle School,High School,College,University,PHD

Expertise:
Accounting,Algebra See all
Accounting,Algebra,Applied Sciences,Architecture and Design,Art & Design,Biology,Business & Finance,Calculus,Chemistry,Communications,Computer Science,Economics,Engineering,English,Environmental science,Essay writing Hide all
Teaching Since: Jul 2017
Last Sign in: 313 Weeks Ago, 5 Days Ago
Questions Answered: 15833
Tutorials Posted: 15827

Education

  • MBA,PHD, Juris Doctor
    Strayer,Devery,Harvard University
    Mar-1995 - Mar-2002

Experience

  • Manager Planning
    WalMart
    Mar-2001 - Feb-2009

Category > Computer Science Posted 06 Jan 2018 My Price 10.00

greatest key less than k and the least key greater

Part 1: BST

Exercise 1.Prove that a binary tree having n  ≥ 1 real nodes has n + 1 external nodes. (Hint: use induction)

 

Exercise 2. for a key k that is not found in binary search tree T, prove that both the greatest key less than k and the least key greater than k lie on the path traced by the search for k.

 

Part 2: RBST

Exercise 3.Design and implement the permute(a) method that takes as  input an array, a, that contains n distinct values and randomly permutes a. The method should run in O(n) time and you should prove that each of the n! possible permutations of a is equally probable.

 

Part 3: Red-Blak and 2-4

Exercise 4.Illustrate the 2-4 tree that corresponds to the Red-Black Tree illustrated in the additional file of this assignment.

Exercise 5. Consider the set of keys K = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.

Draw a (2,4) tree storing K as its keys using the fewest number of nodes.

 

Exercise 6. Let T and U be (2,4) trees storing n and m entries, respectively, such that all the entries in T have keys less than the keys of all the entries in U. Describe an O(logn+logm)-time method for joining T and U into a single tree that stores all the entries in T and U.  (Hint:Find the right place to “splice” one tree into the other to maintain the (2,4) tree property)

 

Part 4. Heap

Exercise 7. A d-ary tree is a generalization of a binary tree in which each internal node has d children. Using Eytzinger’s method it is also possible to represent complete d-ary trees using arrays. Work out the equations that, given an index i, determine the index of i’s parent and each of i’s d children in this representation.

Exercise 8. Explain how the k largest elements from an unordered collection of size n can be

found in time O(nlogk) using O(k) auxiliary space. (hint: use an auxiliary heap of k elements)

______________________________________

The submission is through cuLearn in one zip file. The solution of each part must be included in a separate directory named “Part” followed by the exercise number.  Thus, the directories names are: Part1, Part2, Part3 and Part4. The submitted files formats should be limited to  java files and/or  pdf files. The name of your zip file must be  a concatenation of the student full name and Assign3-2402.zip (e.g. BrandonThomsonAssign3-2402.zip).

 

Attachments:

Answers

SophiaPretty
(5)
Status NEW Posted 06 Jan 2018 12:01 PM My Price 10.00

-----------  ----------- H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly

Not Rated(0)