Representation of sets?, Data Structure & Algorithms

Assignment Help:

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.

 

 


Related Discussions:- Representation of sets?

Explain the term heuristics searching, (a) Discuss the role played by Busin...

(a) Discuss the role played by Business Intelligence Systems in giving companies strategic advantage. (b) Explain the term heuristics searching . (c) With the use of an appr

Splaying procedure, For splaying, three trees are maintained, the central, ...

For splaying, three trees are maintained, the central, left & right sub trees. At first, the central subtree is the complete tree and left and right subtrees are empty. The target

Array-based representation of a binary tree, Assume a complete binary tree ...

Assume a complete binary tree T with n nodes where each node has an item (value). Label the nodes of the complete binary tree T from top to bottom & from left to right 0, 1, ..., n

Different ways for representing s graph, W h at are the different ways by...

W h at are the different ways by which we can represent graph?  Represent the graph drawn below using those ways.     T he d iff e r e nt w a y s by

space, What is Space complexity of an algorithm? Explain

What is Space complexity of an algorithm? Explain.

Convert graph into tree, How can we convert a graph into a tree ? Do we hav...

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?

Memory allocation strategies, Q. Explain the various memory allocation stra...

Q. Explain the various memory allocation strategies.                                                            Ans. M e m ory Allocation Strategies are given as follow

What is efficiency of algorithm, What is Efficiency of algorithm? Effic...

What is Efficiency of algorithm? Efficiency of an algorithm can be precisely explained and investigated with mathematical rigor.  There are two types of algorithm efficiency

Undirected graph, Graphs are data structures which consist of a set of vert...

Graphs are data structures which consist of a set of vertices & a set of edges which connect the vertices. A graph where the edges are directed is called directed graph. Or else, i

Applications of binary trees, In computer programming, Trees are utilized ...

In computer programming, Trees are utilized enormously. These can be utilized for developing database search times (binary search trees, AVL trees, 2-3 trees, red-black trees), Gam

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd