Representation of sets?, Data Structure & Algorithms

A set s is conveniently shown in a computer store by its characteristic function C(s). This is an array of logical numbers whose ith element has the meaning "i is present in s". As , the group of lower integers  s = {2, 3, 5, 7, 11, 13}  is presented by the linear of  bits, by a bitstring:

C(s) = (... 0010100010101100)

The presentation of sets by their characteristic function has the advantage that the operations of computing the intersection, union, and difference of two sets may be implemented as elementary logical operations. The following equivalences, which hold for all components of the base type of the sets y and x, relate logical functions with operations on sets:

i IN (x+y) =  (i IN x) OR (i IN y)

i IN (x*y) =  (i IN x) & (i IN y)

i IN (x-y) =  (i IN x) & ~(i IN y)

These logical operations are available on all digital machine, and moreover they operate concurrently on all corresponding components of a word. It therefore seems that in order to be able to implement the basic set functions in a simpler manner, sets must be represented in a lower, fixed number of words upon which not only the basic logical functions, but also those of shifting are available. Testing for membership is then started by a single shift and a subsequent (sign) bit test operation. As a result, a test of the form  x IN {c1, c2, ... , cn}  can be stated considerably more efficiently than the similar Boolean expression

(x = c1) OR (x = c2) OR ... OR (x = cn)

A corollary is that the set structure could be used only for small integers as components, the largest one being the wordlength of the relying computer.

 

 

Posted Date: 7/27/2012 6:22:54 AM | Location : United States







Related Discussions:- Representation of sets?, Assignment Help, Ask Question on Representation of sets?, Get Answer, Expert's Help, Representation of sets? Discussions

Write discussion on Representation of sets?
Your posts are moderated
Related Questions
what is the difference between data type and abstract data type

Explain about greedy technique The  greedy  method  suggests  constructing  a   solution  to  an  optimization  problem   by  a sequence of steps, every expanding a partially c

b) The user will roll two (six-sided) dices and the user will lose the game if (s)he gets a value 1 on either any of the two dices & wins otherwise. Display a message to the user w

Q. What is the need of using asymptotic notation in the study of algorithm? Describe the commonly used asymptotic notations and also give their significance.

Q. Enumerate number of operations possible on ordered lists and arrays.  Write procedures to insert and delete an element in to array.

Which of the sorting algorithm is stable   Heap sorting is stable.

Find a minimum cost spanning arborescence rooted at r for the digraph shown below, using the final algorithm shown in class. Please show your work, and also give a final diagram wh

Ruby implementation of the Symbol ADT Ruby implementation of the Symbol ADT, as mentioned, hinges on making Symbol class instances immutable that corresponds to the relative la

System defined data types:- These are data types that have been defined by the compiler of any program. The C language contains 4 basic data types:- Int, float,  char and doubl

In the amortized analysis, the time needed to perform a set of operations is the average of all operations performed. Amortized analysis considers as a long sequence of operations