?
Solved

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

Posted on 2014-03-23
10
Medium Priority
?
397 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 900 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 85

Assisted Solution

by:ozo
ozo earned 600 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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
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
 
LVL 85

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 85

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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

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 …
This article provides a brief introduction to tissue engineering, the process by which organs can be grown artificially. It covers the problems with organ transplants, the tissue engineering process, and the current successes and problems of the tec…
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
Suggested Courses

850 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