Quiz 5 - Backtracking and Greedy Algorithms

Question 1

What makes the solution for the ‘Activity Selection Problem’ that we implemented in the exploration, a greedy approach?

• It has optimal substructure
• It is similar to Dynamic Programming algorithm
• We make a best available choice in each iteration and we never look back
• It satisfies greedy property

Answer 1

• We make a best available choice in each iteration and we never look back

Question 2

Pick the statements which are True.

1. Greedy algorithms are efficient compared to dynamic programming algorithms
   Correct!
2. A greedy algorithm is hard to design sometimes as it is difficult to find the best greedy approach
3. Greedy algorithms would always return an optimal solution
   Correct!
4. Dynamic programming technique would always return an optimal solution

Answer 2

1, 2, 4

Question 3

All possible greedy algorithms, at each step, choose what they know is going to lead to an optimal/near optimal solution.

T/F

Answer 3

True

Question 4

Can 0/1 knapsack problem be solved using the Greedy algorithm technique to obtain an optimum solution to fill the knapsack?

0/1 knapsack problem (This is the problem that we saw in the previous modules) When have n items and their values given. We are provided with a knapsack of capacity X. We have only one copy of each item. We need to maximize the value of our knapsack with items that we pick.

T/F

Answer 4

False

Question 5

Fill in the below pseudocode for activity selection problem using the greedy approach. The function returns the count of the maximum number of activities that can be selected.

activitySelection(activities):

sortBasedonEndTime(activities) # uses quick sort to sort the activities

for activity in activities:

if currendEndTime <= activity.startTime:

[ Select ]

[ Select ]

return result

Time complexity for the pseudocode will be
[ Select ]

Answer 5

result = result + 1

currentEndTime = activity.endTime

O(n^2)

Question 6

The asymptotic runtime of the solution for the combination sum problem that was discussed in the exploration is ____________.
* Linear
* N Factorial
* Exponential
* Logarithmic

Answer 6

• Exponential