Solved

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

Posted on 2014-03-23
10
344 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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
I have got the answer.
If anybody likes to hear it, I'll be more than happy.
0
Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

 
LVL 84

Expert Comment

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

Author Comment

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

Expert Comment

by:ozo
Comment Utility
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
Comment Utility
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
Comment Utility
Thanks again.
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

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…
Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
Sending a Secure fax is easy with eFax Corporate (http://www.enterprise.efax.com). First, Just open a new email message.  In the To field, type your recipient's fax number @efaxsend.com. You can even send a secure international fax — just include t…
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.

772 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

13 Experts available now in Live!

Get 1:1 Help Now