1: Are the following true or false: 1. 2n = O(1.1n n100). 2. 3n = O(2n + 4n). 3. n2 = ( n 2 4. 1 +1 2 5 . ),n ). n 22 j=1 j + .1. . + 2 = O(1). 2n = (n4). Problem 2: Find the best estimate that you can for the complicated functions defined below, in terms of simpler functions: 1. f (n) = 1 + 2 + 3 + . . . + n2. 2. f (n) = n2 + 7n + 10 for n 0. 3. f (n) = log 1 + log 2 + log 3 + . . . + log n2. 4. f (n) = n1/2 + n5/4 + n2 100 + 1 . 2 n Problem 3: Consider recurrence fn defined as follows: f0 = 0, f1 = 1, f2 = 7 and fn = 3fn1 + fn2 + fn3 for n 3. Write an algorithm to output fn, given n. What is the running time of your algorithm? Problem 4: What is the running time of the algorithm to add two n n matrices, as a function of n? Problem 5: What is the running time of the algorithm to compute the product AB of two n n matrices A, B, as a function of n? Problem 6: A set S of strings over the alphabet {0, 1} is recursively defined as follows: S (where is the empty string), and if x S then 0x1 S, and 1x0 S. Is the string 01010101 in S? Is the string 11001 in S? Problem 7: Obtain a closed form formula for fn where the sequence fn is defined by the following recurrence relation: f0 = 5, f1 = 3, fn = 2fn1 + 3fn2 for n 2. Problem 8:relation: Obtain a fclosed form formula for fn, where the sequence fn is defined by the recurrence 0 = 1, f1 = 3, fn = 6fn1 9fn2 for n 2. Problem 9: Problem 10: Prove by using mathematical induction that 3n 2n + n2 for all n 1. Evaluate the following : 1. 100! mod 71. 2. 10! mod 11. 3. (2131 + 3121) mod 9. Problem 11: Compute the gcd of the numbers 39 and 91 by using the Extended Euclidean Algorithm. Also express the gcd as a linear combination of 39 and 91. Problem 12: Find the prime factorization of 924. What is the number of divisors of 924? Problem 13: What is the number of ways one can arrange 7 red balls, 5 green balls, and 5 yellow balls in a row? 1 Problem 14: 7 couples (each couple is a pair : husband & wife) arrive at a theater and are seated in a row with 14 seats. What is the total number of ways of seating them if everyone must sit next to their spouse? What is the total number of seatings possible if every lady and gentleman wants to make sure that their spouse does not sit near a member of the opposite sex, other than themselves? Problem 15: Suppose there is an urn contain 10 red balls and 15 green balls. I choose a ball at random from the urn, followed by another ball from the urn at random. Let E1 be the event that the first ball is red and E2 the event that the second ball is green. Are E1, E2 independent? Problem 16: Urn 1 contains 10 red balls, 15 green balls and 16 yellow balls. Urn 2 contains 5 red balls and 2 green balls. I choose a ball at random from Urn 1 and put it into ball 2. Then I choose a ball at random from Urn 2. What is the probability that the ball is red? Problem 17: n men go to a party and leave their hats with the butler. When they leave the party, one-by-one, the butler hands out to each man, a randomly chosen hat from the remaining collection of hats. What is the expected number of men who got their original hat? Problem 18: Urn 1 contains 10 red balls, 15 green balls and 16 yellow balls. Urn 2 contains 5 red balls and 2 green balls. I choose a ball at random from Urn 1 and put it into Urn 2. Then I choose a ball at random from Urn 2. 1. If the (second chosen) ball is red, what is the probability that I chose a yellow ball from Urn 1? 2. If the (second chosen) ball is yellow, what is the probability that I chose a red ball from Urn 1? Problem 19: What is the number of functions possible where the domain is a set of size n and the co-domain is a set of size m? Problem 20: A random function f : A B where |A| = n and |B| = m is a function where for each element of the domain A we define its image as an element of the co-domain B chosen uniformly at random from B. What is the expected size of the range of a random function? Problem 21: Suppose there is a group of 10 boys and 12 girls. You choose a group of people using a random procedure as follows. For every person you toss a fair coin - if it turns up head you include that person, otherwise you do not include him or her. 1. What is the probability that you choose a group of size 6? 2. What is the probability that you choose 5 boys and 6 girls in the group? 3. What is the expected number of people in the group? 4. What is the expected number of boy, girl pairs in the group