Purchase Solution

Algorithm to determine the depth of a comparison network

Not what you're looking for?

Ask Custom Question

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.

Attachments
Purchase this Solution

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.

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 ...

Purchase this Solution


Free BrainMass Quizzes
Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

Basic Networking Questions

This quiz consists of some basic networking questions.