Download AKTU B-Tech 6th Sem 2017-2018 NCS 063 Parallel Algorithm Question Paper

Printed Pages: 02

Paper Id: 110623

Sub Code: NCS-063

--- Content provided by FirstRanker.com ---

Roll No.

B.TECH

(SEM VI) THEORY EXAMINATION 2017-18

PARALLEL ALGORITHM

Time: 3 Hours

--- Content provided by FirstRanker.com ---

Total 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)

1. (a) What are the basic concepts of Parallel Processing?

--- Content provided by FirstRanker.com ---

2. (b) What do you mean by Sequential Model? Also why there is a need of parallel model
3. (c) Differentiate between Utilization and efficiency?
4. (d) What is Sequential Bottleneck in Amdahl's Law?
5. (e) What is Bitonic Sequence?
6. (f) What do you understand by Comparator?

--- Content provided by FirstRanker.com ---

7. (g) What do you understand by Matrix operations?
8. (h) Explain Matrix Transposition.
9. (i) Explain Minimum cost Spanning Tree. Also What do you understand by Graph?
10. (j) What is Parallel-Backtracking?

SECTION B

--- Content provided by FirstRanker.com ---

2. Note: Attempt any three. Each Question carry 10 marks (3*10=30)

1. (a) Explain how Pyramid network superior to Mesh and Tree Models. also explain Butterfly and Shuffle-exchange network.
2. (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.
3. (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.
4. (d) What do you mean by sorting networks? Also discuss the enumeration sort algorithm.

--- Content provided by FirstRanker.com ---

5. (e) Explain the following: (i) Parallel Alpha Beta search (ii) Parallel Branch and Bound.

SECTION C

3. Attempt any one part of the following: (10*1=10)

1. (a) Explain RAM model of serial computation and PRAM model of parallel computation. Summarize the similarities and differences between them. Or
2. (b) Discuss various models of computation in PRAM model. Also explain PRAM algorithm to compute Parallel and prefix sum with example.

--- Content provided by FirstRanker.com ---

4. Attempt any one part of the following: (10*1=10)

1. (a) Write and discuss Cost-Optimal Parallel Algorithm to find Prefix Sums and also Explain Brent's Theorem? Write its statement and proof. Or
2. (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)

1. (a) Explain parallel merging. Also explain merging on the EREW Model. Or

--- Content provided by FirstRanker.com ---

2. (b) A list of n=2k unsorted elements can be sorted by using a network of 2k-2k(k+1) comparators is time O(log2n).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)

1. (a) Explain parallel searching. Also discuss CREW parallel searching algorithm in detail. Or
2. (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)

--- Content provided by FirstRanker.com ---

1. (a) Explain Parallel alpha beta search. Also discuss following in brief with example. (i) Permutation. (ii) Combination. Or
2. (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.

FirstRanker.com