4. Consider the following recursive algorithm. ALGORITHM Q(n) //Input: A positive integer if n = 1 return 1 else return Q(n-1) + 2 *n-1/nb. Set up a recurrence relation for the number of multiplications made by this algorithm and solve it. c. Set up a recurrence relation for the number of additions/subtractions made by this algorithm and solve it./n9. Consider the following recursive algorithm. ALGORITHM Riddle(A[0..n-1]) //Input: An array A[0..n-1] of real numbers if n = 1 return A[0] else temp← Riddle(A[0..n -2]) if temp ≤ A[n 1] return temp else return A[n - 1] a. What does this algorithm compute? b. Set up a recurrence relation for the algorithm's basic operation count and solve it.

1. Compute the following sums. a. 1+3+5+7+ +999 b. 2+4+8+16+...+1024 c Σ+1 d. Σ"}; 1. Σ–13+1g. Σ Σ - e Σ"di( + 1) Ξ 2. Find the order of growth of the following sums. Use the Θ(g(n)) notation with the simplest function g(n) possible. a. Σ"=(2+1)2 € Σ=1 + 1)2-1 b. Σ={1gi2 d. Σ. Σ( + 3)/n4. Consider the following algorithm. ALGORITHM Mystery (n) //Input: A nonnegative integer n S←0 for i ← 1 to n do S+S+i*i return S a. What does this algorithm compute? b. What is its basic operation? c. How many times is the basic operation executed? d. What is the efficiency class of this algorithm? e. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.

5. Consider the following algorithm. ALGORITHM Secret(A[0..n-1]) //Input: An array A[0..n-1] of n real numbers minval A[0]; maxval ← A[0] for i 1 to n - 1 do if A[i] < minval minval ← A[i] if A[i]> maxval maxval ← A[i] return maxval - minval Answer questions (a)-(e) of Problem 4 about this algorithm./n4. Consider the following algorithm. ALGORITHM Mystery (n) //Input: A nonnegative integer n S 0 for i ← 1 to n do S+S+i*i return S a. What does this algorithm compute? b. What is its basic operation? c. How many times is the basic operation executed? d. What is the efficiency class of this algorithm? e. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.

3. Consider the following recursive algorithm, where array is an array of integers. You can assume that the length of array is a power of two, so len(array) is n = 2m for some m ≥ 0. (a) (1 marks) How many array accesses are made in total by calling squoogle (array)? An array access means that you evaulate array[i] for some i. Write your answer as a recursive formula in terms of m. You can treat the arguments to the recursive calls as if they do not require array accesses to compute. (b) (2 marks) Give a closed-form expression for your formula from part a) in terms of m. Prove your answer is correct using induction. (c) (0.5 marks) What is your closed-form expression from part b) in terms of n, the number of elements in the array?

2. Suppose you have a row of n + 1 lilypads, and Fred wants to jump on every one of them exactly once. At each jump, he is able to jump one lilypad forward, one lilypad backwards, or two lilypads forward (skipping one). Let f(n) denote the number of ways Fred can jump on each of the n + 1 lilypads, starting at the first lilypad and ending at the n+1th lilypad. (a) (0.5 marks) What are the first six terms in this sequence, starting with f(0)? (b) (2 marks) Give a recursive formula for f(n). Briefly justify why your formula is correct. What is another name for this sequence?

Exercise 4: 10 Consider the partition problem: given n positive integers, partition them into two disjoint subsets with the same sum of their elements. (Of course, the problem does not always have a/nsolution.) Design an exhaustive-search algorithm for this problem. Try to minil number of subsets the algorithm needs to generate.

Let A[1 .. n] be an array of n distinct numbers. If i<j and A[i]>A[j], then the pair (i, j) is called an inversion of A. 6a) List the five inversions of the array <2, 3, 8, 6, 1>. 6b) What array with elements from the set {1, 2,..., n} has the most inversions? How many does it have? 6c) What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer. 6d) Give an algorithm that determines the number of inversions in any permutation on n elements in O(n lg n) worst-case time. (Hint: Modify merge sort.)

# Project 3: Griefer list ## Introduction Your job working at the MMORPG is going great. After a recent promotion, you've been assigned a more challenging task. The game has become popular enough to attract large numbers of griefers, which use trial accounts to troll and harass your paying customers. Given that the rules are different on different servers, each server maintains its own ban list. To help server admins out, you want to build a tool that lets them quickly lookup whether a player has been banned and when the most recent ban was. You already have a tool that concatenates all the banlists together and consists of lines with the following format: [USERNAME] [SERVERID] [UNIX_TIME_OF_BAN] Example line: bmrlpmyzybrb 819 1636184756 (the trolls seem to like to use randomly generated names) Your tool will read a single input file consisting of a number of lines like the one above, and will insert the players into a self-balancing tree data structure, organized by user name. Along with the above data (which is stored in a file), your tool will also read a list of names from standard input. For each name, it will print a prepared statement (see sample) that contains the name, the number of servers they've been banned on, and the most recent ban they received. You know that a tree is appropriate for this task as there might be duplicate data, and you want to be able to find spans of names in sorted order later. However, you aren't sure which tree to use. You know that given the large number of inserts into the data structure that a scapegoat tree would be appropriate. However, you want to compare it with at least one of these trees: * AVL tree * Red black tree * B-tree

3. Consider the following recursive algorithm, where array is an array of integers. You can assume that the length of array is a power of two, so len(array) is n = 2m for some m ≥ 0. (a) (1 marks) How many array accesses are made in total by calling squoogle (array)? An array access means that you evaulate array[i] for some i. Write your answer as a recursive formula in terms of m. You can treat the arguments to the recursive calls as if they do not require array accesses to compute. (b) (2 marks) Give a closed-form expression for your formula from part a) in terms of m. Prove your answer is correct using induction. (c) (0.5 marks) What is your closed-form expression from part b) in terms of n, the number of elements in the array?

3. Recall that as we discussed in class, there is no known fast algorithm for graph isomorphism, and it is believed that no such algorithm exists. However, it is often possible to solve graph isomorphism quickly if there are restrictions on the types of graphs allowed as input. Your best friend Fred has a proposal for an alternative graph isomorphism algorithm when the input graphs are restricted to be trees. He suggests the following: 1) For each vertex v in G₁, compute deg(v) and append this value to a list L₁. 2) For each vertex v in G₂, compute deg(v) and append this value to a list L2. 3) Sort the lists L₁ and L2 in increasing order. 4) If L₁ and L₂ are the same, reutrn "yes", otherwise return "no”. Does Fred's algorithm work on all possible inputs? You can assume the input graphs are both trees. Prove your answer is correct.