Assume that I have designed an algorithm, IS(G, k), for the decision version of

Question

Assume that I have designed an algorithm, IS(G, k), for the decision version of the independent set problem. IS(G, k), implemented as a method, returns “True” if the input instance (G, k) has an independent of size at least k, and “False” otherwise.

Design an algorithm that reuses IS(G, k) to solve the optimization version of the problem - the problem of finding the maximum size of an independent set. Describe your algorithm in pseudocode, and then using the Big-O notation, give an upper bound on the number of calls to IS(G, k) your algorithm makes in the worst-case scenario.

Explanation / Answer

Let G be the given set and size be an operator such that size(G) gives the size of set G.

Pseudocode for finding maximum sized independent set of G:

Upper bound on number of calls to IS(S,k):

Since, generating all subsets of G will take O(2size(G)) time and for each subset we have to make a call to IS(S,k).

Thus, upper bound on number of calls to IS(S,k) = O(2size(G)).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.