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
Given are the definitions of some important terms: 1) Field: This is an elementary data item characterized by its size, length and type. For instance, Name

Q. Sort the sequence written below of keys using merge sort. 66, 77, 11, 88, 99, 22, 33, 44, 55                                                                      Ans:

B i n a ry Search Algorithm is given as follows 1. if (low > high) 2.     return (-1) 3. mid = (low +high)/2; 4. if ( X = = a [mid]) 5.      return (mid); 6.

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

Ask question #sdgsdgsdginimum 100 words accepted#

The time needed to delete a node x from a doubly linked list having n nodes is O (1)

Data records are stored in some particular sequence e.g., order of arrival value of key field etc. Records of sequential file cannot be randomly accessed i.e., to access the n th

Simulation is the process of making an abstract model of a real world situation in order to be aware of the effect of modifications and alterations and the effect of introducing nu

REPRESENTATION OF ARRAYS This is not uncommon to determine a large number of programs which procedure the elements of an array in sequence. However, does it mean that the eleme

Define the term array. An array is a way to reference a series of memory locations using the same name. Each memory location is represented by an array element. An  array eleme