Analysis of Algorithm Review

Which statement is true about differences between Best and Worst case analysis

• Best case represents the lower bound of time/resource,
  Worst case represents the upper bound of time/resource.

• Best case measures the maximum resources required,

  Worst case measures the minimum.

• Best case happens when the input is well-ordered
  Worst case happens when the input is reversely-ordered

• Best case is for small datasets, Worst case is for large datasets.

Which is true about Average-Case analysis

• The arithmetic mean of Best case and Worst case time

• The expected time/resource used by algorithm.

• The time used by algorithm when the input is randomly ordered.

• The time used by algorithm when the input size is a half of maximum limit.

What is asymptotic notation

• The notation used to describe the growth rate of algorithms

• The greek alphabet used to compare the function value

• The metric to measure the time used to run the program

• A syntax used in high-level programming languages to declare the maximum memory limit of a variable

Which one is NOT methods used to solve recurrence equations.

• Replace and Substitution

• Master Theorem

• State Space Tree

• Linear recurrence relation theorem

What are the three standard steps involved in the Divide and Conquer algorithmic strategy?

• Divide and Conquer the input by splitting it into halves.

  Iterate through the list to find the largest value.

  Return the result.

• Divide the total execution time.

  Conquer the subproblems by solving them one by one.

  Delete the unnecessary data.

• Divide the problem into smaller parts.

  Conquer the hardware by optimizing memory.

  Merge the final code.

• Divide the problem into subproblems.

  Conquer them by solving recursively.

  Combine the solutions to the subproblems.

Which properties of the problem required for Dynamic Programming.

• Optimal Substructure

• Overlapping subproblem

• Non-overlapping subproblem

• Greedy choice

How does Dynamic Programming optimize the process of solving complex recursive problems.

• It uses a Dynamic flow that changes the algorithm's logic to adapt to new inputs.

• Simplifies the problem by using a recursive strategy that solves every sub-instance when it is encountered.

• Storing the results of smaller subproblems in a table or array to avoid re-calculating

• Convert the recursive execution into filling the value in the table using loops

What is the longest common subsequence of the number sequence S and its ascendingly sorted sequence S'.

• Longest increasing subsequence of S

• Edit distance from S to S'

• Longest decreasing subsequence of S

• Longest Palindromic Subsequence of S

Which statement is FALSE about Greedy choice property

• Choosing the best option at the time on each decision.

• The logic of choice can be reconsidered as steps go on

• Involving sorting the values of resource to find the best option.

• May not guarantee the globally optimal result.

What is the greedy choice for Fractional Knapsack

• The highest value item

• The lowest weight item

• The highest value-to-weight ratio

• The highest weight-to-value ratio