High Performance Computing Set 11 MCQs

Q1 | What is the average running time of a quick sort algorithm?

o(n)

o(n log n)

o(n2)

o(log n)

Q2 | Odd-even transposition sort is a variation of

quick sort

shell sort

bubble sort

selection sort

Q3 | What is the average case time complexity of odd-even transposition sort?

o(n log n)

o(n)

o(log n)

o(n2)

Q4 | Shell sort is an improvement on

quick sort

bubble sort

insertion sort

selection sort

Q5 | In parallel Quick Sort Pivot is sent to processes by

broadcast

multicast

selective multicast

unicast

Q6 | In parallel Quick Sort each process divides the unsorted list into

n lists

2 lists

4 lists

n-1 lists

Q7 | Time Complexity of DFS is? (V – number of vertices, E – number of edges)

o(v + e)

o(v)

o(e)

o(v*e)

Q8 | A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he should use?

bfs

dfs

prim\s

kruskal\s

Q9 | Given an array of n elements and p processes, in the message-passing version of the parallel quicksort, each process stores ---------elements of array

n*p

n-p

p/n

n/p

Q10 | In parallel quick sort Pivot selecton strategy is crucial for

maintaing load balance

maintaining uniform distribution of elements in process groups

effective pivot selection in next level

all of the above

Q11 | In execution of the hypercube formulation of quicksort for d = 3, split along -----------dimention to partition sequence into two big blocks, one greater than pivot and other smaller than pivot as shown in diagram

first

scond

third

none of above

Q12 | Which Parallel formulation of Quick sort is possible

shared-address-space parallel formulation

message passing formulation

hypercube formulation

all of the above

Q13 | Which formulation of Dijkstra's algorithm exploits more parallelism

source-partitioned formulation

source-parallel formulation

partitioned-parallel formulation

all of above

Q14 | In Dijkstra's all pair shortest path each process compute the single-source shortest paths for all vertices assigned to it in SOURCE PARTITIONED FORMULATION

true

false

Q15 | A complete graph is a graph in which each pair of vertices is adjacent

true

false

Q16 | The space required to store the adjacency matrix of a graph with n vertices is

in order of n

in order of n log n

in order of n squared

in order of n/2

Q17 | Graph can be represented by

identity matrix

adjacency matrix

sprse list

sparse matrix

Q18 | to solve the all-pairs shortest paths problem which algorithm/s is/are used a) Floyd's algorithm b) Dijkstra's single-source shortest paths c) Prim's Algorithm d) Kruskal's Algorithm

a) and c)

a) and b)

b) and c)

c) and d)

Q19 | Simple backtracking is a depth-first search method that terminates upon finding the first solution.

true

false

Q20 | Best-first search (BFS) algorithms can search both graphs and trees.

true

false

Q21 | A* algorithm is a

bfs algorithm

dfs algorithm

prim\s algorithm

kruskal\s algorithm

Q22 | identify Load-Balancing Scheme/s

asynchronous round robin

global round robin

random polling

all above methods

Q23 | important component of best-first search (BFS) algorithms is

open list

closed list

node list

mode list

Q24 | A CUDA program is comprised of two primary components: a host and a _____.

gpu kernel

cpu kernel

os

none of above

Q25 | The kernel code is dentified by the ________qualifier with void return type

_host_

__global__

_device_

void