Deck 3: Parallel Execution in CUDA, Sorting Algorithms, and Search Techniques

Question 1

What makes a CUDA code runs in parallel

A)__global__ indicates parallel execution of code
B)main() function indicates parallel execution of code
C)kernel name outside triple angle bracket indicates excecution of kernel n times in parallel
D)first parameter value inside triple angle bracket (n) indicates excecution of kernel n times in parallel

Answer 1

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

Question 2

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

A)internal sorting
B)internal searching
C)external sorting
D)external searching

Answer 2

internal sorting

Question 3

______________ 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.

A)internal sorting
B)internal searching
C)external sorting
D)external searching

Answer 3

external sorting

Question 4

______ can be comparison-based or noncomparison-based.

A)searching
B)sorting
C)both a and b
D)none of above

Question 5

The fundamental operation of comparison-based sorting is ________.

A)compare-exchange
B)searching
C)sorting
D)swapping

Question 6

The complexity of bubble sort is ?(n2).

Question 7

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

Question 8

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

Question 9

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

A)non-pivote
B)pivot
C)center element
D)len of array

Question 10

the complexity of quicksort is O(nlog n).

Question 11

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

A)bfs
B)dfs
C)a and b
D)none of above

Question 12

_____ algorithms use a heuristic to guide search.

A)bfs
B)dfs
C)a and b
D)none of above

Question 13

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

Question 14

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

Question 15

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

Question 16

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

A)sorting
B)searching
C)lookup
D)none of above

Question 17

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

A)pre-order traversal
B)post-order traversal
C)level-order traversal
D)in-order traversal

Question 18

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

A)o(v + e)
B)o(v)
C)o(e)
D)o(v*e)

Question 19

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

A)when the graph is a binary tree
B)when the graph is a linked list
C)when the graph is a n-ary tree
D)when the graph is a ternary tree

Question 20

In BFS, how many times a node is visited?

A)once
B)twice
C)equivalent to number of indegree of the node
D)thrice

Question 21

Is Best First Search a searching algorithm used in graphs.

Question 22

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

A)insertion sort
B)merge sort
C)quick sort
D)bubble sort

Question 23

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

A)the minimum possible time complexity of a comparison based sorting algorithm is o(nlogn) for a random input array
B)any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared
C)counting sort is not a comparison based sorting algortihm
D)heap sort is not a comparison based sorting algorithm.

Question 24

mathematically efficiency is

A)e=s/p
B)e=p/s
C)e*s=p/2
D)e=p+e/e

Question 25

Cost of a parallel system is sometimes referred to____ of product

A)work
B)processor time
C)both
D)none