Download AKTU B-Tech 6th Sem 2015-2016 NCS 063 Parallel Algorithms Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 6th Semester (Sixth Semester) 2015-2016 NCS 063 Parallel Algorithms Question Paper

Printed Pages: 4 NCS-063
(Following Paper ID and Roll No. to be ?lled in your
Answer Books)
RollNoJllIIlllll
B.TECH.
Theory Examination (Semester-VI) 2015-16
PARALLELALGORITHMS
Time .' 3 Hours ' Max. Marks : 100
Section-A
Q.l. Attempt all parts. All parts carry equal marks. Write
answer of each part in short. (2X10=20)
(a) De?ne Cost and Speed-up in parallel algorithm.
(b) What do you mean by parallel algon'thm and parallel
computer?
(0) Write down the design strategies of parallel algo-
rithm.
((1) Explain CRCW and ERCW computational model in
brief.
( 1) P.T.O.
2705/19-8/382/9550

(e)
(f)
(g)
(h)
(i)
(a)
Differentiate between static and dynamic intercon-
nection network.
What is sequential alpha-beta search?
Differentiate between sequential matrix multiplica-
tion and parallel matrix multiplication.
Show the difficulties of solving linear equation on
parallel machine in brief. ,
Write two approaches used for dimensionality i'educ- \
tion.
Compare sequential searching with parallel search-
ing algorithm.
Section-B
Q.2. Attempt any five questions from this section. (10X5=50)
Explain sequential model and show the need of par-
allel model and explain any two following models
(i) Hypercube
(ii) Tree model
(iii) Butter?y
(2)
2705/198/382/9550
(b)
(C)
(d)
(6)
De?ne the following
(i) Contrasting pipelining and data parallelism
(ii) Scalability
Discuss the vector-matrix multiplication with the help
of example.
Explain even-odd transposition sort and shear sort
? algorithm with neat and clam diagrams.
Discuss the combinatorial algorithms with suitable
example.
(t) A p-processor PRIORITY PRAM can be simulated by
a p-processor BREW PRAM with time complexity
increased by a factor of 6) (log p). Prove it.
(g) Sort a list (C, D, B, H, E, G, F, A) using bitonic merge
son.
(h) Describe a quick sort algorithm suitable for implemen-
tation on hypercube multi-computers.
(3) _ P.T.O.
270571'f8/382/9550 ? ? '

Section-C
Attempt any two questions from this section. (15X2=30)
Q3. What do you mean by cost optimal algorithm? Compute the
speedup, cost and ef?ciency for addition of 11 numbers by
using n/2 processors by parallel reduction (parallel sum) algo-
rithm compared to sequential algorithm.
Q.4. Let A = {5, 2, 4, 5} be a sequence and p = 16 where p is
no processors. Sort this sequence by using Enumeration sort
algorithm for CRCW technique and show each step. Also
write the algorithm.
Q.5. Write short notes on any two
(a) Parallel version algorithm for all-pair shortest paths
(b) Gauss method for solving linear system
(c) Parallel Kruskal?s algorithm for MST.
(4)
2705/19'8/382/9550