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
Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

Q. Describe the term array.  How do we represent two-dimensional arrays in memory?  Explain how we calculate the address of an element in a two dimensional array.

Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

Define the External Path Length The External Path Length E of an extended binary tree is explained as the sum of the lengths of the paths - taken over all external nodes- from

insertion and deletion in a tree

What is the best case complexity of quick sort In the best case complexity, the pivot is in the middle.

calculate gpa using an algorithm

A graph with n vertices will absolutely have a parallel edge or self loop if the total number of edges is greater than n-1

write a algorithsm in c to perform push and pop operations stastic implementation using array ?

Example: Insertion of a key 33 into a B-Tree (w/split) Step 1: Search first node for key closet to 33. Key 30 was determined. Step 2: Node pointed through key 30, is se