3. (20 points) Random Zoo. A zookeeper has a problem: she does not know if a given animal is a bird or not'. You try to solve her problem by providing her with two different randomized algorithms. (a) (5 points) The first randomized algorithm BirdTest1 takes as input a photograph of the animal then outputs 1 if the photograph depicts a bird and 0 otherwise. If the animal is indeed a bird then the algorithm is always correct (will always output 1) However, if the animal is not a bird then it answers correctly (outputs 0) only with probability at least 1-1. The algorithm runs in (worst-case) time O(lg n). Describe how you would modify this algorithm to make the probability of correctness at least 1-110. State the running time (in O-notation) of this modified algorithm. (b) (5 points) The second randomized algorithm BirdTest2 also takes as input a photo- graph but would always outputs the correct answer. However, the running time is defined as follows: 10n with probability 1/5 T(n)n with probability 1 ( with probability 1-1-1/5 Compute the erpected running time of BirdTest2 and write your answer in O-notation (c) You decided to combine both randomized algorithms in an attempt to gain the speed of the original BirdTest1 while maintaining the correctness using BirdTest2. The following is the new algorithm: BirdTestCombined (photo) flip a fair coin; if heads return BirdTest1(photo); else return BirdTest2(photo); (i) (5 points) Compute the error of BirdTestCombined (i) (5 points) Compute the expected running time of BirdTestCombined and write your answer using O-notation