Algorithm Design Techniques MCQ Quiz - Objective Question with Answer for Algorithm Design Techniques - Download Free PDF

The correct answer is Depth-first search.

Key Points

• A state-space tree for a backtracking algorithm is constructed using Depth-first search.
  • In backtracking, we start from the root of the state-space tree and explore each branch before backtracking.
  • The algorithm explores as far down a branch as possible before backtracking to the previous state to explore other branches.
  • This approach ensures that all possible solutions are considered and is particularly useful in constraint satisfaction problems.
  • Examples of problems that use backtracking include solving puzzles like Sudoku, the N-Queens problem, and generating permutations.

Additional Information

• Depth-first search can be implemented using recursion or an explicit stack data structure.
• It has lower memory requirements than breadth-first search as it stores fewer states at any given time.
• However, depth-first search might get stuck in deep or infinite branches, which can be mitigated using iterative deepening.
• In backtracking, solutions can be found faster in many cases since it prunes branches that are not feasible early on.

The correct answer is O(m.n).

Key Points

• The Longest Common Subsequence (LCS) problem is a classic computer science problem that can be solved using Dynamic Programming (DP).
• The time complexity of solving the LCS problem using DP is O(m.n), where m and n are the lengths of the two sequences being compared.
• This is because the DP approach involves filling up a 2D table of size m x n where each cell represents the length of the LCS of the substrings considered up to that point.
• Here is a step-by-step explanation of the DP approach to solve the LCS problem:

/ Function to find the length of the Longest Common Subsequence
function lcs(X, Y) {
    let m = X.length;
    let n = Y.length;
    let L = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    / Building the L[m+1][n+1] table in bottom-up fashion
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (X[i - 1] === Y[j - 1]) {
                L[i][j] = L[i - 1][j - 1] + 1;
            } else {
                L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
            }
        }
    }

    / L[m][n] contains the length of LCS for X[0..m-1], Y[0..n-1]
    return L[m][n];
}

/ Example usage
let X = "AGGTAB";
let Y = "GXTXAYB";
console.log("Length of LCS is", lcs(X, Y));  / Output: 4
    

Additional Information

• The LCS problem is used in various applications such as diff tools for comparing files, bioinformatics for sequence alignment, and more.
• Even though the time complexity is O(m.n), which can be computationally expensive for large sequences, the DP approach is efficient for moderate-sized inputs.
• There are more advanced techniques like space optimization to reduce the memory usage from O(m.n) to O(min(m,n)), making the algorithm more practical for large inputs.

The correct answer is Option 2.

Key Points

• Dynamic programming has the following characteristics:
  • Optimal substructure: This means that the solution to a problem can be constructed efficiently from solutions to its subproblems. For example, in the case of the shortest path problem, the shortest path from A to C through B can be derived from the shortest path from A to B and B to C.
  • Overlapping subproblems: This refers to the situation where the same subproblems are solved multiple times in the process of solving the overall problem. For example, in the Fibonacci sequence, the same Fibonacci numbers are computed multiple times.
  • Memoization: This technique involves storing the results of expensive function calls and reusing the cached result when the same inputs occur again. This helps in reducing the time complexity of algorithms that solve overlapping subproblems.

Additional Information

• Dynamic programming is often used for optimization problems where the goal is to find the best solution among many possibilities.
• Examples of problems that can be solved using dynamic programming include the knapsack problem, the traveling salesman problem, and sequence alignment in bioinformatics.
• Dynamic programming can be implemented in a top-down approach with memoization or a bottom-up approach with tabulation.
• It is an essential concept in computer science and is widely used in various fields such as operations research, economics, and artificial intelligence.

The correct answer is option 4.

Key Points

• Breadth First Search (A) uses a Queue (IV).
  • BFS explores all nodes at the present depth level before moving on to nodes at the next depth level, making use of a queue data structure to keep track of nodes to be explored.
• Depth First Search (B) uses a Stack (III).
  • DFS explores as far as possible along each branch before backtracking, making use of a stack data structure to keep track of the path.
• Prefix (C) is associated with LISP (I).
  • In LISP and other prefix notation systems, operators precede their operands.
• Infix (D) is related to the Syntax tree (II).
  • Infix notation is commonly used in arithmetic expressions and can be represented by a syntax tree where each node represents an operator and its children represent operands.

Additional Information

• Breadth First Search (BFS) and Depth First Search (DFS) are fundamental algorithms used in graph theory and have applications in various fields such as AI, network analysis, and more.
• Prefix notation, also known as Polish notation, and Infix notation are different ways of writing arithmetic expressions used in computer science and mathematics.
• Understanding the differences between these notations and their implementations is crucial for fields like compiler design and expression evaluation.

The correct answer is Greedy function.

Key Points

• Feedforward networks and the Backpropagation algorithm are used in training neural networks.
• These algorithms can learn to approximate Boolean functions, continuous functions, and even arbitrary functions.
• Greedy algorithms, on the other hand, are a different class of algorithms that build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit.
• Therefore, Greedy function is not directly related to the feedforward networks on the Backpropagation algorithm.

Additional Information

• Feedforward networks process data in one direction from input to output.
• Backpropagation is a supervised learning algorithm used for training artificial neural networks.
• It minimizes the error by adjusting the weights in the network based on the error gradient.
• Greedy algorithms are typically used in optimization problems and are not used in neural network training.
• Examples of greedy algorithms include Dijkstra's algorithm for shortest paths, Prim's algorithm for minimum spanning trees, etc.

Concept:

Flowcharts use special shapes to represent different types of actions or steps in a process. Lines and arrows show the sequence of the steps, and the relationships among them. These are known as flowchart symbols.

Hence Option 4 is correct

Explanation:

• An oval represents a start or end point
• A line is a connector that shows relationships between the representative shapes
• A parallelogram represents input and output
• A rectangle represents a process
• A diamond indicates a decision

The given symbol represents the predefined process such as a sub-routine or a module.

• A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.
• This means a sorting algorithm is called stable if two identical elements do not change the order during the process of sorting.
• Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. and some sorting algorithms are not, like Heap Sort, Quick Sort, etc.

Explanation:

• An algorithm is a strictly defined finite sequence of well-defined statements (often called instruction or commands) that provide the solution to a problem or to a specific class of problems for an acceptable set of input values (if there are any inputs).
• An algorithm is a step by step procedure to solve a given problem.
• The term here “finite” means that the algorithm should reach an endpoint and cannot run forever.
• An algorithm must satisfy the following properties:

• Input: The algorithm must have input values from a specified set.
• Output: The algorithm must produce the output values from a specified set of input values.

                     The output values are the solution to a problem.

• Finiteness: For any input, the algorithm must terminate after certain/finite member of steps i.e. should be terminating and not infinite.
• Definiteness: All steps of the algorithm must be precisely defined.
• Effectiveness: It must be possible to perform each step of the algorithm correctly and in a finite amount of time. It is not enough that each step is definite (or precisely defined), but it must also be feasible.

Code:

#include
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)

Note All elements are distinct, select any three numbers and output 2^nd largest from them. If in the same question 'distinct' keyword is not given, we will have to get 3 distinct elements and this would take O(n) time in the worst case. From these 3 distinct elements the middle element is neither minimum nor maximum. In this case it is O(n). We hope clear your doubt.

8 - queen’s problem:

• In this, 8 queens are placed on a 8 × 8 chessboard such that none of them can take same place.
• It is the backtracking approach. In backtracking approach, all the possible configurations are checked and check whether result is obtained or not.
•  A queen can only be attacked if it is in the same row or column or diagonal of another queen.

Single source shortest path:

• It is used to find the shortest path starting from a source to the all other vertices.
• It is based on greedy approach.
• Example of single source shortest path algorithm is Dijkstra’s algorithm which initially consider all the distance to infinity and distance to source is 0.

Strassen’s matrix multiplication:

• It is a method used for matrix multiplication. It uses divide and conquer approach to multiply the matrices.
• Time consumption is improved by using Strassen’s method as compared to standard multiplication method.
• It is faster than standard method. Strassen’s multiplication can be performed only on square matrices.

Optimal binary search tree:

• It is also known as weight balanced binary tree. In optimal binary search tree, dummy key is added in the tree by first constructing a binary search tree.
• It is based on dynamic programming approach. Total cost must be as small as possible.

Concept:

An algorithm is a set of instructions for solving a problem or carrying out a computation. An algorithm is a precise list of instructions that, when implemented in a software or hardware-based procedure, carry out the predetermined activities in a sequential fashion.

Explanation:

Characteristics of a good algorithm are:-

• The algorithm does not terminate after a fixed number of iterations.
• There is ambiguity present.
• The algorithm acquires the input but does not process it.
• The algorithm contains a logical flaw.
• The algorithm produces invalid results.
• The output is not displayed by the algorithm.
• The algorithm does not precisely outline the execution steps.
• The algorithm is not optimized for optimal performance.

Hence, option 4) is not characteristic of a good algorithm.

Concept:

Optimal coding technique merge the probabilities one by one starting from the lower one.

Explanation:

Characters are: A, B, C, D and E with probabilities 0.08, 0.40, 0.25, 0.15, 0.12 respectively.

Step 1: Merge 0.08 (A) and 0.12, (E)

Step 2: Merge 0.20 with 0.15(D)

Step 3: Merge 0.35 and 0.25 (C)

Step 4: Merge 0.60 with 0.40 (B), then assign 0 to all left edges and 1 to all right edges.

Code for A (0.08) = 1110 (length 4)

Code for B (0.40) = 0 (length 1)

Code for C (0.25) = 10(length 2)

Code for D (0.15) = 110 (length 3)

Code for E (0.12) = 1111 (length 4)

Average code length = [(0.08 × 4) + (0.40 × 1) + (0.25 × 2) + (0.15 × 3) + (0.12 × 4)] / 1 = 0.32 + 0.40 + 0.50 + 0.45 + 0. 48 = 2.15

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

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.

1. (M1M2)(M3M4)
2. M1 ((M2M3) M4)
3. M1(M2(M3M4))
4. ((M1M2)M3)M4
5. (M1(M2M3))M4

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

Knapsack problem has the following two variants-

1. Fractional Knapsack Problem
2. 0/1 Knapsack Problem

Time Complexity- 

• Each entry of the table requires constant time θ(1) for its computation.
• It takes θ(nw) time to fill (n+1)(w+1) entries. Therefore, O(nw + n + w +1) =  O(nw )
• It takes θ(n) time for tracing the solution since the tracing process traces the n rows.
• Thus, overall θ(nw) time is taken to solve 0/1 knapsack problem using dynamic programming.