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

Answer: Option 3

Explanation: 

Statement 1: Greedy technique solves the problem correctly and always provides an optimized solution to the problem.

This Statement is False. Since the Greedy technique does not always solve a problem correctly.

Statement 2: Bellman ford, Floyd-warshal, and Prim’s algorithms use the Dynamic Programming technique to solve the Path problems.

This Statement is also False Since Prim's algorithm does not use the Dynamic Programming technique.

Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. 

The correct answer is Option 3) Greedy method.

Key Points

• The Greedy Method is an algorithmic paradigm that solves optimization problems by making a sequence of choices, each of which looks best at the moment (locally optimal).
• The key assumption is that these locally optimal choices will lead to a globally optimal solution.
• Common examples where greedy algorithms work effectively:
  • Activity Selection Problem
  • Fractional Knapsack Problem
  • Dijkstra’s Shortest Path Algorithm (non-negative weights)
  • Prim’s Minimum Spanning Tree Algorithm

Additional Information

• Option 1 – Branch and Bound: Used for solving combinatorial problems like TSP, Knapsack (0/1), but explores the entire state space with bounding to eliminate unpromising options.
• Option 2 – Backtracking: Explores all possibilities recursively and backtracks upon reaching a dead end. More exhaustive than greedy.
• Option 4 – Dynamic Programming: Solves problems by combining the solutions of overlapping subproblems. Suitable for problems with optimal substructure and overlapping subproblems, not just local choices.

Conclusion: Greedy Method solves optimization problems by making locally optimal choices at each step with the hope of reaching a global optimum.

The correct answer is Trial and error.

Key Points

• The backtracking approach is based on the trial-and-error principle, where potential solutions are incrementally built and tested for feasibility.
  • It systematically explores all possible configurations to solve a problem.
  • If a solution fails to satisfy the conditions, the algorithm "backtracks" by undoing the last step and trying a different option.
  • This approach is commonly used for problems involving decision-making, such as puzzles, combinatorial problems, and optimization tasks.
  • Examples include the N-Queens problem, Sudoku solver, and maze traversal.
  • Backtracking is a recursive approach, where the algorithm returns to previous states to explore other possibilities.

Additional Information

• Backtracking is used in a wide range of applications, including artificial intelligence, game theory, and constraint satisfaction problems.
• The efficiency of backtracking can be enhanced by employing pruning techniques to eliminate unnecessary branches.
• It contrasts with approaches like greedy algorithms, which make decisions based on immediate benefits, or divide-and-conquer, which splits problems into smaller subproblems.
• The trial-and-error principle ensures that all possibilities are exhaustively explored, making it a reliable method for finding solutions.
• Despite its reliability, backtracking may not be optimal for large-scale problems due to its time complexity.

The correct answer is Evaluating the time and space complexity of the algorithm.

Key Points

• Evaluating the time and space complexity of an algorithm is crucial because it helps determine the algorithm's efficiency and scalability.
  • Time complexity measures the amount of computational time an algorithm takes to complete as a function of the input size.
  • Space complexity measures the amount of memory an algorithm requires to execute as a function of the input size.
  • By analyzing both time and space complexity, developers can choose the most optimal approach to solve a problem effectively.
  • Efficient algorithms reduce processing time and conserve resources, which is critical in real-world applications, especially for large datasets.
• Other concerns like testing on large datasets, choosing programming languages, and hardware implementation are secondary considerations and depend on the algorithm's efficiency.

Additional Information

• Algorithms are often analyzed using Big-O notation, which describes the upper bound of their performance.
• Common time complexities include O(1), O(log n), O(n), O(n^2), and O(2^n), with lower complexities being more efficient.
• Space complexity is particularly important in systems with limited memory resources, such as embedded systems.
• Optimizing time and space complexity is a key aspect of computer science and software development.

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 =

n = 4 - 1 = 3

Total number of ways of multiplication = =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.