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
I'm a bachelor's student, and I spend most of my time coding algorithms and data structures using Java . I also teach this stuff to freshman students in my university, and I'm a top student in my class . Your project is very easy for me, ready to get It done very fast ;)