Algorithms Test 1

Question 1
2 / -0.33

When using Dijkstra’s algorithm to find shortest path in a graph, which of the following statement is not true?

A
It can find shortest path within the same graph data structure

B
Every time a new node is visited, we choose the node with smallest known distance/cost (weight) to visit first

C
Shortest path always passes through least number of vertices

D
The graph needs to have a non-negative weight on every edge

Question 2
2 / -0.33

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

A
Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n²)

B
Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n²)

C
Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)

D
Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)

Question 3
2 / -0.33

Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).

A
Quick Sort

B
Heap Sort

C
Merge Sort

D
Insertion Sort

Question 4
2 / -0.33

What is the worst-case and average-case time complexity of the Binary search?

A
O(n²)

B
O(1)

C
O(n log n)

D
O(log n)

Question 5
2 / -0.33

Consider the below-given statement written in C language:
int A = {25, 9, 15, 30, 11, 17 , 22}
Bubble sort is applied on array A. Which element is present at index 2 after the second iteration?

A
11-11

B
114-111

C
117-116

D
119-112

Question 6
2 / -0.33

What is the time complexity for the below given block of code where i, j, n are integers and lines of code do contain any extra line space between them?
for(i = 0; i < n; i ++ )
for(j = m ; j > 0; j = j/2)
printf(“Hello world” );

A
O(n) + O(log2m)

B
O(n × m)

C
O(n × log₂m)

D
O(n + log₂m)

Question 7
2 / -0.33

Consider the following table:
Algorithms
Design Paradigms
(A) Huffman Coding
(I) Divide and Conquer
(B) Merge sort
(II) Greedy
(C) Coin change problem
(III) Dynamic Programming

Match the algorithms to the design paradigms they are based on.

A
(A) ↔ (I), (B) ↔ (II), (C) ↔ (III)

B
(A) ↔ (II), (B) ↔ (III), (C) ↔ (I)

C
(A) ↔ (III), (B) ↔ (I), (C) ↔ (II)

D
(A) ↔ (II), (B) ↔ (I), (C) ↔ (III)

Question 8
2 / -0.33

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this: 2 5 1 7 9 12 11 10 Which statement is correct?

A
The pivot could be either the 7 or the 9.

B
The pivot could be the 7, but it is not the 9

C
The pivot is not the 7, but it could be the 9

D
Neither the 7 nor the 9 is the pivot.

Question 9
2 / -0.33

Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?

A
Heap Sort

B
Selection Sort

C
Insertion Sort

D
Merge Sort

Question 10
2 / -0.33

If T(n) = 2T(n/2)+nlogn then T(n)?

A
O(nlogn)

B
O(n²)

C
O(n(logn)²)

D
O(2ⁿ)

Question 11
2 / -0.33

If G = (V,E) is a directed graph, then length of adjacency list is ______ and it requires ______ amount of memory.

A
2|E|, θ(V)

B
|E|, θ(V+E)

C
|E|, θ(E)

D
2|E|, θ(V+E)

Question 12
2 / -0.33

Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this: 16 14 15 10 12 27 28. How many heapify operations have been performed on root of heap?

A
1

B
2

C
3 or 4

D
5 or 6

Question 13
2 / -0.33

Consider 5 array of size 25, 31, 37, 49, 57 respectively. All arrays are sorted. All the arrays into a single array by using the optimal algorithm and the single array is again a sorted array. What is the maximum number of comparisons that will be needed in the worst case?

A
450-450

B
4504-4501

C
4507-4506

D
4509-4502

Question 14
2 / -0.33

What is the best time complexity of bubble sort?

A
N²

B
N logN

C
N

D
N(logN)²

Question 15
2 / -0.33

You have to sort 1 GB of data with only 100 MB of available main memory. Which sorting technique will be most appropriate?

A
Heap sort

B
Merge sort

C
Quick sort

D
Insertion sort

Question 16
2 / -0.33

Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?

A
Insertion Sort with time complexity O(kn).

B
Heap Sort with time complexity O(nLogk).

C
Quick Sort with time complexity O(kLogk).

D
Merge Sort with time complexity O(kLogk).

Question 17
2 / -0.33

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 18
2 / -0.33

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 algorithm

D
Heap Sort is not a comparison based sorting algorithm

Question 19
2 / -0.33

What is the worst case time complexity of insertion sort where position of the data to be inserted is calculated using binary search?

A
N

B
NlogN

C
N²

D
N(logN)²

Question 20
2 / -0.33

Consider a hash table with 9 slots. The hash function is ℎ(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

A
3, 0, and 1

B
3, 3 and 3

C
4, 0, and 1

D
3, 0, and 2

Question 21
2 / -0.33

Which sorting algorithm will take least time when all elements of input array are identical? Consider typical implementations of sorting algorithms.

A
Insertion Sort

B
Heap Sort

C
Merge Sort

D
Selection Sort

Question 22
2 / -0.33

Consider a hypothetical system in which merge sort is implemented on an array of size of 2 bytes each. The size of the array is 2 MB. The maximum time taken by the merge sort to process the array is 256 seconds. What is the size of the input in MB of a problem that can be solved in 81.92 minutes?

A
16

B
32

C
48

D
64

Question 23
2 / -0.33

Consider two strings M = ”abababbaa” and N = ”babaa”. The length of the longest common subsequence between two given string is r and the number of times the length of the longest common subsequence repeated in the matrix is n while using Dynamic programming. What is the value of r + r×n + n² ?
NOTE: Common subsequence may not necessarily be contiguous

A
19-19

B
194-191

C
197-196

D
199-192

Question 24
2 / -0.33

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

A
θ(n)

B
θ(nLogn)

C
θ(n²)

D
θ(n² log n)

Question 25
2 / -0.33

Consider the 10 Jobs for A to J. The execution of each job takes 1 unit of time. One job can be executed at a time. Each job is related with a profit and a deadline. If job is completed before deadline then the corresponding profit is earned. The maximum profit earned is _____.
Job
A
B
C
D
E
F
G
H
I
J
Profit
25
35
40
30
18
25
33
43
19
25
Deadline
4
7
4
7
1
4
6
5
3
6

A
231-231

B
2314-2311

C
2317-2316

D
2319-2312

Submit Test

Algorithms	Design Paradigms
(A) Huffman Coding	(I) Divide and Conquer
(B) Merge sort	(II) Greedy
(C) Coin change problem	(III) Dynamic Programming

Job	A	B	C	D	E	F	G	H	I	J
Profit	25	35	40	30	18	25	33	43	19	25
Deadline	4	7	4	7	1	4	6	5	3	6

Algorithms Test...

Question 1

It can find shortest path within the same graph data structure

Every time a new node is visited, we choose the node with smallest known distance/cost (weight) to visit first

Shortest path always passes through least number of vertices

The graph needs to have a non-negative weight on every edge

Question 2

Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n2)

Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n2)

Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)

Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)

Question 3

Quick Sort

Heap Sort

Merge Sort

Insertion Sort

Question 4

O(n2)

O(1)

O(n log n)

O(log n)

Question 5

11-11

114-111

117-116

119-112

Question 6

O(n) + O(log2m)

O(n × m)

O(n × log2m)

O(n + log2m)

Question 7

(A) ↔ (I), (B) ↔ (II), (C) ↔ (III)

(A) ↔ (II), (B) ↔ (III), (C) ↔ (I)​​

(A) ↔ (III), (B) ↔ (I), (C) ↔ (II)

(A) ↔ (II), (B) ↔ (I), (C) ↔ (III)

Question 8

The pivot could be either the 7 or the 9.

The pivot could be the 7, but it is not the 9

The pivot is not the 7, but it could be the 9

Neither the 7 nor the 9 is the pivot.

Question 9

Heap Sort

Selection Sort

Insertion Sort

Merge Sort

Question 10

O(nlogn)

O(n2)

O(n(logn)2)

O(2n)

Question 11

2|E|, θ(V)

|E|, θ(V+E)

|E|, θ(E)

2|E|, θ(V+E)

Question 12

1

2

3 or 4

5 or 6

Question 13

450-450

4504-4501

4507-4506

4509-4502

Question 14

N2

N logN

N

N(logN)2

Question 15

Heap sort

Merge sort

Quick sort

Insertion sort

Question 16

Insertion Sort with time complexity O(kn).

Heap Sort with time complexity O(nLogk).

Quick Sort with time complexity O(kLogk).

Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n²)

Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n²)

O(n²)

O(n × log₂m)

O(n + log₂m)

(A) ↔ (II), (B) ↔ (III), (C) ↔ (I)

O(n²)

O(n(logn)²)

O(2ⁿ)

N²

N(logN)²

N²

N(logN)²

θ(n²)

θ(n² log n)