Assignement

1. For each of the following functions f find a simple function g such that f(n) =Θ(g(n)). (a) f1(n) = (1000)2n + 4n. (b) f2(n) = n + n log n +√n. (c) f3(n) = log(n20) + (logn)10. (d) f4(n) = (0.99)n + n100. 3. The set cover problem is as follows: given a set S of subsets S1, ..., Sm of the universal set U={1, ..., n}, find the smallest subset of subsets T ⊂ S such that ∪ti∈T ti = U. For example, there are the following subsets, S1 = {1, 3, 5}, S2 ={2, 4}, S3 = {1, 4}, and S4 = {2, 5} The set cover would then be S1 and S2. Find a counterexample for the following algorithm based on greedy strategy: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered. need within 2-3 hour. Thanks