Printed Pages: 4
NCS-063
(Following Paper ID and Roll No. to be filled in your Answer Books)
--- Content provided by FirstRanker.com ---
Paper ID: 110663
Roll No.
B.TECH.
Theory Examination (Semester-VI) 2015-16
PARALLEL ALGORITHMS
--- Content provided by FirstRanker.com ---
Time: 3 Hours
Max. Marks: 100
Section-A
Q.1. Attempt all parts. All parts carry equal marks. Write answer of each part in short. (2×10=20)
- Define Cost and Speed-up in parallel algorithm.
- What do you mean by parallel algorithm and parallel computer?
- Write down the design strategies of parallel algorithm.
- Explain CRCW and ERCW computational model in brief.
- Differentiate between static and dynamic interconnection network.
- What is sequential alpha-beta search?
- Differentiate between sequential matrix multiplication and parallel matrix multiplication.
- Define the following
- Contrasting pipelining and data parallelism
- Scalability
- Show the difficulties of solving linear equation on parallel machine in brief.
- Compare sequential searching with parallel searching algorithm.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
Section-B
Attempt any five questions from this section. (10×5=50)
- Explain sequential model and show the need of parallel model and explain any two following models
- Hypercube
- Tree model
- Butterfly
- Discuss the vector-matrix multiplication with the help of example.
- Write two approaches used for dimensionality reduction.
- Explain even-odd transposition sort and shear sort algorithm with neat and clean diagrams.
- Discuss the combinatorial algorithms with suitable example.
- A p-processor PRIORITY PRAM can be simulated by a p-processor EREW PRAM with time complexity increased by a factor of (log p). Prove it.
- Sort a list (C, D, B, H, E, G, F, A) using bitonic merge sort.
- Describe a quick sort algorithm suitable for implementation on hypercube multi-computers.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
Section-C
Attempt any two questions from this section. (15×2=30)
- Q.3. 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.
- 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
- Parallel version algorithm for all-pair shortest paths
- Gauss method for solving linear system
- Parallel Kruskal's algorithm for MST.
--- Content provided by FirstRanker.com ---
Visit FirstRanker.com for more.
--- Content provided by FirstRanker.com ---
This download link is referred from the post: AKTU B-Tech Last 10 Years 2010-2020 Previous Question Papers || Dr. A.P.J. Abdul Kalam Technical University
--- Content provided by FirstRanker.com ---