Solved

I'm facing a question with comparison networks. Find second and third min.

Posted on 2014-03-23
10
349 Views
Last Modified: 2014-03-24
I'm asked to
a. prove that depth of a comparison network that will find values of seond and third minimum is Omega(lg n).  
b. build such a network.

I need a hand here.

http://en.wikipedia.org/wiki/File:Six-wire-bubble-sorting-network.svg
0
Comment
Question by:aboo_s
  • 6
  • 3
10 Comments
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 300 total points
ID: 39949332
Could you do it for the first minimum?
Do that and then remember that Omega(3 lg n) = Omega(lg n)
0
 
LVL 10

Author Comment

by:aboo_s
ID: 39949460
And why is finding the first minimum is Omega(n) in network depth?
You need only n/2 comparators for that.
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 200 total points
ID: 39949464
Omega(n) = Omega(n/2) but the depth of a comparison network for the first minimum is Omega(lg n)
0
 
LVL 10

Author Comment

by:aboo_s
ID: 39949613
ozo:
I know that the depth is Omega(lg n), I'm asked to prove that. And build such a network.
0
 
LVL 10

Author Comment

by:aboo_s
ID: 39949616
I have got the answer.
If anybody likes to hear it, I'll be more than happy.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 84

Expert Comment

by:ozo
ID: 39949626
Can you find an Omega(lg n) depth network for the first minimum?
0
 
LVL 10

Author Comment

by:aboo_s
ID: 39949645
Yes, that's what I have found.  Attached is an example for N=8.
first-min.jpg
0
 
LVL 84

Expert Comment

by:ozo
ID: 39949655
And does TommySzalapski's hint suggest a way to modify that yo find the second and third minimum?
0
 
LVL 10

Author Comment

by:aboo_s
ID: 39949659
No, he only pointed out that if you can do it for the first it's no problem to do the second and third. But that wasn't what I asked. I asked to do it for the minimum in the first place.

Anyway, thank you all for your time, points will be split.
0
 
LVL 10

Author Closing Comment

by:aboo_s
ID: 39949660
Thanks again.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Roulette strategy probability question 58 90
Linear algebra 3 62
Energy conservation - Edward Leedskalnin 20 94
Calculating Z-SCORE inside Excel. 4 86
Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
This Micro Tutorial hows how you can integrate  Mac OSX to a Windows Active Directory Domain. Apple has made it easy to allow users to bind their macs to a windows domain with relative ease. The following video show how to bind OSX Mavericks to …
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.

910 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now