Deck 11: Algorithms and Parallel Formulations

Question 1

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

A)o(n)
B)o(n log n)
C)o(n2)
D)o(log n)

Answer 1

o(n log n)

Question 2

Odd-even transposition sort is a variation of

A)quick sort
B)shell sort
C)bubble sort
D)selection sort

Answer 2

bubble sort

Question 3

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

A)o(n log n)
B)o(n)
C)o(log n)
D)o(n2)

Answer 3

o(n2)

Question 4

Shell sort is an improvement on

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

Question 5

In parallel Quick Sort Pivot is sent to processes by

A)broadcast
B)multicast
C)selective multicast
D)unicast

Question 6

In parallel Quick Sort each process divides the unsorted list into

A)n lists
B)2 lists
C)4 lists
D)n-1 lists

Question 7

Time Complexity of DFS is? (V - number of vertices, E - number of edges)

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

Question 8

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?

A)bfs
B)dfs
C)prim\s
D)kruskal\s

Question 9

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

A)n*p
B)n-p
C)p/n
D)n/p

Question 10

In parallel quick sort Pivot selecton strategy is crucial for

A)maintaing load balance
B)maintaining uniform distribution of elements in process groups
C)effective pivot selection in next level
D)all of the above

Question 11

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

A)first
B)scond
C)third
D)none of above

Question 12

Which Parallel formulation of Quick sort is possible

A)shared-address-space parallel formulation
B)message passing formulation
C)hypercube formulation
D)all of the above

Question 13

Which formulation of Dijkstra's algorithm exploits more parallelism

A)source-partitioned formulation
B)source-parallel formulation
C)partitioned-parallel formulation
D)all of above

Question 14

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

Question 15

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

Question 16

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

A)in order of n
B)in order of n log n
C)in order of n squared
D)in order of n/2

Question 17

Graph can be represented by

A)identity matrix
B)adjacency matrix
C)sprse list
D)sparse matrix

Question 18

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)a and c
B)a and b
C)b and c
D)c and d

Question 19

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

Question 20

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

Question 21

A* algorithm is a

A)bfs algorithm
B)dfs algorithm
C)prim\s algorithm
D)kruskal\s algorithm

Question 22

identify Load-Balancing Scheme/s

A)asynchronous round robin
B)global round robin
C)random polling
D)all above methods

Question 23

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

A)open list
B)closed list
C)node list
D)mode list

Question 24

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

A)gpu kernel
B)cpu kernel
C)os
D)none of above

Question 25

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

A)_host_
B)__global__ 
C)_device_
D)void