Uttar Pradesh Technical University (UPTU) 2007 B.E Computer Science parallel algorithms - Question Paper
parallel algorithms
CS - 052
* V - 1 0 4 9 *
Printed Pages : 4
(Following Paper ID and Roll No. to be filled in your Answer Book)
PAPER ID : 1049
Roll No.
(SEM. VIII) EXAMINATION, 2006-07 PARALLEL ALGORITHMS
[Total Marks : 100
Time : 3 Hours]
Note : (1) Attempt all questions.
(2) All questions carry equal marks.
(3) Be precise in your answers.
1 Attempt any two parts :
10x2=20
(a) Define the following
(i) Contrasting pipelining and data parallelism
(ii) Scalability.
(b) Given a set of n values a1 a, an and an associative operation (f) the prefix sum problem is to compute the n quantities.
al
al + 32
+ 2 "I" <3
al + *2 + a3 + .........................+ an
Give an parallel algorithm to find prefix
sums of n-element using n-1 processors on
PRAM model.
(c) (i) Describe the models of computation in brief.
(ii) Given A, a parallel algorithm with computation time t, if parallel algorithm A performs in computational operations, then P processors can execute algorithm A in time t+(m-t)/p.
Answer any two parts : 10x2=20
(a) Explain odd-even transposition sort. Do you think it is accurate to describe odd-even transposition sort as a parallel bubble sort? Give your views.
(b) Which of the following sequences are bitomic sequences :
(i) 8,4,2,1,2,5,7,9
(ii) 1,9,7,3,2,5
(iii) 1,3,6,4,7,9
(iv) 3,3,4,5,2
(v) 6,2,6,9,7.
(c) Describe multiprocessor oriented parallel quicks short algorithm, with an example.
Answer any two parts : 10x2=20
(a) Describe branch and bound algorithm by taking a suitable example. Describe anomalies in parallel branch and bound.
(b) Define the following in brief:
(i) Distributed tree search for parallel alpha-beta search
(ii) Sequential apha-beta search.
|
(c) Use the minimax algorithm to evaluate the following game tree : |
 |
|
Fig. 1 |
4 Answer any two parts : 10x2=20
(a) Explain the algorithm for matrix multiplication on the hypercube $ IMD model, with suitable example.
(b) Explain the row-column-oriented algorithm for matrix multiplication for multicomputers.
(c) Suppose that two n x n matrices A and B are to be multiplied, and assume that every element of A and B is stored exactly once and that no processing element contains more than one element of either matrix. If we ignore any data broadcasting facility, multiplying A and B to produce the n x n matrix C requires atleast S
data routing steps, where a (2.) > n2. [Given
a data item originally available at a single processor in some model of parallel computation, let the function a (k), be the maximum number of processors to which the data can be transmitted in K or fewer data routing steps.] V-1049] 3 [Contd..
Attempt any two parts :
(a) Given p > 2 processers, an upper bound on the number of active operations required by P - depth search on the CREW (Concurrent read exclusive write) PRAM model is
Di denotes the degree of vertex i
(b) Define the connected components of an undirected graph. Explain the Hirschbergs connected component algorithm with the suitable example.
(c) Discuss the parallel algorithm based on KruskaT s algorithm for minimum cost spanning tree.
|
Attachment: |
| Earning: Approval pending. |
