Question 1

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

Accepted Answer

The average running time of a quick sort algorithm is O(n log n), as it divides the array and sorts the subarrays in a logarithmic time for each division.

Question 2

Odd-even transposition sort is a variation of

Accepted Answer

Odd-even transposition sort is a variation of bubble sort, where adjacent pairs of elements are compared and possibly swapped in a specific order to sort the entire list.

Question 3

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

Accepted Answer

Odd-even transposition sort has an average case time complexity of O(n^2), similar to bubble sort, because it compares and swaps adjacent elements in a sequence through multiple passes.

Question 4

Shell sort is an improvement on

Accepted Answer

Shell sort is considered an improvement on insertion sort. It allows the exchange of items that are far apart, reducing the total number of movements needed for an element to reach its final position.

Question 5

In parallel Quick Sort Pivot is sent to processes by

Accepted Answer

In parallel Quick Sort, the pivot is sent to all processes involved in the sorting operation, which is effectively done through broadcasting. Broadcasting ensures that every process receives the same pivot value for partitioning their subset of the data.

Question 6

In parallel Quick Sort each process divides the unsorted list into

Accepted Answer

In parallel Quick Sort, each process typically divides the unsorted list into 2 lists: one for elements less than the pivot and another for elements greater than the pivot.

Question 7

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

Accepted Answer

The time complexity of Depth First Search (DFS) is O(V + E) for an adjacency list representation of the graph, where V is the number of vertices and E is the number of edges. This accounts for visiting every vertex once and exploring each edge connected to the vertex.

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?

Accepted Answer

The description matches the Depth-First Search (DFS) algorithm, which explores as far as possible along each branch before backtracking. This is suitable for visiting every vertex in the manner described.

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

Accepted Answer

In the message-passing version of the parallel quicksort, if there are p processes and an array of n elements, each process would ideally handle an equal portion of the array. Therefore, each process stores n/p elements of the array, ensuring the workload is evenly distributed among the processes.

Question 10

In parallel quick sort Pivot selecton strategy is crucial for

Accepted Answer

In parallel quicksort, the pivot selection strategy is crucial for maintaining load balance among processors, ensuring a uniform distribution of elements across process groups, and facilitating effective pivot selection in subsequent levels of the sorting process. This ensures efficiency and optimizes performance in a parallel computing environment.

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

Accepted Answer

The answer of In execution of the hypercube formulation of...

Question 12

Which Parallel formulation of Quick sort is possible

Accepted Answer

Quick sort can be implemented in various parallel computing architectures, including shared-address-space, message-passing, and hypercube formulations. Each of these approaches can leverage the divide-and-conquer nature of Quick sort to perform sorting in parallel, thus improving performance on suitable hardware and software platforms.

Question 13

Which formulation of Dijkstra's algorithm exploits more parallelism

Accepted Answer

The source-parallel formulation of Dijkstra's algorithm is designed to exploit parallelism by allowing multiple shortest path computations to be performed simultaneously from different source nodes.

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

Accepted Answer

In the source partitioned formulation of Dijkstra's algorithm for all-pairs shortest paths, each process is responsible for computing the shortest paths from a subset of source vertices to all other vertices.

Question 15

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

Accepted Answer

In a complete graph, every pair of distinct vertices is connected by a unique edge, meaning each vertex is adjacent to every other vertex.

Question 16

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

Accepted Answer

The space required to store the adjacency matrix of a graph with n vertices is in the order of n squared because an adjacency matrix is a square matrix with dimensions n x n, where n is the number of vertices in the graph.

Question 17

Graph can be represented by

Accepted Answer

The answer of Graph can be represented by
...

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

Accepted Answer

Floyd's algorithm is specifically designed for solving the all-pairs shortest paths problem in a graph, and Dijkstra's algorithm can be adapted to solve the all-pairs shortest paths problem by running it once for each vertex as the source. Prim's and Kruskal's algorithms are used for finding minimum spanning trees, not for solving the all-pairs shortest paths problem.

Question 19

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

Accepted Answer

Simple backtracking is indeed a depth-first search method that terminates as soon as it finds the first solution to the problem it is trying to solve.

Question 20

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

Accepted Answer

Best-first search algorithms are designed to traverse and search through both tree and graph data structures by exploring a graph or tree in a way that prioritizes visiting the most promising node first based on a given heuristic.

Quiz 11: Algorithms and Parallel Formulations