Download AKTU B-Tech 6th Sem 2017-2018 NCS 063 Parallel Algorithm 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) 2017-2018 NCS 063 Parallel Algorithm Question Paper

Printed Paes:02 Sub CodezNCS-063
Paperld: lllllili RollNo.| | | | | | | | | | |
B.TECH
(SEM VI) THEORY EXAMINATION 2017-18
PARALLEL ALGORITHM
T ime: 3 Hours T otal Marks: 100
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
SECTION A
1. Note: Attempt all parts. All parts carry equal marks. Write answer in short. (10*2=20)
(a)What are the basic concepts of Parallel Processing?
(b)What do you mean by Sequential Model? Also why there is a need of parallel model
(c) Differentiate between Utilization and efficiency?
(d)What is Sequential Bottleneck in Amdahl?s Law?
(e) What is Bitonic Sequence?
(f) What do you understand by Comparator?
(g) What do you understand by Matrix operations?
(h) Explain Matrix Transposition.
(i) Explain Minimum cost Spanning Tree. Also What do you understand by Graph?
(j) What is Parallel-Backtracking?
SECTION B
2. Note: Attempt any three .Each Question carry 10 marks (3*10=30)
(a) Explain how Pyramid network superior to Mesh and Tree Models. also explain Butter?y and
Shuf?e-exchange network.
(b) What do you mean by cost optimal algorithm? Compute the speedup, cost and efficiency for
addition of n numbers by using n/2 processors by parallel reduction (parallel sum) algorithm
compared to sequential algorithm.
(c) What do you understand by Lower bounds on parallel sorting? Explain Odd Even
Transposition Sort to sort these sequences? X: (G, H, F, D, E, C, B, A).Assume there are four
processors and show each step.
(d)What do you mean by parallel sorting networks? Also discuss the enumeration sort
algorithm.
(e)Explain the following: (1) Parallel Alpha Beta search (ii) Parallel Branch and Bound.
SECTION C
3. Attempt any one part of the following: (10*1=10)
(a) Explain RAM model of serial computation and PRAM model of parallel computation.
Summarize the similarities and differences between them.
01'
(b) Discuss various models of computation in PRAM model. Also explain PRAM algorithm to
compute Parallel and pre?x sum with example.

4. Attempt any one part of the following: (10*1=10)
(a)Write and discuss Cost-Optimal Parallel Algorithm to find Prefix Sums and also Explain
Brent?s Theorem? Write its statement and proof.
Or
(b) What is Amdahl?s Effect? Explain Also discuss Amdahl?s Law. also explain difference
between Difference between Amdahl?s and Gustafson?s Laws.
5. Attempt any one part of the following: (10*1=10)
(a) Explain parallel merging. Also explain merging on the EREW Model.
Or
(b) A list of n=2k unsorted elements can be sorted by using a network of 2k'2k(k+1) comparators
is time O(logzn).Sort a list (C,D,B,H,E,G,F,A) using bitonic merge sort
6. Attempt any one part of the following: (10*1=10)
(a) Explain parallel searching. Also discuss CREW parallel searching algorithm in detail.
or
(b) Discuss 2-D mesh SIMD Model. Describe parallel matrix multiplication algorithm on 2D
Mesh SIMD Model
7. Attempt any one part of the following: (10*1=10)
(a) )Explain Parallel alpha beta search. Also discuss following in brief with example.
(i) Permutation. (ii) Combination. (iii) Derangements.
or
(b) What is combinatorial search problem? How a search problem can be represented by tree ?
Describe a combinatorial searching problem solving methodology that can be represented by
tree. Also Explain Depth and Breadth First search algorithm with an example