1.4.3 Algorithms

• An algorithm must be ambiguous to allow for flexibility in its execution.

  False
• An algorithm must handle all possible inputs to be considered input-specific.


  True
• What is the efficiency of an algorithm measured in terms of?

  Time and memory
• An algorithm must terminate after a limited number of steps to be finite.


  True
• Match the algorithm type with its description:

  Sorting Algorithms ↔️ Arrange elements in order

  Searching Algorithms ↔️ Locate specific elements

  Graph Algorithms ↔️ Solve graph-related problems

  Dynamic Programming ↔️ Break down complex problems
• Match the algorithm type with an example:

  Sorting ↔️ Bubble Sort

  Searching ↔️ Binary Search

  Graph ↔️ Dijkstra's Algorithm
• Dijkstra's Algorithm finds the shortest path in a weighted graph
• An algorithm with high simplicity is easy to understand and implement.


  True
• Searching algorithms are used to locate specific elements in a data structure.


  True
• What is the time complexity of linear search in the worst-case scenario?

  O(n)
• Merge sort is a divide-and-conquer algorithm used for sorting data.
• Big Omega notation represents the best-case lower bound of an algorithm's time complexity.
• Divide and conquer algorithms often improve time complexity, especially for large datasets.
• What is an algorithm designed to solve?

  Specific problem or task
• What does it mean for an algorithm to be effective?

  Produces the desired output
• An example of an algorithm characteristic being demonstrated is correctness when it sorts an array to {1, 2, 3, 4, 5}
• Which algorithm characteristic allows it to handle increasing data sizes without significant performance degradation?

  Scalability
• What is the primary purpose of sorting algorithms?

  Arrange elements in order
• Divide and conquer algorithms solve subproblems independently and combine the solutions.


  True
• Binary Search is efficient for locating an element in a sorted list.


  True
• What does efficiency in an algorithm refer to?

  Minimal time and memory
• What is the primary purpose of sorting algorithms?

  Arrange elements in order
• Quicksort is an example of a divide-and-conquer sorting algorithm.
• What is Kruskal's algorithm used for in graph theory?

  Minimum spanning tree
• What does Big Theta notation describe in algorithmic analysis?

  Average-case or tight bound
• What is a key advantage of dynamic programming in algorithm design?

  Reduces redundant calculations
• An algorithm must terminate after a finite number of steps
• Match the characteristic of a good algorithm with its definition:

  Correctness ↔️ Produces expected outputs

  Efficiency ↔️ Uses minimal time and memory

  Simplicity ↔️ Easy to understand and implement

  Scalability ↔️ Handles increasing data sizes
• A recursive function for calculating factorial demonstrates the simplicity characteristic of an algorithm.


  True
• Steps to find the largest number in an array using an algorithm

  1️⃣ Initialize `maxNum` to the first element.

  2️⃣ Iterate through the array, comparing each element with `maxNum`.

  3️⃣ If an element is larger, update `maxNum`.

  4️⃣ Return `maxNum`.
• Greedy algorithms make locally optimal choices to find a global solution
• What does the Bubble Sort algorithm do to sort a list?

  Compares and swaps adjacent elements
• The characteristic of an algorithm that ensures it produces expected outputs for all valid inputs is called correctness
• An algorithm's ability to handle increasing data sizes without significant performance degradation is called scalability
• Match the algorithm type with its example use case:

  Sorting Algorithms ↔️ Ordering items in a shopping cart by price

  Searching Algorithms ↔️ Finding a user in a database

  Graph Algorithms ↔️ Finding the shortest path in a map

  Dynamic Programming Algorithms ↔️ Optimizing production schedules

  Greedy Algorithms ↔️ Making change with fewest coins
• Steps of the Breadth-First Search (BFS) algorithm:

  1️⃣ Explore all vertices at the present depth

  2️⃣ Move to vertices at the next depth level
• Big O notation represents the worst-case upper bound of an algorithm's time complexity.


  True
• Match the algorithm design pattern with its approach:

  Dynamic Programming ↔️ Breaks down complex problems into overlapping subproblems

  Divide and Conquer ↔️ Divides the problem into smaller, independent subproblems

  Greedy ↔️ Makes locally optimal choices to find a global solution
• Greedy algorithms always find the best possible solution.

  False