3.1 Algorithm Development

• What is an algorithm defined as?

  Ordered steps to solve a problem
• Steps to make a peanut butter sandwich

  1️⃣ Gather bread, peanut butter, and a knife

  2️⃣ Open the bread package and take out two slices

  3️⃣ Spread peanut butter evenly on one slice

  4️⃣ Place the second slice on top of the peanut butter

  5️⃣ Cut the sandwich in half, if desired

  6️⃣ Serve the sandwich
• The finite termination property of an algorithm requires it to complete in a finite amount of time
• The steps in an algorithm transform the input into the output
• For what type of problems is the greedy paradigm best suited?

  Optimization problems
• Dynamic Programming solves a complex problem by breaking it down into simpler sub-problems
• The Greedy technique makes locally optimal choices at each stage to find a global optimum
• The Binary Search algorithm is used to find a specific number in a sorted list
• An algorithm is a set of ordered steps that solves a specific problem
• Algorithmic paradigms are high-level approaches to designing algorithms
• What is the main characteristic of the Brute Force algorithmic paradigm?

  Enumerates all solutions
• What is the key advantage of Dynamic Programming?

  Guarantees an optimal solution
• The Divide-and-Conquer paradigm is effective for problems that can be easily divided into independent sub-problems.


  True
• Brute Force involves systematically trying all possible solutions until the correct one is found.


  True
• What is the input for the Bubble Sort algorithm?

  List of numbers
• The first problem in this study material is to sort a list of numbers in ascending order
• The input for the Bubble Sort algorithm is a list of numbers


  True
• The searching algorithm used in this study material is Binary Search
• In the Binary Search pseudocode, the left index is initialized to 0
• What happens in the Binary Search algorithm if the middle element is the target?

  Return middle index
• The space complexity of the Bubble Sort algorithm is O(1)


  True
• The choice of algorithm depends on the specific problem, the size of the input, and the trade-offs between time and space complexity.
• Instructions in an algorithm must be executed in a specific sequence.


  True
• What does the input of an algorithm represent?

  The data the algorithm operates on
• Match the algorithmic paradigm with its description:

  Brute Force ↔️ Enumerates all possible solutions

  Divide-and-Conquer ↔️ Breaks a problem into sub-problems

  Greedy ↔️ Makes locally optimal choices

  Dynamic Programming ↔️ Stores solutions to avoid recomputation
• The choice of algorithmic paradigm depends on the problem's constraints and desired properties.


  True
• The Brute Force technique systematically tries all possible solutions
• Steps of the Bubble Sort algorithm

  1️⃣ Compare adjacent elements

  2️⃣ Swap if necessary

  3️⃣ Repeat until sorted
• Steps of the Binary Search algorithm

  1️⃣ Calculate middle index

  2️⃣ Compare middle element to target

  3️⃣ Adjust search range

  4️⃣ Repeat until found or exhausted
• Match the algorithm component with its description:

  Input ↔️ Data the algorithm operates on

  Output ↔️ Desired result produced by the algorithm

  Steps ↔️ Precise instructions to transform input

  Termination ↔️ Algorithm completes in finite steps
• The Greedy paradigm makes locally optimal choices in the hope of finding a global optimum
• The Greedy paradigm makes locally optimal choices but does not guarantee a globally optimal solution
• For what type of problems is the Brute Force paradigm most suitable?

  Small, simple problems
• Dynamic Programming stores solutions to avoid recomputing
• Dynamic Programming is used for problems with overlapping sub-problems and optimal substructure
• What is the purpose of this study material?

  Practice algorithm development
• What is the problem addressed in the second part of this study material?

  Searching for a number
• What is the output of the Binary Search algorithm if the target number is not found?

  -1
• The Binary Search algorithm continues while the left index is less than or equal to the right index


  True
• What algorithm is used to search for a specific number in a sorted list?

  Binary Search