Scribd
Upload
65 views2 pages

Important Questions

The document outlines important questions related to parallel algorithms, covering various models such as PRAM, Fully Connected, and Pyramid models. It includes topics like parallel summation, matrix transposition, searching algorithms, and the design of parallel versions of sorting and graph algorithms. Each question prompts discussion or development of algorithms with examples and considerations of time complexity.

Uploaded by

Rahul Vimal
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
65 views2 pages

Important Questions

The document outlines important questions related to parallel algorithms, covering various models such as PRAM, Fully Connected, and Pyramid models. It includes topics like parallel summation, matrix transposition, searching algorithms, and the design of parallel versions of sorting and graph algorithms. Each question prompts discussion or development of algorithms with examples and considerations of time complexity.

Uploaded by

Rahul Vimal
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

IMPORTANT QUESTIONS

PARALLEL ALGORITHMS (ECS-073)



Q1. Discuss the parallel computation models and explain with example
PRAM and Sequential model (LMCC Model).
Q2. Explain with example Fully Connected Model and Pyramid Model.
Q5. Explain with example parallel summation and prefix sum
Algorithm/Min-Max algorithm.
Q6. Given A, a parallel algorithm with computation time t, if parallel
algorithms A perform M computation operations, then p processors
can execute A in t+(m-t)/p. Prove it.
Q8. Discuss the parallel algorithm for matrix transposition and matrix
multiplication algorithms with example.
Q9. Discuss the parallel algorithm for searching k
th
element in X+Y on CREW
PRAM.
Q11. Consider a linked list L, the rank of each node in L is the distance from
the end of the list, formally, if succ(i)=nil then rank(i)=0; otherwise
rank(i)=rank(succ(i))+1. Develop a parallel algorithm for a suitable PRAM
model.
Q12. Explain the parallel graph algorithm for finding connected components.
Q13. Design a parallel version of odd-even sorting algorithm. You are also
required to comment on its time-complexity.
Q15. Design and discuss a parallel version of Depth-First-Search algorithm
for P-Depth, Breadth-Depth and Breadth-First Search algorithm with
example.
Q17. Describe in detail a parallel implementation of Bi-directional Gaussian
elimination algorithm.
Q21. Design a parallel algorithm for searching an element on CREW model
with example. Also explain its time complexity.

You might also like