Explore BrainMass

Algorithm to determine the depth of a comparison network

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

Mr. Johnson draws an n-input comparison network with m comparators according to the following conventions.

The lines of the network go left-to-right, and comparators are drawn vertically to connect two lines. The network is drawn on an underlying grid, so that each comparator occupies one of at most m columns. Comparators can share columns, but they do not overlap.

Mr. Johnson represents a given drawing as a list L of triples, in which each triple (x, y, c) represents a comparator connecting line x to line y in column c.

Describe an efficient algorithm to determine the depth of a comparison network, where the input is Mr. Johnson's representation of a drawing of the network. Analyze your algorithm in terms of m and n.

Please look at the attachment for an example of his drawing and representation of a 4-input sorting network.

© BrainMass Inc. brainmass.com October 24, 2018, 8:47 pm ad1c9bdddf


Solution Preview

Let us first list out observations that are key to developing an efficient algorithm to determine the depth of a comparison network.

As each comparator can go in separate column, maximum number of columns possible in the given comparison network = m

Since comparators in a column operate in parallel, it allows us to process them in any order in that column, as far as our algorithm is concerned.

Given that -
- number of input lines = n
- number of comparators = m
- (x,y,c) represents a comparator connecting line x to line y in column c.
- L = list of comparators, representing the sorting network.

Since nothing is specified about the order of comparators in L, and given example also lists them in arbitrary order, this solution considers that L is simply specifying a collection of comparators that needs to be organised in certain order before computing the depth of network.

If contents of L is ...

Solution Summary

Solution describes an O(max{m,n}) algorithm to determine the depth of an n-input comparison network with m comparators, with pseudocode interspersed with detailed explanations and performance analysis of steps in algorithm.

See Also This Related BrainMass Solution

Solve LAN scenario

Include the following:

I. The physical extent of the LAN (number of buildings).The number of users.
1. Dental office is in on building. There are:
1 Receptionist
1 Scheduler
1 Billing Clerk
1 Senior Accounting Staff
3 Dental Hygienists
2 Full-time Dentist
2 Dental Assistants
The office has 4 separate rooms, each one with its own set up of dental equipment and 1 X-ray room

II. The number of nodes and workstation types (i.e., Pentium, etc.).
Specifics type and explain (Dell Pentium)

III. The number of servers.
Specifics and explain (Dell Printer server, File, Web)

IV. The applications (i.e., e-mail, Windows, MS Office, etc.).
Specifics and explain

V. The architecture (i.e., client/server, peer-to-peer, mainframe, segmented, etc.).
Specifics and explain

VI. The topology (i.e., bus, ring, star, etc.).
Specifics and explain

VII. The media (i.e., UTP, STP, Coaxial cable, Fiber, etc.).
Specifics and explain (UTP)

VIII. The connections (i.e., Hubs, repeaters, bridges, gateways, etc.).
Specifics and explain

IX. The NOS (i.e., Novell, Windows NT, UNIX, etc.).
Specifics and explain (Windows NT)

X. The LAN Management (i.e., administrator, help desk, etc.).

View Full Posting Details