Show how to compute prefix sum in constant time using pram

Assignment Help Data Structure & Algorithms

Reference no: EM13996937

1. Given a sequence of numbers {a1, a2, ... , an}, show how to compute the prefix sum in constant time using PRAM. Which PRAM is used, how many processors are needed, and what is the cost of this algorithm?

2. Design an algorithm to distribute a copy of a sequence X = {x1, x2, ... , xk} that is stored in global memory to the local memory of each processor in O(log n) time, assuming you have an n-processor EREW PRAM and k =O(log n).

3. The suffix sum (or suffix maxima) was briefly discussed in class and is defined in our textbook by Akl. The prefix maxima can be computed by first reversing the sequence, then computing its prefix sum, and finally reversing the results of this computation. Provide a formal description of this PRAM algorithm and analyze its running time and cost. (Note: A formal description is illustrated by the one on slide 31 of our PRAM slide chapter.)

4. Show the simulation of CR by EREW PRAM. This is problem 30.2-8 in the Cormen, et. al. reference. NOTE: This is similar to the simulation of CW by EREW PRAM covered in slides. Recall that for a CW simulation, values must be carried from processors to memory. However, for the CR simulation, values must be carried from the selected memory cells back to the processors that are reading a memory cell value.

5. Give an O(lg n)-time EREW algorithm that determines for each object in an n-object list whether it is in the middle object. (Note: The middle object is defined to be the object in the |n/2|position.)

Reference no: EM13996937

Questions Cloud

How long does it take light incident perpendicular to glass : A 5.5 cm -thick layer of oil (n=1.46) is sandwiched between a 1.5 cm -thick sheet of glass. How long (in ns) does it take light incident perpendicular to the glass to pass through this 9.5 cm -thick sandwich?

What is the width of the central maximum on the screen : What is the width of the central maximum on the screen (in cm)? What is the distance from the center of the central maximum to the 3rd order minimum of the single slit pattern (in cm)?

What are its disadvantages relative to revenue sharing : Profit sharing is not widely practiced in the franchise business. What are its disadvantages relative to revenue sharing?

At what x-coordinate could you place a proton : At what x-coordinate could you place a proton so that it would experience no net force? Express your answer to two significant figures and include the appropriate units.

Show how to compute prefix sum in constant time using pram : Given a sequence of numbers {a1, a2, ... , an}, show how to compute the prefix sum in constant time using PRAM. Which PRAM is used, how many processors are needed, and what is the cost of this algorithm?

What are the costs and benefits of outsourcing : What are the costs and benefits of outsourcing? Can outsourcing be used to avoid tariffs and other trade restrictions? Provide 2 real-world examples of outsourcing by a firm(s) which competes globally. Need citations

Identify legal responsibilities of teachers : Use the GCU eLibrary to research information beyond what is provided in the course materials to explore the law and its application to special education issues covered in this course. Explore state departments of education Web sites to investigate..

How will people know that the screen is touch-sensitive : Sketch two (2) alternative interface designs for the ATM and indicate which alternative you prefer. The goal of this assignment is to exercise your user interface design abilities. Creativity in balancing usability with the constraints of the inte..

Define a sympathy strike : Provide a two paragraph summary of the case and Define a "sympathy strike?" How does it apply to this case study

User Account

All Pages