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?

Algorithm, give me algorithm of simple interest

give me algorithm of simple interest

Which sorting methods sorting a list which is almost sorted, Which sorting ...

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

Cohen sutherland algorithm, Using the cohen sutherland. Algorithm. Find the...

Using the cohen sutherland. Algorithm. Find the visible portion of the line P(40,80) Q(120,30) inside the window is defined as ABCD A(20,20),B(60,20),C(60,40)and D(20,40)

Algorithms, write short note on algorithms

write short note on algorithms

Explain the halting problem, Explain the halting problem Given a comput...

Explain the halting problem Given a computer program and an input to it, verify whether the program will halt on that input or continue working indefinitely on it.

Determine the effect of ruby in implementation of string, Determine the eff...

Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact

Time complexity of merge sort and heap sort algorithms, What is the time co...

What is the time complexity of Merge sort and Heap sort algorithms? Time complexity of merge sort is O(N log2 N) Time complexity of heap sort is   O(nlog2n)

Complexity of an algorithm, An algorithm is a sequence of steps to solve a ...

An algorithm is a sequence of steps to solve a problem; there may be more than one algorithm to solve a problem. The choice of a particular algorithm depends upon following cons

space, What is Space complexity of an algorithm? Explain

What is Space complexity of an algorithm? Explain.

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