High Performance Computing Set 3 MCQs

Q1 | What makes a CUDA code runs in parallel

__global__ indicates parallel execution of code

main() function indicates parallel execution of code

kernel name outside triple angle bracket indicates excecution of kernel n times in parallel

first parameter value inside triple angle bracket (n) indicates excecution of kernel n times in parallel

Q2 | In ___________, the number of elements to be sorted is small enough to fit into the process's main memory.

internal sorting

internal searching

external sorting

external searching

Q3 | ______________ algorithms use auxiliary storage (such as tapes and hard disks) for sorting because the number of elements to be sorted is too large to fit into memory.

internal sorting

internal searching

external sorting

external searching

Q4 | ______ can be comparison-based or noncomparison-based.

searching

sorting

both a and b

none of above

Q5 | The fundamental operation of comparison-based sorting is ________.

compare-exchange

searching

sorting

swapping

Q6 | The complexity of bubble sort is Θ(n2).

true

false

Q7 | Bubble sort is difficult to parallelize since the algorithm has no concurrency.

true

false

Q8 | Quicksort is one of the most common sorting algorithms for sequential computers because of its simplicity, low overhead, and optimal average complexity.

true

false

Q9 | The performance of quicksort depends critically on the quality of the ______-.

non-pivote

pivot

center element

len of array

Q10 | the complexity of quicksort is O(nlog n).

true

false

Q11 | The main advantage of ______ is that its storage requirement is linear in the depth of the state space being searched.

bfs

dfs

a and b

none of above

Q12 | _____ algorithms use a heuristic to guide search.

bfs

dfs

a and b

none of above

Q13 | If the heuristic is admissible, the BFS finds the optimal solution.

true

false

Q14 | The search overhead factor of the parallel system is defined as the ratio of the work done by the parallel formulation to that done by the sequential formulation

true

false

Q15 | The critical issue in parallel depth-first search algorithms is the distribution of the search space among the processors.

true

false

Q16 | Graph search involves a closed list, where the major operation is a _______

sorting

searching

lookup

none of above

Q17 | Breadth First Search is equivalent to which of the traversal in the Binary Trees?

pre-order traversal

post-order traversal

level-order traversal

in-order traversal

Q18 | Time Complexity of Breadth First Search is? (V – number of vertices, E – number of edges)

o(v + e)

o(v)

o(e)

o(v*e)

Q19 | Which of the following is not an application of Breadth First Search?

when the graph is a binary tree

when the graph is a linked list

when the graph is a n-ary tree

when the graph is a ternary tree

Q20 | In BFS, how many times a node is visited?

once

twice

equivalent to number of indegree of the node

thrice

Q21 | Is Best First Search a searching algorithm used in graphs.

true

false

Q22 | Which of the following is not a stable sorting algorithm in its typical implementation.

insertion sort

merge sort

quick sort

bubble sort

Q23 | Which of the following is not true about comparison based sorting algorithms?

the minimum possible time complexity of a comparison based sorting algorithm is o(nlogn) for a random input array

any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared

counting sort is not a comparison based sorting algortihm

heap sort is not a comparison based sorting algorithm.

Q24 | mathematically efficiency is

e=s/p

e=p/s

e*s=p/2

e=p+e/e

Q25 | Cost of a parallel system is sometimes referred to____ of product

work

processor time

both

none