Category: Data Structures & Algorithms Objective Questions

250+ TOP MCQs on Route Cipher and Answers

Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) on “Route Cipher”.

1. What is route cipher?
a) a transposition cipher that performs encryption by following an imaginary pattern on a grid
b) a substitution cipher that performs encryption by following an imaginary pattern on a grid
c) a transposition cipher that performs encryption by following a zig zag pattern on a grid
d) a substitution cipher that performs encryption by following a zig zag pattern on a grid

Answer: a
Clarification: Route cipher is a transposition cipher. It encrypts the plain text by following an imaginary pattern on a grid. This pattern can vary from one version of route cipher to others.

2. Route cipher is an example of ____________
a) mono-alphabetic cipher
b) poly-alphabetic cipher
c) transposition cipher
d) additive cipher

Answer: c
Clarification: Route cipher is a transposition cipher. It falls under the category of transposition cipher as it encrypts the plain text by rearranging its letters.

3. Encryption in Route cipher is done ___________
a) by arranging the letters in a zig zag fashion in a table
b) by randomly arranging letters
c) by following an imaginary pattern drawn on a grid
d) by swapping adjacent letters
Answer: c
Clarification: Route cipher is a transposition cipher. It encrypts the plain text by following an imaginary pattern on a grid.

4. Which of the following ciphers are created by shuffling the letters of a word?
a) playfair cipher
b) route cipher
c) vigenere cipher
d) hill cipher
Answer: b
Clarification: In transposition cipher the letters of the given data are shuffled in a particular order, fixed by a given rule. Route cipher is the only transposition cipher out of the given options.

5. Route cipher is closely related to?
a) Autokey cipher
b) Hill cipher
c) Rail fence cipher
d) Columnar transposition cipher
Answer: c
Clarification: Route cipher is closely related to rail fence cipher. In rail fence cipher the plain text is written in a zig zag fashion in a grid whereas in route cipher the plain text is written horizontally.

6. Rail fence cipher is more secure as compared to route cipher?
a) true
b) false
Answer: b
Clarification: Rail fence is cipher is less secure than route cipher. It is because the key of route cipher not only defines the size of the grid but also the path that is to be followed.

7. Router cipher becomes less secure when we have to encrypt longer messages.
a) true
b) false
Answer: b
Clarification: The key of route cipher not only defines the size of grid but also the path that is to be followed. So longer the message is, the harder it becomes to guess the path.

8. What will be the plain text corresponding to cipher text “RSEADC” if with the number of columns are given to be 3 and route of reading is down the columns?
a) SACRED
b) DERSAC
c) REDSAC
d) SEDRAC

Answer: c
Clarification: For decryption we reverse the process used in encryption. So we arrange the letters of cipher text down the columns and then read the grid horizontally.

So the resulting plain text is “REDSAC”.

9. What will be the plain text corresponding to cipher text “SFNUFACT” if with number of columns are given to be 3 and route of reading is from the bottom right anti clockwise?
a) FACTSFUN
b) FACTFUNS
c) FUNSFACT
d) FUNFACTS

Answer: d
Clarification: For decryption we reverse the process used in encryption. So we arrange the letters of cipher text from bottom right anti clockwise and then read the grid horizontally.

So the resulting plain text is “FUNFACTS”.

10. What will be the ciphered text if route cipher is used for encrypting the plain text “” with number of columns given to be 5 and route from the bottom right anti clockwise?
a) SUANNDFROY
b) SORAFUDYNN
c) YOFNASUNDRY
d)

Answer: c
Clarification: For encrypting a plain text using route cipher we use a table having 5 columns as shown below. Then we read from the bottom right anti clockwise to cipher the plain text.

So the ciphered text becomes “YOFNASUNDRY”.

11. What will be the ciphered text if route cipher is used for encrypting the plain text “” with a number of columns given to be 5 and route of reading is down the columns?
a) SUANNDFROY
b) SORAFUDYNN
c) SNAUDNORFY
d)

Answer: a
Clarification: For encrypting a plain text using route cipher we use a table having 5 columns as shown below. Then we read down the columns to cipher the plain text.

So the ciphered text becomes “SUANNDFROY”.

250+ TOP MCQs on Topological Sort and Answers

Data Structure Multiple Choice Questions on “Topological Sort”.

1. Topological sort can be applied to which of the following graphs?
a) Undirected Cyclic Graphs
b) Directed Cyclic Graphs
c) Undirected Acyclic Graphs
d) Directed Acyclic Graphs
Answer: d
Clarification: Every Directed Acyclic Graph has one or more topological ordering whereas Cyclic and Undirected graphs can’t be ordered topologically.

2. Most Efficient Time Complexity of Topological Sorting is? (V – number of vertices, E – number of edges)
a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)
Answer: a
Clarification: The topological sort algorithm has complexity same as Depth First Search. So, DFS has a complexity O(V+E).

3. In most of the cases, topological sort starts from a node which has __________
a) Maximum Degree
b) Minimum Degree
c) Any degree
d) Zero Degree
Answer: d
Clarification: Topological sort starts with a node which has zero degree. If multiple such nodes exists then it can start with any node.

4. Which of the following is not an application of topological sorting?
a) Finding prerequisite of a task
b) Finding Deadlock in an Operating System
c) Finding Cycle in a graph
d) Ordered Statistics

Answer: d
Clarification: Topological sort tells what task should be done before a task can be started. It also detects cycle in the graph which is why it is used in the Operating System to find the deadlock. Ordered statistics is an application of Heap sort.

5. Topological sort of a Directed Acyclic graph is?
a) Always unique
b) Always Not unique
c) Sometimes unique and sometimes not unique
d) Always unique if graph has even number of vertices

Answer: c
Clarification: The topological sort of a graph can be unique if we assume the graph as a single linked list and we can have multiple topological sort order if we consider a graph as a complete binary tree.

6. Topological sort can be implemented by?
a) Using Depth First Search
b) Using Breadth First Search
c) Using Depth and Breadth First Search
d) Using level ordered search

Answer: c
Clarification: We can implement topological sort by both BFS and DFS. In BFS, we use queue as data structure and in DFS, we use Linked list (if recursive) or Stack (if not recursive) as data structure.

7. Topological sort is equivalent to which of the traversals in trees?
a) Pre-order traversal
b) Post-order traversal
c) In-order traversal
d) Level-order traversal

Answer: a
Clarification: In pre-order traversal of trees, we process the root first and then child from left to right.

8. A man wants to go different places in the world. He has listed them down all. But there are some places where he wants to visit before some other places. What application of graph can he use to determine that?
a) Depth First Search
b) Breadth First Search
c) Topological Sorting
d) Dijkstra’s Shortest path algorithm
Answer: c
Clarification: As the definition of topological sorting suggests, it is the way to do tasks in prescribed order. So, if he does topological sorting, it will be easy for him to recognize what should be the order to visit different places.

9. When the topological sort of a graph is unique?
a) When there exists a hamiltonian path in the graph
b) In the presence of multiple nodes with indegree 0
c) In the presence of single node with indegree 0
d) In the presence of single node with outdegree 0
Answer: a
Clarification: A hamiltonian path exists in a Directed Acyclic Graph when all pairs of consecutive vertices are in sorted order and are connected by edges. In such a case, there exists a unique topological sorting order.

250+ TOP MCQs on Exponential Search and Answers

Data Structures & Algorithms Multiple Choice Questions on “Exponential Search”.

1. Exponential search algorithm requires which of the following condition to be true?
a) array should be sorted
b) array should have not be sorted
c) array should have a less than 128 elements
d) array should be partially sorted

Answer: a
Clarification: Exponential sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.

2. Which of the following searching algorithm is used with exponential sort after finding the appropriate range?
a) Linear search
b) Binary search
c) Jump search
d) Fibonacci Search

Answer: b
Clarification: In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range.

3. Exponential search has ____________
a) neither an exponential space complexity nor exponential time complexity
b) exponential time complexity but a linear space complexity
c) exponential space complexity but a linear time complexity
d) both exponential time and space complexity

Answer: a
Clarification: Exponential search has neither an exponential space complexity nor exponential time complexity. It is named exponential search because it searches for an element in an exponential manner.

4. Choose the correct while loop statement from the following that finds the range where are the element being search is present (x is the element being searched in an array arr of size n)?
a) 

while (i 

b) 


while (i 

c) 


while (arr[i] 

d) 


while (i 
Answer: a
Clarification: In exponential search we first find the range where the element being searched can be present before applying binary search. We do this by comparing the value of element under search with the array elements present at the positions 1,2,4,8….n. 

 
 


	
5. What is the time complexity of exponential sort?
a) O(n)
b) O(2n)
c) O(n log n)
d) O(log n)
Answer: d
Clarification: In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range. This takes O(log n) time in the worst case.


6. What is the auxiliary space requirement of an exponential sort when used with iterative binary search?
a) O(n)
b) O(2n)
c) O(1)
d) O(log n)
Answer: c
Clarification: Exponential search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).


7. What is the auxiliary space requirement of the exponential sort when used with recursive binary search?
a) O(n)
b) O(2n)
c) O(1)
d) O(log n)
Answer: d
Clarification: Exponential search requires an auxiliary space of log n when used with recursive binary search. This space is required for the recursion call stack space.


8. Which of the following searching algorithm is fastest?
a) jump search
b) exponential search
c) linear search
d) all are equally fast
Answer: b
Clarification: Exponential search has the least time complexity (equal to log n) out of the given searching algorithms. This makes exponential search preferable in most cases.


9. In which of the following case jump search will be preferred over exponential search?
a) jumping backwards takes significantly more time than jumping forward
b) jumping forward takes significantly more time than jumping backwards
c) when the given array is very large in size
d) when the given array is very small in size
Answer: a
Clarification: Jump search only needs to jump backwards once, while an exponential search can jump backwards up to log n times. Thus jump search will be preferred if jumping backwards is expensive.


10. Best case of the exponential search will have time complexity of?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
Answer: a
Clarification: Best case of the exponential search will be when the first element of the array is the element that is being searched. In this case, only one comparison will be required. Thus it will have a time complexity of O(1).


11. Which of the following code correctly represent exponential search?
a)



	


int expSearch(int arr[], int n, int x) 
{ 
	if (arr[0] == x) 
		return 0; 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 
 
return binarySearch(arr, i/2, min(i, n-1), x);
//applies binary search in the calculated range
}
















b)
















int expSearch(int arr[], int n, int x) 
{ 
	if (arr[0] == x) 
		return 0; 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 
	return binarySearch(arr, i, min(i, n-1), x);
//applies binary search in the calculated range
}
















c)
















int expSearch(int arr[], int n, int x) 
{ 
 
	if (arr[0] == x) 
		return 0; 
 
 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i/2; 
 
return binarySearch(arr, i/2, min(i, n-1), x);
//applies binary search in the calculated range
}
















d)
















int expSearch(int arr[], int n, int x) 
{ 
	if (arr[0] == x) 
		return 0; 
 
	int i = 1; 
	while (i < n && arr[i] <= x) 
		i = i*2; 
 
return binarySearch(arr, i/2, max(i, n-1), x); 
//applies binary search in the calculated range
}
















Answer: a
Clarification: In exponential search we first find a range where the required element should be present in the array. Then we apply binary search in this range.


 
 


12. Jump search has a better time complexity than the exponential search.
a) True
b) False


Answer: b
Clarification: The worst case time complexity of jump search and exponential searches are O(n1/2) and O(log n) respectively. So exponential search is better in terms of time complexity.


13. Exponential search performs better than binary search when the element being searched is present near the starting point of the array.
a) True
b) False


Answer: a
Clarification: Exponential search first finds the range where binary search needs to be applied. So when the element is present near the starting point of the array then exponential search performs better than standard binary search.


14. Choose the incorrect statement about exponential search from the following.
a) Exponential search is an in place algorithm
b) Exponential search has a greater time complexity than binary search
c) Exponential search performs better than binary search when the element being searched is present near the starting point of the array
d) Jump search has a greater time complexity than an exponential search


Answer: b
Clarification: Time complexity of exponential search and binary search are the same. But exponential search performs better than binary search when the element being searched is present near the starting point of the array.


15. Which of the following is not an alternate name of exponential search?
a) Logarithmic search
b) Doubling search
c) Galloping search
d) Struzik search


Answer: a
Clarification: Logarithmic search is not an alternate name of the exponential search. Some alternate names of exponential search are Doubling search, Galloping search and Struzik search.


 and Answers.

250+ TOP MCQs on Shell Sort MCQs and Answers Pdf

Data Structures & Algorithms Multiple Choice Questions on “Shell Sort”.

1. Shell sort is also known as _____________
a) diminishing decrement sort
b) diminishing increment sort
c) partition exchange sort
d) diminishing insertion sort

Answer: b
Clarification: Shell sort is also known as diminishing increment sort since each pass is defined by an increment h such that only the records which are h units apart will be sorted.

2. Statement 1: Shell sort is a stable sorting algorithm.
Statement 2: Shell sort is an in-place sorting algorithm.
a) Both statements are true
b) Statement 2 is true but statement 1 is false
c) Statement 2 is false but statement 1 is true
d) Both statements are false

Answer: b
Clarification: In Shell sort, the relative order of elements with equal values may change. Therefore, it is not a stable sorting algorithm. Shell sort is an in-place sorting algorithm as it requires O(1) auxiliary space.

3. Shell sort is applied on the elements 27 59 49 37 15 90 81 39 and the chosen decreasing sequence of increments is (5,3,1). The result after the first iteration will be
a) 27 59 49 37 15 90 81 39
b) 27 59 37 49 15 90 81 39
c) 27 59 39 37 15 90 81 49
d) 15 59 49 37 27 90 81 39

Answer: c

4. Consider the following code snippet, which implements the Shell sort algorithm.

shellSort( int elements[], int num_elements , int incrmnts[], int num_incrmnts)
{
	int incr, j, k, span, y;
	for(incr = 0; incr ;&lt num_incrmnts; incr++)
	{
		span = incrmnts[incr]; data-structure-questions-answers-shell-sort
		for( j = span; j &lt; num_elements; j++)
		{
			k = j;
			y = elements[j];
			while (________ )
			{
				elements [ k]  = elements[k - span];
				k = k - span;
			}
			elements[k] = y;
		}
	}

Which condition will correctly implement the while loop?
a) k >= j && y < elements[k- span]
b) k >= span || y < elements[k + span]
c) k >= j || y < elements[k + span]
d) k >= span && y < elements[k- span]

Answer: d
Clarification: In Shell sort, for increment = h we sort the sub-arrays that start at arbitrary element and include every hth element.
So, if h = 4 the algorithms sorts:
Sub-array formed with elements at positions 1, 5, 9, 13 … in original array
Sub-array formed with elements at positions 2, 6, 10, 14 … in original array
Sub-array formed with elements at positions 3, 7, 11, 15 … in original array
Sub-array formed with elements at positions 4, 8, 12, 16 … in original array
Therefore, the condition given in option k >= span && y < elements[k- span] will implement while loop correctly.

5. Shell sort is an improvement on ____
a) insertion sort
b) selection sort
c) binary tree sort
d) quick sort

Answer: a
Clarification: Shell sort is an improvement on insertion sort that allows the exchange of elements that are far apart. Shell sort algorithm sorts separate sub-arrays of the original input array. These sub-arrays contains every hth element of the original array.

6. An array that is first 7-sorted, then 5-sorted becomes _________
a) 7-ordered
b) 5-ordered
c) both 2-ordered and 5-ordered
d) both 7-ordered and 5-ordered

Answer: d
Clarification: An array that is 7-sorted, becomes 7-ordered. And an array that is 5-sorted, becomes 5-ordered. If k-ordered array is h-sorted, it remains k-ordered. Thus, an array that is first 7-sorted, then 5-sorted becomes both 7-ordered and 5-ordered.

7. If Hibbard increments (h1= 1, h2= 3, h3= 7, …, hk = 2k–1) are used in a Shell sort implementation, then the best case time complexity will be ________
a) O(nlogn)
b) O(n)
c) O(n2)
d) O(logn)

Answer: a
Clarification: The best case occurs when the array is already sorted. In best case the number of comparison for each of the increments-based insertion sorts is equal to length of array.
Here 2k –1 < n, where n is the number of records. So k < log(n+1), thus the sorting time in best case is less the n * log(n+1). Therefore best case time complexity is O(nlogn).

8. Records R1, R2, R3,.. RN with keys K1, K2, K3,.. KN are said to be h-ordered, if ________
a) Ki <= Ki+h for 1<= i*h <= N
b) Kh <= Ki+h for 1<= i <= N
c) Ki <= Kh for 1<= i <= h
d) Ki <= Ki+h for 1<= i <= N-h

Answer: d
Clarification: Records are h-ordered if every hth element (starting anywhere) yields a sorted array. Therefore, given records with keys K1, K2, K3,.. KN are said to be h-ordered, if Ki <= Ki+h for 1<= i <= N-h.

9. Shell sort is more efficient than insertion sort if the length of input arrays is small.
a) True
b) False

Answer: b
Clarification: Insertion sort is more efficient than Shell sort if the length of array is small because insertion sort is quite simple to program and involve very few actions other than comparisons and replacements on each pass.

10. Which of the following is true?
a) Shell sort’s passes completely sort the elements before going on to the next-smallest gap while Comb sort’s passes do not completely sort the elements
b) Shell sort’s passes do not completely sort the elements before going on to the next-smallest gap like in Comb sort
c) Comb sort’s passes completely sort the elements before going on to the next-smallest gap like in Shell sort
d) Shell sort’s passes do not completely sort the elements before going on to the next-smallest gap while Comb sort’s passes completely sort the elements

Answer: a
Clarification: Both Shell sort and Comb sort have repeated sorting passes with decreasing gaps. Unlike Comb sort, in Shell sort the array is sorted completely in each pass before going on to the next-smallest gap.

250+ TOP MCQs on LSD Radix Sort and Answers

Data Structures & Algorithms Multiple Choice Questions on “LSD Radix Sort”.

1. Which of the following is the distribution sort?
a) Heap sort
b) Smooth sort
c) Quick sort
d) LSD radix sort

Answer: d
Clarification: In Distribution sort the inputted values are distributed to multiple intermediate structures which are then combined and placed on the output. And LSD radix sort distributes values into buckets based on the digits within values, so it is a distribution sort.

2. What is the worst case time complexity of LSD radix sort?
a) O(nlogn)
b) O(wn)
c) O(n)
d) O(n + w)
Answer: b
Clarification: Time complexity of LSD radix sort depends upon the word size and the number on items. It runs in O(wn) time in worst case, where n is the number of inputted elements and w is the number of digits in the largest number.

3. LSD radix sort requires _____ passes to sort N elements.
a) (w/logR)
b) N(w/logR)
c) (w/log(RN))
d) (wN/log(N))

Answer: a
Clarification: LSD radix sort sorts the N elements in (w/logR) passes where w is the number of digits in largest number and R(radix) is extra space required for performing the sorting operation.

4. Which of the following is false?
a) LSD radix sort is an integer sorting algorithm
b) LSD radix sort is a comparison sorting algorithm
c) LSD radix sort is a distribution sort
d) LSD radix sort uses bucket sort

Answer: b
Clarification: LSD radix sort uses bucket sort for grouping the keys based on the digits at that value. And as it grouped the keys based on the digits at that values, it is integer sorting algorithm.

5. Which of the following sorting algorithm is stable?
a) Heap sort
b) Selection sort
c) In-place MSD radix sort
d) LSD radix sort
Answer: d
Clarification: In LSD radix sort after sorting the multiple elements with the same key will be in the same order as they were in the input array. So LSD radix sort is stable sort.

6. LSD radix sort is faster than comparison sorts.
a) True
b) False

Answer: b
Clarification: LSD radix sort is faster than comparison sorts when the word size is less than logn. But LSD radix sort runs slowly for elements with larger word size and smaller radix.

7. Which of the following should be used to sort a huge database on a fixed-length key field?
a) Insertion sort
b) Merge sort
c) LSD radix sort
d) Quick sort
Answer: c
Clarification: LSD radix requires only w passes to sort a fixed-length string, where w is a length of the strings. So, LSD radix sort is best suited to sort a huge database on a fixed-length key field.

8. Which of the following is a combination of LSD and MSD radix sorts?
a) Forward radix sort
b) 3-way radix quick sort
c) Trie base radix sort
d) Flash sort

Answer: a
Clarification: Forward radix sort combines the advantages of LSD and MSD radix sort. Forward radix sort inspects a complete horizontal strip at a time just like LSD radix sort.

9. Which of the following is true for the LSD radix sort?
a) works best for variable length strings
b) accesses memory randomly
c) inner loop has less instructions
d) sorts the keys in left-to-right order

Answer: b
Clarification: LSD radix sort sorts the keys in right-to-left order, working with Least Significant Digit first. The inner loop has a lot of instructions and LSD radix sort is used to sort fixed-length strings.

10. LSD radix sort is in-place sorting algorithm.
a) False
b) True

Answer: a
Clarification: LSD radix is not an in-place sorting algorithm. It needs extra memory to store the elements in bucket and its worst case space complexity is O(w + R).

and Answers.

250+ TOP MCQs on Strassen’s Algorithm and Answers

Data Structures & Algorithms Multiple Choice Questions on “Strassen’s Algorithm”.

1. Strassen’s algorithm is a/an_____________ algorithm.
a) Non- recursive
b) Recursive
c) Approximation
d) Accurate

Answer: b
Clarification: Strassen’s Algorithm for matrix multiplication is a recursive algorithm since the present output depends on previous outputs and inputs.

2. What is the running time of Strassen’s algorithm for matrix multiplication?
a) O(n2.81)
b) O(n3)
c) O(n1.8)
d) O(n2)

Answer: a
Clarification: Strassen’s matrix algorithm requires only 7 recursive multiplications of n/2 x n/2 matrix and Theta(n2) scalar additions and subtractions yielding the running time as O(n2.81).

3. What is the running time of naïve matrix multiplication algorithm?
a) O(n2.81)
b) O(n4)
c) O(n)
d) O(n3)
View Answer

Answer: d
Clarification: The traditional matrix multiplication algorithm takes O(n3) time. The number of recursive multiplications involved in this algorithm is 8.

4. Strassen’s matrix multiplication algorithm follows ___________ technique.
a) Greedy technique
b) Dynamic Programming
c) Divide and Conquer
d) Backtracking

Answer: c
Clarification: Strassen’s matrix multiplication algorithm follows divide and conquer technique. In this algorithm the input matrices are divided into n/2 x n/2 sub matrices and then the recurrence relation is applied.

5. The number of scalar additions and subtractions used in Strassen’s matrix multiplication algorithm is ________
a) O(n2.81)
b) Theta(n2)
c) Theta(n)
d) O(n3)

Answer: b
Clarification: Using Theta(n2) scalar additions and subtractions, 14 matrices are computed each of which is n/2 x n/2. Then seven matrix products are computed recursively.

6. Running time of Strassen’s algorithm is better than the naïve Theta(n3) method.
a) True
b) False

Answer: a
Clarification: Strassen’s Algorithm requires only 7 recursive multiplications when compared with the naïve Theta(n3) method which reuires 9 recursive multiplications to compute the product.

7. Given the program of naïve method.

for i=1 to n do
   for j=1 to n do
       Z[i][j]=0;
       for k=1 to n do 
            ___________________________

Fill in the blanks with appropriate formula
a) Z[i][j] = Z[i][j] + X[i][k]*Y[k][j]
b) Z[i][j] = Z[i][j] + X[i][k] + Y[k][j]
c) Z[i][j] = Z[i][j] * X[i][k]*Y[k][j]
d) Z[i][j] = Z[i][j] * X[i][k] + Y[k][j]

Answer: a
Clarification: In the naïve method of matrix multiplication the number of iterating statements involved are 3, because of the presence of rows and columns. The element in each row of one matrix is multiplied with each element in the column of the second matrix. The computed value is placed in the new matrix Z[i][j].

8. Who demonstrated the difference in numerical stability?
a) Strassen
b) Bailey
c) Lederman
d) Higham

Answer: d
Clarification: The difference in the numerical stability was demonstrated by Higham. He overemphasized that Strassen’s algorithm is numericaly unstable for some applications.

9. What is the recurrence relation used in Strassen’s algorithm?
a) 7T(n/2) + Theta(n2)
b) 8T(n/2) + Theta(n2)
c) 7T(n/2) + O(n2)
d) 8T(n/2) + O(n2)

Answer: a
Clarification: The recurrence relation used in Strassen’s algorithm is 7T(n/2) + Theta(n2) since there are only 7 recursive multiplications and Theta(n2) scalar additions and subtractions involved for computing the product.

10. Who discussed techniques for reducing the memory requirements for Strassen’s algorithm?
a) Strassen
b) Lederman
c) Bailey
d) Higham
Answer: c
Clarification: The submatrices formed at the levels of recursion consume space. Hence in order to overcome that Bailey discussed techniques for reducing the memory required.

11. What is the formula to calculate the element present in second row, first column of the product matrix?
a) M1+M7
b) M1+M3
c) M2+M4 – M5 + M7
d) M2+M4

Answer: d
Clarification: The element at second row, first column can be found by the formula M2 + M4, where M2 and M4 can be calculated by
M2= (A(2,1) + A(2,2)) B(1,1)
M4=A(2,2)(B(1,2) – B(1,1)).

12. Strassen’s Matrix Algorithm was proposed by _____________
a) Volker Strassen
b) Andrew Strassen
c) Victor Jan
d) Virginia Williams

Answer: a
Clarification: Strassen’s matrix multiplication algorithm was first published by Volker Strassen in the year 1969 and proved that the n3 general matrix multiplication algorithm wasn’t optimal.

13. How many iterating statements are involved in the naïve method of matrix multiplication?
a) 1
b) 2
c) 3
d) 4

Answer: c
Clarification: In the naïve method of matrix multiplication the number of iterating statements involved are 3, because of the presence of rows and columns in a matrix. The element in each row of the first matrix is multiplied with each element in the column of the second matrix.

14. Strassen’s algorithm is quite numerically stable as the naïve method.
a) True
b) False

Answer: b
Clarification: Strassen’s algorithm is too numerically unstable for some applications. The computed result C=AB satisfies the inequality with a unit roundoff error which corresponds to strong stability inequality(obtained by replacing matrix norms with absolute values of the matrix elements).

15. Compute the product matrix using Strassen’s matrix multiplication algorithm.
Given a11=1; a12=3;a21=5;a22=7
b11=8;b12=4;b21=6;b22=2
a) c11=20;c12=12;c21=100;c22=15
b) c11=22;c12=8;c21=90;c22=32
c) c11=15;c12=7;c21=80;c22=34
d) c11=26;c12=10;c21=82;c22=34
Answer: d
Clarification: The solution can be obtained by
C11=1*8 + 3*6 =8+18=26
C12=1*4 + 3*2 =4+6=10
C21=5*8 + 7*6 =40+42=82
C22= 5*4 + 7*2=20+14=34.