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
Tree is dynamic data structures. Trees can expand & contract as the program executes and are implemented via pointers. A tree deallocates memory whereas an element is deleted.

1.  Using the traditional method of CPM: a.  What activities are on the critical path? b.  What is the expected total lead time of the project? 2.  Using CCPM: a.  What

Q. Explain the Hash Tables, Hash function and Hashing Techniques properly?             A n s . H as h Table is explained as follows : A hash table is a data struc

We have discussed already about three tree traversal methods in the earlier section on general tree. The similar three different ways to do the traversal -inorder , preorder, and p

Example which cause problems for some hidden-surface algorithms Some special cases, which cause problems for some hidden-surface algorithms, are penetrating faces and cyclic ov

/* the program accepts two polynomials as a input & prints the resultant polynomial because of the addition of input polynomials*/ #include void main() { int poly1[6][


The structures of files vary from operating system to operating system. In this unit, we will discuss the fundamentals of file structures with the generic file organisations. A

1. Define the following terms in a rule-based expert system? a) Knowledge base b) Inference engine 2. What is a fuzzy rule? Explain the difference between classical and fuzzy

1.  You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.  2.  You