[Show all top banners]

atro
Replies to this thread:

More by atro
What people are reading
Subscribers
:: Subscribe
Back to: Kurakani General Refresh page to view new replies
 Algorithm help
[VIEWED 4896 TIMES]
SAVE! for ease of future access.
Posted on 02-19-09 11:21 PM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

Hey guys need help from you. I've seen people get help here. I am a web developer/graphic designer but I have to take this class its a requirement and i am not much of a programmer. If you give me a good pseudo code it will be fine. I understand the concept but i cannot write from the scratch. If you are going to use language then you can use C. I hope i get some help. And please dont flame this thread. Thanks.

When the collection of data is large, a large number of comparisons may

still be needed to do a binary search. For example, a telephone directory of a large city

could easily take about 25 comparisons per search. To improve this, multiway searching

uses a general tree, which is a tree data structure that can have more than two children.

In multiway searching, we store a few keys in each tree node, and the children represent

the subtrees containing (a) the entries smaller than all the keys, (b) the entries larger

than the first key but smaller than the rest (c) the entries larger than the first two keys

but smaller than the rest, and so on. The figure below shows an example of a general

tree that can be used for multiway searching. In the root of this tree we have the keys of

6 and 10, so if we are looking for a key less than 6, we would take the left branch. If we

are looking for a key between 6 and 10, we would take the middle branch, and for a key

larger than 10, we would take the right branch.

Write an algorithm to do a multiway search. For your answer you can assume that

each node has two arrays called Keys[3] and Links[4] and that you have a function

called Compare(keyList, searchKey) that returns a positive integer indicating the key that

matches or a negative integer indicating the link to take. (For example, Compare([2,6,10],

6) would return a value of 2 because the second key matches, and Compare([2,6,10], 7)

would return a value of −3 because 7 would be found on the third link associated with the

gap between the second and third key values.) When you have finished your algorithm,

do a wort-case and an average-case analysis, assuming that the tree is complete and each

internal node has four children. (You might want to draw a sample tree.) What would

be the impact on your two analyses if the tree was not complete or if some internal nodes

had fewer than four children?



 
Posted on 02-20-09 10:23 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 
 
Posted on 02-20-09 11:10 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

Not sure if this is correct


Multiwaysearch(keyList,start,end,searchKey)

//keylist        the list of keys
//start           the index of the first value to consider
//end            the index of the last value to consider
//searchKey the element of list we want

if start<end then
   result= compare(keyList,searchKey)
   if result > 0 then
      return result
   else
   
     if result < 0 then
        return Multiwaysearch(keyList, links[abs(result)],end,searchKey)
    end if
end if
      

 
Posted on 02-20-09 11:12 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

Thank you so much tech guy, you are great.

I will keep this thread alive to see more answers.

Thanks TechGuy and thanks Sajha community.

 
Posted on 02-20-09 11:37 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

you know what
if result < 0 then
        return Multiwaysearch(keyList, links[abs(result)],end,searchKey)
    end if
end if


should be

Multiwaysearch(keyList,searchKey)
.
.
.
.


if result < 0 then
        return Multiwaysearch( links[abs(result)],searchKey)
    end if
end if

no need for start and end 
but this will cause and infinite recursion if NO MATCH...

lets see if someone has taken Algorithm Analysis class.


 
Posted on 02-20-09 11:41 AM     Reply [Subscribe]
Login in to Rate this Post:     0       ?    
 

Not sure if you are looking for binary search. Looks like it is binary search though
Here is the function for binary search

int Multiwaysearch(keyList,start,end,searchKey)
{
    int k = 0;
   while( start <= end)
       {
               k = ( start + end)/2;
              if (searchKey = = keyList[k])
                  return k; // returns this position if  searchKey is found in keyList
              if (searchKey < keyList[k])
                   end = k -1;
              else
                  start = k+1;
        }
      return -1; // returns -1 indicating that no match was found
      return ( -k) // this might return the position the number would be found if the number is not in the  keyList.
}

 You don't have to use compare function here, but if you need to you could now modify anyway.
Hope this helps


 


Please Log in! to be able to reply! If you don't have a login, please register here.

YOU CAN ALSO



IN ORDER TO POST!




Within last 60 days
Recommended Popular Threads Controvertial Threads
TPS Re-registration case still pending ..
Toilet paper or water?
ढ्याउ गर्दा दसैँको खसी गनाउच
Tourist Visa - Seeking Suggestions and Guidance
I hope all the fake Nepali refugee get deported
and it begins - on Day 1 Trump will begin operations to deport millions of undocumented immigrants
From Trump “I will revoke TPS, and deport them back to their country.”
Travel Document for TPS (approved)
wanna be ruled by stupid or an Idiot ?
To Sajha admin
Those who are in TPS, what’s your backup plan?
MAGA denaturalization proposal!!
How to Retrieve a Copy of Domestic Violence Complaint???
advanced parole
MAGA and all how do you feel about Trumps cabinet pick?
All the Qatar ailines from Nepal canceled to USA
MAGA मार्का कुरा पढेर दिमाग नखपाउनुस !
NOTE: The opinions here represent the opinions of the individual posters, and not of Sajha.com. It is not possible for sajha.com to monitor all the postings, since sajha.com merely seeks to provide a cyber location for discussing ideas and concerns related to Nepal and the Nepalis. Please send an email to admin@sajha.com using a valid email address if you want any posting to be considered for deletion. Your request will be handled on a one to one basis. Sajha.com is a service please don't abuse it. - Thanks.

Sajha.com Privacy Policy

Like us in Facebook!

↑ Back to Top
free counters