📢 Too many exams? Don’t know which one suits you best? Book Your Free Expert 👉 call Now!


    Question

    Which of the following properties must a problem exhibit

    to be solvable by a greedy algorithm?
    A Overlapping subproblems and optimal substructure. Correct Answer Incorrect Answer
    B Greedy choice property and optimal substructure. Correct Answer Incorrect Answer
    C No backtracking and exponential time complexity. Correct Answer Incorrect Answer
    D Memoization and tabulation. Correct Answer Incorrect Answer
    E Divide and conquer and recursion. Correct Answer Incorrect Answer

    Solution

    Greedy algorithms work by making locally optimal choices at each step with the hope that these choices will lead to a globally optimal solution. This requires two properties:     1.  Greedy Choice Property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice.     2.  Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.

    Practice Next
    ask-question