CMPS 211 Problems Ass 6, Fall 2016

Algorithm Homework and Test Problems Steven S. Skiena Department of Computer Science State University of New York Stony Brook, NY 11794-4400 skiena@cs.sunysb.edu January 29, 2006 All of the midterm and final exam problems for this semester will be drawn from this list. Thus trying to solve the problems associated with topics covered on the exam is the best possible way to study. Note that this document contains two groups of problems, one group from my personal problem list and another selected from Bill Gasarch’s problem list. Be sure to look at both sets. In particular, I promise at least one problem from Gasarch’s list on each midterm and final. 1 Mathematical Preliminaries and Analysis In this section, we should have all the problems dealing with the big oh notation, recurrence relations, logarithms, etc. 1.1 Summations 1.2 Big Oh 1. Graph the following expressions. For each expression, state for which values of n that expression is the most efficient. For the following functions: 4n2 log3 n 3n 20n 2 log2 n n2/3 (a) Graph all seven functions on a single plot. 1 (b) Partition the integers n ≥ 1 into groups such that all the integers in a group have the same function which yields the smallest values of f(n). (c) Partition the integers n ≥ 1 into groups such that all the integers in a group have the same function which yields the largest values of f(n). (d) Arrange the expressions by asymptotic growth rate from slowest to fastest. 2. Show that for any real constants a and b, b > 0, (n + a)b = Θ(nb) (*) 3. (a) Is 2n+1 = O(2n)? (b) Is 22n = O(2n)? (*) 4. For each of the following, compute how large a problem instance do you need before algorithm A is faster than algorithm B. How much time do the algorithms take on that instance? (a) Algorithm A takes n2 days to solve a problem of size n. Algorithm B takes n3 seconds on the same problem. (b) Algorithm A takes n2 days to solve a problem of size n. Algorithm B takes 2n seconds on the same problem. 5. Let P be a problem. The worst-case time complexity of P is O(n2). The worst- case time complexity of P is also Ω(n lg n). Let A be an algorithm that solves P. Which subset of the following statements are consistent with this information about the complexity of P? • A has worst-case time complexity O(n2). • A has worst-case time complexity O(n3/2). • A has worst-case time complexity O(n). • A has worst-case time complexity Θ(n2). • A has worst-case time complexity Θ(n3). 6. For each of the following pairs of functions, either f(n) is in O(g(n)), f(n) is in Ω(g(n)), or f(n) = Θ(g(n)). Determine which relationship is correct and briefly explain why. (a) f(n) = log n2; g(n) = log n + 5 (b) f(n) = √n; g(n) = log n2 2 (c) f(n) = log2 n; g(n) = log n (d) f(n) = n; g(n) = log2 n (e) f(n) = n log n + n; g(n) = log n (f) f(n) = 10; g(n) = log 10 (g) f(n) = 2n; g(n) = 10n2 (h) f(n) = 2n; g(n) = 3n (*) 7. List the functions below from the lowest to the highest order. If any two or more are of the same order, indicate which. n 2n n lg n ln n n − n3 + 7n5 lg n √n en n2 + lg n n2 2n−1 lg lg n n3 (lg n)2 n! n1+ε where 0 < ε < 1 (*) 8. List the functions below from the lowest to the highest order. If any two or more are of the same order, indicate which. √n n 2n n log n n − n3 + 7n5 n2 + log n n2 n3 log n n 1 3 + log n (log n)2 n! ln n n log n log log n ( 1 3)n ( 3 2)n 6 (*) 9. For each of the following pairs of functions f(n) and g(n), determine whether f(n) = O(g(n)), g(n) = O(f(n)), or both. (a) f(n) = (n2 − n)/2, g(n) = 6n (b) f(n) = n + 2√n, g(n) = n2 (c) f(n) = n log n, g(n) = n√n/2 (d) f(n) = n + log n, g(n) = √n (e) f(n) = 2(log n)2, g(n) = log n + 1 (f) f(n) = 4n log n + n, g(n) = (n2 − n)/2 3 10. Prove that n3 − 3n2 − n + 1 = Θ(n3). 11. Prove that (a) 2n = O(n!) (b) n! = Ω(2n) 12. For each of the following pairs of functions f(n) and g(n), give an appropriate positive constant c such that f(n) ≤ c · g(n) for all n > 1. (a) f(n) = n2 + n + 1, g(n) = 2n3 (b) f(n) = n√n + n2, g(n) = n2 (c) f(n) = n2 − n + 1, g(n) = n2/2 13. Prove that if f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then f1(n) + f2(n) = O(g1(n) + g2(n)). 14. Prove that if f1(N) = Ω(g1(n)) and f2(n) = Ω(g1(n)), then f1(n) + f2(n) = Ω(g1(n) + g2(n)). 15. Prove that if f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then f1(n) · f2(n) = O(g1(n) · g2(n)) 16. Prove or disprove. O((x + y)2) = O(x2) + O(y2) (*) 17. Show that big-O is transitive. That is, if f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)). problem 18. True or False? (a) 2n2 + 1 = O(n2) (b) √n = O(log n) (c) log n = O(√n) (d) n2(1 + √n) = O(n2 log n) (e) 3n2 + √n = O(n2) (f) √n log n = O(n) (g) log n = O(n−1/2) (*) 19. For each of the following pairs of functions f(n) and g(n), state whether f(n) = O(g(n)), f(n) = Ω(g(n)), f(n) = Θ(g(n)), or none of the above 4 (a) f(n) = n2 + 3n + 4, g(n) = 6n + 7 (b) f(n) = n√n, g(n) = n2 − n (c) f(n) = 2n − n2, g(n) = n4 + n2 (*) 20. Is f(cn) = Θ(f(n)) for all functions f and positive constants c? (Hint: Consider particularly fast-growing functions.) (*) 1.3 Recurrence Relations 1.4 Induction 1.5 Proof by Contradiction 1.6 Number Theory 1.7 Binomial Coefficients and Counting 1.8 Logarithms 1. (a) Prove that loga(xy) = loga x + loga y (b) Prove that loga xy = y loga x (c) Prove that loga x = logb x logb a (d) Prove that xlogb y = ylogb x (*) 2. Prove that that the binary representation of n ≥ 1 has ⌊lg2 n⌋ + 1 bits. 3. In one of my research papers I give a comparison-based sorting algorithm that runs in O(n log(√n)). Given the existence of an Ω(n log n) lower bound for sorting, how can this be possible? (*) 1.9 Estimation 1. Do all the books you own total at least one million pages? How many total pages are stored in your school library? 2. How many words are there in the textbook? 3. How many hours are one million seconds? How many days? Answer these questions by doing all arithmetic in your head. 5 4. Estimate how many cities and towns there are in the United States. 5. Estimate how many cubic miles of water flow out of the mouth of the Mississippi River each day? Do not look up any supplemental facts. Describe all assumptions you made in arriving at your answer. 6. A sorting algorithm takes 1 second to sort 1000 items on your local machine. How long will it take to sort 10,000 items. . . (a) if you believe that the algorithm takes time proportional to n2, and (b) if you believe that the algorithm takes time roughly proportional to n log n? 1.10 Probability 1.11 Program Analysis 1. What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using the big-Oh notation. function mystery(n) 1. r := 0 2. for i := 1 to n − 1 do 3. for j := i + 1 to n do 4. for k := 1 to j do 5. r := r + 1 6. return(r) 2. What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using big-Oh notation. function pesky(n) 1. r := 0 2. for i := 1 to n do 3. for j := 1 to i do 4. for k := j to i + j do 5. r := r + 1 6. return(r) 6 3. What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using big-Oh notation. function prestiferous(n) 1. r := 0 2. for i := 1 to n do 3. for j := 1 to i do 4. for k := j to i + j do 5. for l := 1 to i + j − k do 6. r := r + 1 7. return(r) (*) 4. What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using big-Oh notation. function conundrum(n) 1. r := 0 2. for i := 1 to n do 3. for j := i + 1 to n do 4. for k := i + j − 1 to n do 5. r := r + 1 6. return(r) (**) 1.12 Proofs of Correctness 1. (a) Prove the correctness of the following recursive algorithm for incrementing natural numbers: function increment(y) comment Return y+1 1. if y = 0 then return(1) else 2. if (y mod 2) = 1 then 3. return(2 · increment(⌊y/2⌋)) 4. else return(y + 1) (b) Analyze this algorithm. How many right-shifts does it use, i.e., how many times is line 2 executed in the worst case? 2. (a) Prove the correctness of the following recursive algorithm to multiply two natural numbers is correct, for all integer constants c ≥ 2. function multiply(y, z) 7 comment Return the product yz. 1. if z = 0 then return(0) else 2. return(multiply(cy,⌊z/c⌋) + y · (z mod c)) (b) Analyze this algorithm. How many additions does it use, i.e., how many times is line 2 executed in the worst case? 1.13 Programming Exercises 2 Data Structures 2.1 Simple Data Structures 1. For each of the four types of linked lists in the following table, what is the asymptotic worst-case running time for each dynamic-set operation listed? singly singly doubly doubly unsorted sorted unsorted sorted Search(L, k) Insert(L, x) Delete(L, x) Successor(L, x) Predecessor(L, x) Minimum(L) Maximum(L) (*) 2. A common problem for compilers and text editors is determining whether the paren- theses (or other brackets) in a string are balanced and properly nested. For example, the string ((())())() contains properly nested pairs of parentheses, which the strings )()( and ()) do not. (a) Give an algorithm that returns true if a string contains properly nested and bal- anced parentheses, and false if otherwise. Hint: At some point while scanning an illegal string from left to right will you have encountered more right parentheses than left parentheses. (b) Give an algorithm that returns the position of the first offending parenthesis if the string is not properly nested and balanced. That is, if an excess right parenthesis is found, return its position; if there are too many left parentheses, return the position of the first left parenthesis. Return -1 if the string is properly balanced and nested. 3. Write a program to reverse the direction of a given singly-linked list. In other words, after the reversal all pointers should now point backwards. 8 4. Suppose that we are given a stack of n elements which we would like to sort, by returning a stack containing the records in sorted order (with the smallest value on top). We are allowed to use only the following operations to manipulate the data: • Pop-Push(s1,s2) – pop the top item from stack s1 and push it onto stack s2. • Compare(s1,s2) – test whether the top element of stack s1 is less than the top element of stack s2. (a) Give a Θ(n2) sorting algorithm using just these operations and three stacks. (b) Give an initial stack which cannot be sorted just using these operations and two stacks. (c) Give a Θ(n2) sorting algorithm using just these operations and two stacks, where you are allowed to temporarily park elements in a constant number of additional registers. (hint: use insertion sort) (*) 5. Design a data structure that allows one to search, insert, and delete an integer X in O(1) time (ie constant time, independent of the total number of integers stored). Assume that 1 ≤ X ≤ n and that there are m + n units of space available for the symbol table, where m is the maximum number of integers that can be in the table at any one time. (Hint: use two arrays A[1..n] and B[1..m].) You are not allowed to initialize either A or B, as that would take O(m) or O(n) operations. This means the arrays are full of random garbage to begin with, so you must be very careful. (**) 2.2 Heaps 1. Devise an algorithm for finding the k smallest elements of an unsorted set of n integers in O(n + k lg n). 2. Given an array-based heap on n elements and a real number x, efficiently determine whether the kth smallest in the heap is greater than or equal to x. Your algorithm should be O(k) in the worst-case, independent of the size of the heap. Hint: you not have to find the kth smallest element; you need only determine its relationship to x. (*) 3. Give an O(n lg k)-time algorithm which merges k sorted lists with a total of n ele- ments into one sorted list. (hint: use a heap to speed up the elementary O(kn)-time algorithm). (*) 9 4. Devise a data structure that supports the following operations on an n-element set: insert in time O(lg n), and delete max in O(1) time. Note that delete max takes O(lg n) in a conventional heap. (*) 5. (a) Give an efficient algorithm to find the second-largest key among n keys. You can do better than 2n − 3 comparisons. (b) Give an efficient algorithm to find the third-largest key among n keys. How many key comparisons does you algorithm do in the worst case? Must your algorithm determine which key is largest and second-largest in the process? (*) 2.3 Union-Find 1. (a) Show a Union-Find program of size n that requires Θ(n2) time if Find without path compression and arbitrary Union are performed. (b) Show a Union-Find program of size n that requires Θ(n lg n) time if Find without path compression and size-weighted Union are performed. 2. There is well-known data structure for union and find operations that supports these operations in in worst-case time O(log n) and amortized time O(log∗ n). Design a data structure that can perform a sequence m union and find operations on a universal set of n elements, consisting of a sequence of all unions followed by a sequence of all finds, in time O(m + n). (*) 2.4 Trees and Other Dictionary Structures 1. Design a dictionary data structure in which insertions, deletions and membership queries can be all processed in O(1) time in the worst case. You may assume the set elements are integers drawn from a finite set 1, 2, .., n, and initialization can take O(n) time. 2. Describe how to modify any balanced tree data structure such that search, insert, delete, minimum, and maximum still take O(lg n) time each, but successor and pre- decessor now take O(1) time each. Which operations have to be modified to support this? (*) 3. Suppose you have access to a balanced dictionary data structure, which supports each of the operations search, insert, delete, minimum, maximum, successor, and predecessor in O(log n) time. Explain how to modify the insert and delete operations so they still take O(log n) but now minimum and maximum take O(1) time. (Hint: think in terms of using the abstract dictionary operations, instead of mucking about with pointers and the like.) 10 (*) 4. You are given the task of reading in n numbers and then printing them out in sorted order. Suppose you have access to a balanced dictionary data structure, which sup- ports each of the operations search, insert, delete, minimum, maximum, successor, and predecessor in O(log n) time. • Explain how you can use this dictionary to sort in O(n log n) time using only the following abstract operations: minimum, successor, insert, search. • Explain how you can use this dictionary to sort in O(n log n) time using only the following abstract operations: minimum, insert, delete, search. • Explain how you can use this dictionary to sort in O(n log n) time using only the following abstract operations: insert and in-order traversal. (*) 5. Given the pre-order and in-order traversals of a binary tree, is it possible to reconstruct the tree? If so, sketch an algorithm to do it. If not, give a counterexample. Repeat the problem if you are given the pre-order and post-order traversals. 6. Design a data structure to support the following operations: • insert(x,T) – Insert item x into the set T. • delete(k,T) – Delete the kth smallest element from T. • member(x,T) – Return true iff x ∈ T. All operations must take O(log n) time on an n-element set. (*) 7. In the bin-packing problem, we are given n metal objects, each weighing between zero and one kilogram. We also have a collection of large, but fragile bins. Our goal is to find the smallest number of bins that will hold the n objects, with no bin holding more than one kilogram. • The any-fit heuristic for bin packing is as follows. Take each of the objects in the order in which they are given. For each object, place it into any partially filled bin which has room. If no such bin exists, start a new bin. Design an algorithm that implements the first-fit heuristic (taking as input the n weights w1, w2, ..., wn and outputting the number of bins needed when using first-fit) in O(n log n) time. • Repeat the above using the best-fit heuristic, where we put the next object in the partially filled bin with the smallest amount of extra room after the object is inserted. 11 • Repeat the above using the worst-fit heuristic, where we put the next object in the partially filled bin with the largest amount of extra room after the object is inserted. (*) 8. Let A[1..n] be an array of real numbers. Design an algorithm to perform any sequence of the following operations: • Add(i,y) – add the value y to the ith number. • Partial-sum(i) – return the sum of the first i numbers, i.e. �n i=1 A[i]. There are no insertions or deletions; the only change is to the values of the numbers. Each operation should take O(log n) steps. You may use one additional array of size n as a work space. (*) 9. Extend the data structure of the previous problem to support insertions and deletions. Each element now has both a key and a value. An element is accessed by its key. The addition operation applied to the values, but the element are accessed by its key. The Partial sum operation is different. • Add(k,y) – add the value y to the item with key k. • Insert(k,y) – insert a new item with key k and value y. • Delete(k) – delete the item with key k. • Partial-sum(k) – return the sum of all the elements currently in the set whose key is less than y, i.e. � xj<y xi. The worst case running time should still be O(n log n) for any sequence of O(n) oper- ations. (**) 10. Suppose that we are given a sequence of n values x1, x2, ..., xn and seek to quickly answer repeated queries of the form: given i and j, find the smallest value in xi, . . ., xj. (a) Design a data structure that uses O(n2) space and answers queries in O(1) time. (b) Design a data structure that uses O(n) space and answers queries in O(log n) time. For partial credit, your data structure can use O(n lg n) space and have O(log n) query time. (*) 12 2.5 Programming Exercises 3 Sorting and Searching 3.1 Applications of Sorting 1. Newt Gingrich is given the job of partitioning 2n players into two teams of n players each. Each player has a numerical rating that measures how good he/she is at the game. Newt seeks to divide the players as unfairly as possible, so as to create the biggest possible talent imbalance between team A and team B. Show how Newt can do the job in O(n lg n) time. 2. Given two sets S1 and S2 (each of size n), and a number x, describe an O(n log n) algorithm for finding whether there exists a pair of elements, one from S1 and one from S2, that add up to x. (For partial credit, give a Θ(n2) algorithm for this problem.) 3. Given a set of S containing n real numbers, and a real number x. We seek an algorithm to determine whether there are two elements of S whose sum is exactly x. (a) Assume that S is unsorted. Give an O(n log n) algorithm for the problem. (b) Assume that S is sorted. Give an O(n) algorithm for the problem. 4. For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, S = {6, 13, 19, 3, 8}, 19 − 3 maximizes the difference, while 8 − 6 minimizes the difference. (a) Let S be an unsorted array of n integers. Give an algorithm that finds the pair x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(n) worst-case time. (b) Let S be a sorted array of n integers. Give an algorithm that finds the pair x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(1) worst-case time. (c) Let S be an unsorted array of n integers. Give an algorithm that finds the pair x, y ∈ S that minimizes |x − y|, for x ̸= y. Your algorithm must run in O(n lg n) worst-case time. (d) Let S be a sorted array of n integers. Give an algorithm that finds the pair x, y ∈ S that minimizes |x − y|, for x ̸= y. Your algorithm must run in O(n) worst-case time. 5. Give an efficient algorithm to determine whether two sets (of size m and n) are disjoint. Analyze the complexity of your algorithm in terms of m and n. Be sure to consider the case where m is substantially smaller than n. 6. Give an efficient algorithm to compute the union of sets A and B, where n = max(|A|, |B|). The output should be an array of distinct elements that form the union of the sets, such that appears more than once in the union. 13 (a) Assume that A and B are unsorted. Give an O(n log n) algorithm for the problem. (b) Assume that A and B are sorted. Give an O(n) algorithm for the problem. 7. The nuts and bolts problem is defined as follows. You are given a collection of n bolts of different widths, and n corresponding nuts. You can test whether a given nut and bolt together, from which you learn whether the nut is too large, too small, or an exact match for the bolt. The differences in size between pairs of nuts or bolts can be too small to see by eye, so you cannot rely on comparing the sizes of two nuts or two bolts directly. You are to match each bolt to each nut. (a) Give an O(n2) algorithm to solve the nuts and bolts problem. (b) Suppose that instead of matching all of the nuts and bolts, you wish to find the smallest bolt and its corresponding nut. Show that this can be done in only 2n−2 comparisons. (c) Show that any algorithm for the nuts and bolts problem must take Ω(n log n) comparisons in the worst case. (Hint: sorting n items takes Ω(n log n) comparisons in the worst case.) (*) 3.2 Quicksort 1. The running time for Quicksort depends upon both the data being sorted and the partition rule used to select the pivot. Although Quicksort is O(n log n) on average, certain partition rules cause Quicksort to take Θ(n2) time if the array is already sorted. (a) Suppose we always pick the pivot element to be the key from the last position of the subarray. On a sorted array, does Quicksort now take Θ(n), Θ(n log n), or Θ(n2)? (b) Suppose we always pick the pivot element to be the key from the middle position of the subarray. On a sorted array, does Quicksort now take Θ(n), Θ(n log n), or Θ(n2)? (c) Suppose we always pick the pivot element to be the key of the median element of the first three keys of the subarray. (The median of three keys is the middle value, so the median of 5, 3, 8 is five.) On a sorted array, does Quicksort now take Θ(n), Θ(n log n), or Θ(n2)? (d) Suppose we always pick the pivot element to be the key of the median element of the first, last, and middle elements of the subarray. On a sorted array, does Quicksort now take Θ(n), Θ(n log n), or Θ(n2)? 2. Suppose an array A consists of n elements, each of which is red, white, or blue. We seek to sort the elements so that all the reds come before all the whites, which come before all the blues The only operation permitted on the keys are • Examine(A,i) – report the color of the ith element of A. 14 • Swap(A,i,j) – swap the ith element of A with the jth element. Find a correct and efficient algorithm for red-white-blue sorting. There is a linear-time solution. (*) 3.3 Mergesort 3.4 Other Sorting Algorithm 1. An inversion of a permutation is a pair of elements which are out of order. (a) Show that a permutation of n items has at most n(n − 1)/2 inversions. Which permutation(s) have exactly n(n − 1)/2 inversions? (b) Let P be a permutation and P r be the reversal of this permutation. Show that P and P r have a total of exactly n(n − 1)/2 inversions. (c) Use the previous result to argue that the expected number of inversions in a random permutation is n(n − 1)/4. 2. Show that n positive integers in the range 1 to k can be sorted in O(n log k) time. 3. We seek to sort a sequence S of n integers with many duplications, such that the number of distinct integers in S is O(log n). (a) Give an O(n log log n) worst-case time algorithm to sort such subsequences. (b) Why doesn’t this violate the Ω(n log n) lower bound for sorting? (*) 3.5 Searching 1. Consider the numerical 20 questions game. In this game, player 1 thinks of a number in the range 1 to n. Player 2 has to figure out this number by asking the fewest number of true/false questions. Assume that nobody cheats. (a) What is an optimal strategy if n in known? (b) What is a good strategy is n is not known? 2. Let M be an n × m integer matrix in which the entries of each row are sorted in increasing order(from left to right) and the entries in each column are in increasing order (from top to bottom). Give an efficient algorithm to find the position of an integer x in M, or to determine that x is not there. How many comparisons of x with matrix entries does your algorithm use in worst case? (*) 3. Prove that a successful sequential search for a random element in an n element list performs, on average, (n + 1)/2 comparisons. 15 4. The mode of a set of numbers is the number that occurs most frequently in the set. The set (4, 6, 2, 4, 3, 1) has a mode of 4. (a) Give an efficient and correct algorithm to compute the mode of a set of n numbers. (b) Suppose we know that there is an (unknown) element that occurs n/2 + 1 times in the set. Give a worst-case linear-time algorithm to find the mode. For partial credit, your algorithm may run in expected linear time. (*) 5. Suppose you are given an input set S of n numbers, and a black box that if given any sequence of real numbers and an integer k instantly and correctly answers whether there is a subset of input sequence whose sum is exactly k. Show how to use the black box O(n) times to find a subset of S that adds up to k. (*) 3.6 Programming Exercises 4 Divide and Conquer 4.1 Binary Search 1. Suppose you are given an array A of n sorted numbers that has been circularly shifted k positions to the right. For example, {35, 42, 5, 15, 27, 29} is a sorted array that has been circularly shifted k = 2 positions, while {27, 29, 35, 42, 5, 15} has been shifted k = 4 positions. • Suppose you know what k is. Give an O(1) algorithm to find the largest number in A. • Suppose you do not know what k is. Give an O(lg n) algorithm to find the largest number in A. For partial credit, you may give an O(n) algorithm. 2. Suppose that you are given a sorted sequence of distinct integers {a1, a2, . . . , an}. Give an O(lg n) algorithm to determine whether there exists an index i such at ai = i. For example, in {−10, −3, 3, 5, 7}, a3 = 3. In {2, 3, 4, 5, 6, 7}, there is no such i. (*) 3. Given an array storing numbers ordered by value, modify the binary search routine to return the position of the first number with value x in the situation where x can appear multiple times in the array. Be sure that your algorithm is Θ(log n), that is, do not resort to sequential search once an occurrence of x is found. (*) 4. Suppose that S and T are sorted arrays, each containing n distinct elements. (a) Give an O((lg n)2) algorithm to find the nth smallest of the 2n element. 16 (b) Give a lower bound or faster algorithm for the problem. (*) 4.2 Recursive Algorithms 1. A max-min algorithm finds both the largest and smallest elements in an array of n values. Design and analyze a divide-conquer max-min algorithm that uses ⌈3n/2⌉ − 2 comparisons for any integer n. (Hint: first consider the case where n is a power of 2.) (*) 2. Give an efficient divide-and-conquer algorithm to find the kth largest element in the merge of two sorted sequences S1 and S2. The best algorithm runs in time O(log(max(m, n))), where |S1| = n and |S2| = m. (*) 3. Given an array of n real numbers, consider the problem of finding the maximum sum in any contiguous subvector of the input. For example, in the array {31, −41, 59, 26, −53, 58, 97, −93, −23, 84} the maximum is achieved by summing the third through seventh elements, where 59 + 26 + (−53) + 58 + 97 = 187. When all numbers are positive, the entire array is the answer, while when all numbers are negative, the empty array maximizes the total at 0. • Give a simple, clear, and correct Θ(n2)-time algorithm to find the maximum contiguous subvector. • Now give a Θ(n)-time dynamic programming algorithm for this problem. To get partial credit, you may instead give a correct O(n log n) divide-and-conquer algorithm. (*) 4. Let X = {x1, x3, ..., xn} be a sequence of arbitrary real numbers. Give a linear time algorithm to find the subsequence of consecutive elements xi, xi+1, ..., xj whose product is maximum over all consecutive subsequences. The product of the empty subsequence is defined as 1. Observe that X can contain reals less than 1, including negative numbers. (*) 17 4.3 Programming Exercises 5 Dynamic Programming 5.1 Greedy Algorithms 1. The natural greedy algorithm for making change of n units using the smallest number of coins is as follows. Give the customer one unit of the highest denomination coin of at most n units, say d units. Now repeat to make change of the remaining n − d units. For each of the following nations coinage, establish whether or not this greedy algorithm always minimizes the number of coins returned in change. If so, prove it, if not give a counter example. (a) United States coinage, which consists of half dollars (50 cents), quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies. (b) English coinage before the decimalization, which consisted of half-crowns (30 pence), florins(24 pence), shillings (12 pence), sixpence (6 pence), threepence (3 pence), pennies (1 pence), half pennies (1/2 pence), and farthings (1/4 pence). (c) Portuguese coinage, which includes coins for 1,2 1 2,5,10,20,25 and 50 escudos. You need only consider change for an integer number of escudos. (d) Martian coinage, where the available denominations are 1,p, p2, . . ., pk, where p > 1 and n ≥ 0 are integers. (*) 2. Consider the problem of storing n books on shelves in a library. The order of the books is fixed by the cataloging system and so cannot be rearranged. Therefore, we can speak of a book bi, where 1 ≤ i ≤ n, that has a thickness ti and height hi. T