Write functions for computing union, intersection, and set difference on arbitrarily long bit vectors used to represent
Question:
Write functions for computing union, intersection, and set difference on arbitrarily long bit vectors used to represent set membership as described in Section 9.3. Assume that for each operation both vectors are of equal length.
Transcribed Image Text:
9.3 Bit Vectors for Representing Sets Determining whether a value is a member of a particular set is a special case of searching for keys in a sequence of records. Thus, any of the search methods discussed in this book can be used to check for set membership. However, we can also take advantage of the restricted circumstances imposed by this problem to develop another representation. In the case where the set elements fall within a limited key range, we can repre- sent the set using a bit array with a bit position allocated for each potential member. Those members actually in the set store a value of 1 in their corresponding bit; those members not in the set store a value of 0 in their corresponding bit. For example, consider the set of primes between 0 and 15. Figure 9.1 shows the corresponding bit table. To determine if a particular value is prime, we simply check the corre- sponding bit. This representation scheme is called a bit vector or a bitmap. The mark array used in several of the graph algorithms of Chapter 11 is an example of such a set representation. If the set fits within a single computer word, then set union, intersection, and difference can be performed by logical bitwise operations. The union of sets A and B is the bitwise OR function (whose symbol is | in Java). The intersection of sets A and B is the bitwise AND function (whose symbol is & in Java). For example, if we would like to compute the set of numbers between 0 and 15 that are both prime and odd numbers, we need only compute the expression 0011010100010100 & 0101010101010101.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 66% (3 reviews)
To implement the functions for computing union intersection and set difference on arbitrarily long bit vectors used to represent set membership well c...View the full answer
Answered By
Ehsan Mahmood
I’ve earned Masters Degree in Business Studies and specialized in Accounts & Finance. Couple with this, I have earned BS Sociology from renowned institute of Pakistan. Moreover, I have humongous teaching experience at Graduate and Post-graduate level to Business and humanities students along with more than 7 years of teaching experience to my foreign students Online. I’m also professional writer and write for numerous academic journals pertaining to educational institutes periodically.
4.90+
248+ Reviews
287+ Question Solved
Related Book For
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer
Question Posted:
Students also viewed these Computer science questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
As described in Section 5.7, virtual memory uses a page table to track the mapping of virtual addresses to physical addresses. This exercise shows how this table must be updated as addresses are...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
Figure shows an overhead view of a ring that can rotate about its center like a merry-go-round. Its outer radius R2 is 0.800 m, its inner radius R1 is R2/2.00, its mass M is 8.00 kg, and the mass of...
-
A heat engine has a solar collector receiving 600 Btu/h per square foot inside which a transfer media is heated to 800 R. The collected energy powers a heat engine which rejects heat at 100 F. If the...
-
The Princeville Company has debt covenants on its bank loan. During the 15-year term of the loan, Princeville must comply with these covenants: a. Current ratio must be 1.25 or higher. b. Debt ratio...
-
How has the London Stock Exchange kept its position as one of the leading markets?
-
1. Prepare a budget for this year for the Administrative Department at Tom's Toyota Company based on the following information: 2. Big Bob's Discount Appliances expects sales of $5,000, $5,000, and...
-
Esfandairi Enterprises is considering a new three - year expansion project that requires an initial fixed asset investment of $ 2 , 4 0 0 , 0 0 0 . The fixed asset will be depreciated straight - line...
-
Compute the probabilities for the following situations. These probabilities can be computed analytically, or you may write a computer program to generate the probabilities by simulation. (a) Out of a...
-
Write an algorithm to implement the transpose self-organizing list heuristic, assuming that the list is implemented using an array. In particular, write a function transpose that takes as input a...
-
A cold air chamber is proposed for quenching steel ball bearings of diameter D = 0.2 m and initial temperature T i = 400C. Air in the chamber is maintained at 15C by a refrigeration system, and the...
-
Discuss the concept of "securitization" in political discourse. How does framing political issues through a security lens affect policy decisions, civil liberties, and public perception?
-
The rest of the project shall include, but is not limited to: 1. Marco factors that may have long-term impacts on the whole industry, such as regulations; competition from other firms. You can find...
-
How does the theory of constructivism influence our understanding of international relations, and in what ways does it challenge traditional realist and liberal paradigms?
-
Background: SO MUCH CANDY DATA, SERIOUSLYCandy hierarchy data for 2017 Boing Boing Halloween candy hierarchy. This is survey data over the span of 4-years. The data is split into 4 separate files....
-
Consider the payoff matrix in Figure 2. What outcomes, if any, are Nash equilibria? a. There is one equilibrium: Firm 1 and Firm 2 both expand West. b. There is one equilibrium: Firm 1 and Firm 2...
-
Crunchem Cereal Company incurred the following actual costs during 20x4. Direct material used..................................................................$412,500 Direct...
-
In Exercises discuss the continuity of each function. f(x) -3 1 x - 4 y 3 2 -1 -2 -3+ 3 X
-
Give an example to show that the RTS/CTS in the 802.11 protocol is a little different than in the MACA protocol.
-
A wireless LAN with one AP has 10 client stations. Four stations have data rates of 6 Mbps, four stations have data rates of 18 Mbps, and the last two stations have data rates of 54 Mbps. What is the...
-
List two ways in which WiMAX is similar to 802.11, and two ways in which it is different from 802.11.
-
The receipt of payment for an account receivable: affects assets and equity affects assets and liabilities affects only the asset side of the accounting equation has no effect on the accounting...
-
Dan got a 1 0 year Fixed Rate Mortgage for $ 1 0 0 , 0 0 0 . The loan has constant annual payments and an annual interest rate of 5 % . There are no closing costs. Suppose Dan prepays the loan in...
-
1) Why could quantum computing be a very important tool in supply chain management (what can it do that traditional computing can't)? 2) Give 1 or 2 examples of some current issues in supply chain...
Study smarter with the SolutionInn App