Explanation:
The given symbol represents the predefined process such as a subroutine or a module.
Design Element 
Shape 
Design Element 
Shape 
Design Element 
Shape 
Process 
Sequential data 
Parallel mode 

Terminator 
Direct data 
Loop limit 

Decision 
Manual input 
Onpage reference 

Document 
Card 
Offpage reference 

Data (input and output) 
Paper tape 
Yes/No decision indicators 

Predefined process (such as subroutine or a module) 
Display 
Condition 

Stored data 
Manual operation 
Control transfer 

Internal storage 
Preparation 
Annotation 
Concept:
Order of M_{1} = w × x
Order of M_{2} = x × y
Order of M_{3} = y × z
For cost of (M_{1}M_{2})M_{3} = wxy + wyz. Detailed steps below.
Similarly, cost of M_{1} (M_{2}M_{3}) = xyz + wxz
For (M_{1}M_{2})M_{3 }to take less time than M_{1}(M_{2}M_{3})
(wxy + wyz) < (xyz + wxz)
Dividing both the sides of above equation, we get
(1/x + 1/z) < (1/w + 1/y)
Concept
A = 0.17, B = 0.11, C = 0.24, D = 0.33, E = 0.15
Hence, arranging them is increasing order,
Characters 
Frequency 
B 
0.11 
E 
0.15 
A 
0.17 
C 
0.24 
D 
0.33 
Constructing the tree from bottom up. We will add the nodes generated in the nondecreasing sequence generated above
Characters 
Frequency 




A 
0.17 
C 
0.24 
Node1 
0.26 
D 
0.33 
Characters 
Frequency 








Node1 
0.26 
D 
0.33 
Node2 
0.41 
Characters 
Frequency 












Node2 
0.41 
Node3 
0.59 
Characters 
Frequency 
















Node4 
1.00 
Characters 
Code 
B 
100 
E 
101 
A 
00 
C 
01 
D 
11 
Breaking down the encoding 100 00 01 101
100 = B
00 = A
01 = C
101 = E
Concept:
If we multiply two matrices of order l × m and m × n,
then number of scalar multiplications required = l × m × n
Data:
A_{1} = 10 × 5, A_{2} = 5× 20, A_{3} = 20 × 10, A_{4} = 10 × 5
Calculation:
There are 5 ways in which we can multiply these 4 matrices.
(A_{1}A_{2})(A_{3}A_{4}) , A_{1}A_{2}(A_{3}A_{4}), A_{1} ((A_{2}A_{3}) A_{4}) , (A_{1}(A_{2}A_{3}))A_{4}, ((A_{1}A_{2})A_{3})A_{4}
Minimum number of scalar multiplication can be find out using A_{1} ((A_{2}A_{3})A_{4})
For A_{2}A_{3} (order will become 5 ×10) = 5 × 20 × 10 = 1000
For (A_{2}A_{3})A_{4} (order will become 5 × 5) = 5 × 10 × 5 = 250
For A_{1 }((A_{2}A_{3})A_{4}) [Order will become 10 × 5] = 10× 5 × 5 = 250
Minimum number of scalar multiplication required = 1000 + 250 + 250 = 1500
In all other cases, scalar multiplication are more than 1500.A sorting technique is called stable if
Explanation:
The correct answer is option 2.
Key Points
Concept:
Huffman coding is a data compression technique. It constructs a tree by selecting the minimum frequency of available nodes. And assign the weights 1 for the left child and 0 for the right child or 0 for the left child and 1 for the rightleft.
Add all the internal nodes of the tree
Average length =1 + 0.6 + 0.36 + 0.20 = 2.16
OR
Length of A = 1111 = 4 × 0.11 = 0.44
Length of B = 0 = 1 × 0.4 = 0.4
Length of C = 110 = 3 × 0.16 = 0.48
Length of D = 1110 = 4 × 0.09 = 0.36
Length of E = 10 = 2 × 0.24 = 0.48
Average length = 0.36 + 0.4 + 0.72 + 0.6 + 0.24
= 2.16
∴ Hence the correct answer is 2.16.
The longest common subsequence(LCM)
LCS problem is the problem of finding the longest subsequence common to all sequences in a set of sequences.
Longest Common Subsequence problems is an example of Dynamic Programming.
In LCS:
If there is match, A[i, j] = A[i – 1, j – 1] + 1
If not match: max(A[i – 1, j], A[i, j – 1])
Assembly line scheduling
The main goal of assembly line scheduling is to give the best route or can say fastest from all assembly line.
Assembly line schedulingproblems is an example of Dynamic Programming.
A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:
Character 
Probability 
P 
0.22 
Q 
0.34 
R 
0.17 
S 
0.19 
T 
0.08 
Total 
1.00 
If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is_____.
In Huffman coding, character with minimum probability are combined first and then other in similar way.
First take T and R,
Now, combine P and S
Another two minimum probabilities are 0.25 and 0.34, combine them.
Now, combine all remaining in same way.
Here, for left arm we are considering a 0 and for right arm we are considering 1.
Code for P = 01 (length 2)
Code for Q = 11 (length 2)
Code for R = 101 (length 3)
Code for S = 00 (length 2)
Code for T = 100 (length 3)
Expected length of encoded message =
\(\sum \left( {length\;of\;code\; \times probabilty} \right)\) × number of characters
= [(0.22 × 2) + (0.34 ×2) + (0.17×3) + (0.19×2) + (0.08 × 3)] ×100
= (0.44 + 0.68 + 0.51 + 0.38 + 0.24) × 100
= 225 bits
Consider the following table:
Algorithms 
Design Paradigms 
(P) Kruskal 
(i) Divide and Conquer 
(Q) Quicksort 
(ii) Greedy 
(R) FloydWarshall 
(iii) Dynamic Programming 
Match the algorithms to the design paradigms they are based on.
Knapsack problem has the following two variants
Time Complexity
What is the product of following matrix using Strassen's matrix multiplication algorithm?
\(A=\begin{bmatrix}1 & 3 \\\ 5 & 7 \end{bmatrix} \ \ \ \ B = \begin{bmatrix}8 & 4 \\\ 6 & 2 \end{bmatrix}\)
Concept:
Hence recurrence relation is T(N) = 8T(N/2) + O(N2)
Calculation:
The following paradigm can be used to find the solution of the problem in minimum time:
Given a set of nonnegative integer, and a value K, determine if there is a subset of the given set with sum equal to K:Concept:
“Subset sum problem”:
Given a set of nonnegative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum(K).
Explanation:
Assume array of nonnegative integer of size n. This problem can u solved by 
Method 1: Using recursion
Method 1: Using Dynamic Programming (Optimal solution of “Subset sum problem”)
Dynamic Programming paradigm can be used to find the solution of the problem in minimum time.
Additional Note:
Subset sum problem is NP Complete Problem, because 0/1 Knapsack problem polynomial reduced to sum of
subset problem and 0/1 Knapsack problem is NP complete problem.
Concepts:
If there is match, A[i, j] = A[i – 1, j – 1] + 1
If not match: max(A[i – 1, j], A[i, j – 1])
Table of longest common subsequence:
B → 
p 
q 
p 
r 
q 
r 
p 

A ↓ 
0 
0 
0 
0 
0 
0 
0 
0 
q 
0 
0 
1 
1 
1 
1 
1 
1 
p 
0 
1 
1 
2 
2 
2 
2 
2 
q 
0 
1 
1 
2 
2 
3 
3 
3 
r 
0 
1 
1 
2 
3 
3 
4 
4 
r 
0 
1 
1 
2 
3 
3 
4 
4 
Length of longest common subsequence (LCS) = x = 4
LCS of length 4 are “qprr”, “pqrr” and “qpqr”
∴ y = 3
x + 10y = 4 + 10 × 3 = 34
The minimum number of comparisons required to find the minimum and the maximum of 100
numbers is ________Data:
n = 100
Formula:
minimum number of comparisons = \(\frac{{3n}}{2}  2\)
Calculation:
minimum number of comparisons = \(\frac{{3\; \times \;100}}{2}  2 = 148\)
Important Points:
Divide and conquer is used to achieve minimum comparison
Tournament Method Technique
1. To find the smallest element in the array will take n−1 comparisons = 100 – 1 = 99.
2. To find the largest element 
After the first round of Tournament, there will be exactly n/2 numbers = 50 that will lose the round.
So, the biggest looser (the largest number) should be among these 50 looser.
To find the largest number will take \(\frac{n}{2}  1\) comparisons = 49.
Total 99 + 49 = 148.
Consider a sequence of 14 elements: A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0].
The subsequence sum \(S\left( {i,j} \right) = \mathop \sum \nolimits_{k = i}^j A\left[ k \right]\). Determine the maximum of S(i, j),
where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used.)Largest Sum Contiguous subarray is from index 2 to 11
Maximum subsequence sum = S(2, 11) = 6, 3, 1, 2, 13, 4, 9, 1, 4, 12 = 29
Code in C++ to find the maximum contiguous sum of array
#include <iostream>
using namespace std;
int kadane(int arr[], int n)
{
int max_so_far = 0;
int max_ending = 0;
for (int i = 0; i < n; i++)
{
max_ending = max_ending + arr[i];
max_ending = max(max_ending, 0);
max_so_far = max(max_so_far, max_ending);
}
return max_so_far;
}
int main()
{
int arr[] = { −5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "largest sum of contiguous subarray is " << kadane(arr, n);
return 0;
}
An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
Code:
#include<stdio.h>
int main() {
int ary[10] = {250,1,9,7,3,4,5,21,15,19};
//if we take any 3 elemement from n distinct element in an array one of them would be neither maximum nor minimum.
int a = ary[0];
int b = ary[1];
int c = ary[2];
if((b > a && a >c)  (c > a && a > b))
printf("%d",a);
else if((a > b && b >c)  (c > b && b >a))
printf("%d",b);
else
printf("%d",c);
}
Output: 9
9 is neither maximum nor minimum
Explanation:
Neither recursion nor iteration takes place in the above code, every statement in the above program takes a constant amount of time
and hence order is θ (1)
1. Do not include ao in the subsequence:
Then the maximum possible weight will be equal to the maximum possible weight of a subsequence of {a_{1},a_{2},.....a_{n}} which is represented by Y.
2. Include a_{0 }then the maximum possible weight will be equal to:
a_{0} + (each number picked in Y will get divided by 2) = ao+Y/2.
The key point here is Y will itself pick optimal subsequence to maximize the weight. The value of a_{0} can be anything (negative or i ∈ R it is possible that Y>a_{0}+Y/2.
Here Y/2 meaning: Each number picked in Y will get divided by 2.
Hence the correct answer is max (Y, a0 + Y/2)
Four matrices M_{1}, M_{2}, M_{3} and M_{4} of dimensions p × q, q × r, r × s and s × t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M_{1} × M_{2}) × (M_{3} × M_{4})), the total number of scalar multiplications is part rst+ prt. When multiplied as ((M1 × M2) × (M3 )× M4), the total number of scalar multiplications is pqr+ prs + pst .
If p = 10, g = 100, r = 20, s = 5, and t = 80, then the minimum number of scalar multiplications needed is
The correct answer is option 3
Concept:
If we multiply two matrices [A]_{l × m} and [B]_{m × n}
Then the number of scalar multiplications required = l × m × n
Data:
Given 4 matrix are given with their dimensions
Matrix 
M1 
M2 
M3 
M4 
Dimension 
p× q 
q× r 
r× s 
s× t 
Dimension  10×100  100×20  20×5  5×80 
Calculation:
Total number of ways of multiplication =\(\frac{^{2n}C_n}{n+1}\)
n = 4  1 = 3
Total number of ways of multiplication =\(\frac{^{2n}C_n}{n+1}\) =5
There are 5 ways in which we can multiply these 4 matrices.
(M10×100 × M100× 20 )(M20× 5 × M5× 80)  10×100×20 +20× 5×80 +10×20×80 =44,000 
M10×100 × ( (M100× 20 × M20× 5 )× M5× 80)  10×100×80 +100×20×5 +100×5×80 =130,000 
M10×100 × ( M100× 20 × (M20× 5 × M5× 80))  10×100×80 +100×20×80 +20×5×80 = 248,000 
( (M10×100 × M100× 20 )× M20× 5 )× M5× 80  10×100×20 +10×20×5 +10×5×80 =25,000 
( (M10×100 ×( M100× 20 × M20× 5 ))× M5× 80  10×100×5 +100×20×5 +10×5×80 =19,000 
The minimum number of scalar multiplication can find out using (M1(M2M3))M4
(M1(M2M3))M4 =19,000
Shortcut Trick
Frist find scaler multiplication of those which are common in some of the 5 ways of multiplication
then it will become easy to solve
(M1M2) is common in 1 and 4
(M2M3) is common in 2 and 5
(M3M4) is common in 1 and 3
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 : n  1] is given below.
Let L_{i} denote the length of the longest monotonically increasing sequence starting at index i in the array.
Initialize L_{n1} = 1
For all i such that 0 ≤ i ≤ n  2
\(L_i=\left\{\begin{matrix}1+L_{i+1}&\rm if\ A[i]<A[i+1]\\\ 1&\rm otherwise\end{matrix}\right.\)
Finally the length of the longest monotonically increasing sequence is Max (L_{0}, L_{1}, ... L_{n1}).
Which of the following statements is TRUE?
The correct answer is Option 1.
Key Points
Hence the correct answer is The algorithm uses dynamic programming paradigm.
The correct answer is option 4
Concept
Rule Of Towers of Hanoi problem:
Tower of Hanoi is a mathematical puzzle where we have three poles and n disks. The main goal in the puzzle is to move the entire stack to another pol, obeying the following simple rules:
Solution Of Towers of Hanoi problem:
Begin with n disks on pole one
Moreover, it is easy to say that the puzzle can not be solved using fewer steps. This shows that
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with ṅ discs is
T(n) = 2T(n − 1) + 1
Example:
Follow the above algorithm to solve the problem of the Tower of Hanoi
here we have threepole and also have three disks