2.2.3 Algorithm design

• The finiteness characteristic of an algorithm ensures it terminates in a finite number of steps
• Order the key characteristics of a good algorithm

  1️⃣ Definiteness

  2️⃣ Finiteness

  3️⃣ Input

  4️⃣ Output

  5️⃣ Effectiveness
• Each step of an algorithm must be feasible and executable to ensure its effectiveness
• Steps to find the maximum value in an array using an algorithm

  1️⃣ Start with the first element as the current maximum

  2️⃣ Iterate through the array, comparing each element to the current maximum

  3️⃣ If an element is greater, update the current maximum

  4️⃣ Return the current maximum as the result
• Dynamic programming avoids redundant computations by reusing previously calculated results

  True
• Dynamic Programming reduces redundant computations by solving sub-problems once
• Steps of the Merge Sort algorithm

  1️⃣ Divide the array into two halves

  2️⃣ Recursively sort each half

  3️⃣ Merge the sorted halves
• In the pseudo-code for Merge Sort, the variable `mid` calculates the middle
• What are the three main steps in the Divide and Conquer technique?

  Divide, Conquer, Combine
• What is a key disadvantage of Greedy algorithms?

  May not find optimal solution
• Steps of the Divide and Conquer technique

  1️⃣ Divide the problem into smaller sub-problems

  2️⃣ Conquer the sub-problems recursively

  3️⃣ Combine the solutions
• An effective algorithm must ensure that each step is feasible and executable.

  True
• In an algorithm to find the maximum value, you update the current maximum if a larger element is found.


  True
• Which algorithm design technique is used to solve the Fibonacci sequence problem?

  Dynamic Programming
• Dynamic Programming guarantees an optimal solution but requires high space complexity.
• In the Coin Change problem, a Greedy algorithm selects the largest denomination coin first to reduce the amount needed.
• In the coin change problem, selecting the largest denomination coin first is a greedy approach.


  True
• Dynamic programming avoids redundant computations by storing solutions to overlapping sub-problems
• Match the algorithm design technique with its key idea:

  Divide and Conquer ↔️ Break down into smaller parts

  Greedy ↔️ Choose best immediate option

  Dynamic Programming ↔️ Solve sub-problems once
• What does time complexity measure in algorithm analysis?

  Execution time
• What is the time complexity of a constant-time algorithm?

  O(1)
• The recursive Fibonacci sequence has a time complexity of O(2^n)
• An algorithm accepts zero or more inputs
• A scalable algorithm maintains performance as the input size increases.
• What is a key disadvantage of the greedy algorithm design technique?

  May not find optimal solution
• Match the complexity class with its description:

  O(1) ↔️ Independent of input size

  O(n) ↔️ Scales directly with input size

  O(log n) ↔️ Divides input size at each step

  O(n^2) ↔️ Grows as the square of input size
• What is the purpose of an algorithm?

  Solve a specific problem
• What does effectiveness mean in the context of algorithms?

  Feasible and executable
• Divide and conquer is efficient for large problems and can be parallelized.


  True
• Steps in the divide and conquer technique

  1️⃣ Divide the problem into sub-problems

  2️⃣ Conquer the sub-problems recursively

  3️⃣ Combine the solutions
• The choice of algorithm design technique depends on the problem and desired trade-offs.


  True
• A real-world example of divide and conquer is merge sort.
• An algorithm is a step-by-step procedure to solve a specific problem
• How many inputs can an algorithm have?

  Zero or more
• A good algorithm must have clear and unambiguous steps to ensure definiteness
• An algorithm can accept zero or more inputs


  True
• Divide and conquer algorithms break a problem into smaller sub-problems
• Match the algorithm design technique with its key idea:

  Divide and Conquer ↔️ Break down into manageable parts

  Greedy ↔️ Best immediate decision

  Dynamic Programming ↔️ Store and reuse sub-problem solutions
• Dynamic Programming guarantees an optimal solution.


  True
• The left half of the array in Merge Sort is processed recursively.

  True