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

Ask an Expert

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

Write your message here..

Related Questions

Find the adjacency matrix, Consider the digraph G with three vertices P1,P2... Consider the digraph G with three vertices P1,P2 and P3 and four directed edges, one each from P1 to P2, P1 to P3, P2 to P3 and P3 to P1. a. Sketch the digraph. b. Find the a

Program on radix sort., Write a program that uses the radix sort to sort 10... Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

Breadth-first search, Breadth-first search starts at a given vertex h, whic... Breadth-first search starts at a given vertex h, which is at level 0. In the first stage, we go to all the vertices that are at the distance of one edge away. When we go there, we

Algorithm to sort a given list by quick sort method, Q. Write down an algor... Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

Enumerate about the carrier set members, Enumerate about the carrier set me... Enumerate about the carrier set members Ruby is written in C, so carrier set members (which is, individual symbols) are implemented as fixed-size arrays of characters (which is

Computational complexity, Generally, Computational complexity of algorithms... Generally, Computational complexity of algorithms are referred to through space complexity (space needed for running program) and time complexity (time needed for running the progr

Column major representation, Column Major Representation In memory th... Column Major Representation In memory the second method of representing two-dimensional array is the column major representation. Under this illustration, the first column of

Algorithm that counts number of nodes in a linked list, Q. Write an algorit... Q. Write an algorithm that counts number of nodes in a linked list.                                       A n s . Algo rithm to Count No. of Nodes in Linked List C

Doubly linklist, explanation of doubly linklist explanation of doubly linklist

The # of times an algorithm executes, for(int i = 0; i for (int j = n -... for(int i = 0; i for (int j = n - 1; j >= i ; j--){ System.out.println(i+ " " + j);