a. Design a non-recursive algorithm for computing an (discussed in the class). What is the basic operation? How many times is the algorithm's basic operation executed? b. Using an = a*an-1 (discussed in the class) to design a recursive algorithm for computing an . What is the basic operation? Set up and solve a recurrence relation for the number of times that algorithm's basic operation is executed. c. Using an = a*(a(n-1)/2) 2 (n is odd integer) and an = a*(an/2) 2 (n is even integer) (discussed in the class) to design a recursive algorithm for computing an . What is the basic operation? Set up and solve a recurrence relation for the number of times that algorithm's basic operation is executed.

1. (a) Prove or give a counter example: If A UB = AUG, then B = C. (b) Simplify AU( BU ((AU B) nC)) using basic set operations. Do not use Venn diagrams (except, perhaps, to check your result)! (c) Let A, B, C, and D be subsets of S. Using set operations (C, 3,0, U,"), express the situation that two or fewer (e.g., exactly two, exactly one, or exactly none) of (A, B, C, D) occur. You can use Venn diagrams to help visualize the problem, but your answer must be expressed using set operations (e.g., An B).Problem 1 The symbol - is a set operation (like U and (). For any two subsets A, B of a universal set 12, the set A - B is defined as A-B := AnB = {All r ( A such that x ( B } As special cases, ? - A is the same set as A', and A - A is the same set as O. (Clicker Question 17 is about the set An B'. It may be worth reviewing that question.) (a) Draw a Venn Diagram for the sets A and B (assuming they partly overlap each other), and indicate the three regions corresponding to the three sets A-B, An B and B-A. (b) Is A - B always a subset of A? State the reason. (c) By using De Morgan's Law, what is the complement of A - B? Express the result by using A, B and the three basic set operations U, A and'. (d) If 2 is the sample space of a random experiment, and A and B are events, we would interpret An B as the event that A and B both occur. Interpret the event A - B in a similar way, and prove that P(A - B) = P(A) - P(AnB).7.) Consider the set of Natural Numbers and the set of Rational Numbers. Which one is not dense? Prove that it is not dense. 8.) Consider the set of Integers. Categorize the integers as closed or not closed for each of the four basic operations, addition, subtraction, multiplication, and division. Show proof for any operation where the set is not closed