## Exercises #### Section 2.1 1. Use Binary Search, Recursion ([Algorithm 2.1](LiB0015.html#149)) to search for the integer 120 in the following list (array) of integers. Show the actions step by step.  2. Suppose that, even unrealistically, we are to search a list of700 million items using Binary Search, Recursion ([Algorithm 2.1](LiB0015.html#149)). What is the maximum number of comparisons that this algorithm must perform before finding a given item or concluding that it is not in the list? 3. Let us assume that we always perform a successful search. That is, in [Algorithm 2.1](LiB0015.html#149) the item *x* can always be found in the list *S.* Improve [Algorithm 2.1](LiB0015.html#149) by removing all unnecessary operations. 4. Show that the worst-case time complexity for Binary Search ([Algorithm 2.1](LiB0015.html#149)) is given by  When *n* is not restricted to being a power of 2. *Hint*: First show that the recurrence equation for ***W*** (*n*) is given by  To do this, consider even and odd values of *n* separately. Then use induction to solve the recurrence equation. 5. Suppose that, in [Algorithm 2.1](LiB0015.html#149) (line 4), the splitting function is changed to *mid* = *low*:. Explain the new search strategy. Analyze the performance of this strategy and show the results using order notation. 6. Write an algorithm that searches a sorted list of *n* items by dividing it into three sublists of almost *n*/3 items. This algorithm finds the sublist that might contain the given item and divides it into three smaller sublists of almost equal size. The algorithm repeats this process until it finds the item or concludes that the item is not in the list. Analyze your algorithm and give the results using order notation. 7. Use the divide-and-conquer approach to write an algorithm that finds the largest item in a list of *n* items. Analyze your algorithm, and show the results in order notation. #### Section 2.2 1. Use Mergesort ([Algorithms 2.2](LiB0016.html#158) and [2.4](LiB0016.html#169)) to sort the following list. Show the actions step by step.  2. Give the tree of recursive calls in Exercise 8. 3. Write for the following problem a recursive algorithm whose worst-case time complexity is not worse than Θ (*n* ln *n*). Given a list of *n* distinct positive integers, partition the list into two sublists, each of size *n*/2, such that the difference between the sums of the integers in the two sublists is maximized. You may assume that *n* is a multiple of 2. 4. Write a nonrecursive algorithm for Mergesort ([Algorithms 2.2](LiB0016.html#158) and [2.4](LiB0016.html#169)). 5. Show that the recurrence equation for the worst-case time complexity for Mergesort ([Algorithms 2.2](LiB0016.html#158) and [2.4](LiB0016.html#169)) is given by  when *n* is not restricted to being a power of 2. 6. Write an algorithm that sorts a lists of *n* items by dividing it into three sublists of about *n*/3 items, sorting each sublist recursively and merging the three sorted sublists. Analyze your algorithm, and give the results under order notation. #### Section 2.3 1. Given the recurrence relation  find *T* (625). 2. Consider algorithm *solve* given below. This algorithm solves problem *P* by finding the output (solution) *O* corresponding to any input *I.* ``` void solve (input I, output& O) { if (size (I) == 1) find solution O directly; else{ partition I into 5 inputs I1, I2, I3, I4, I5, where size (Ij) = size (I)/3 for j = 1, ..., 5; for (j = 1; j < = 5; j++) solve (Ij, Oj); combine O1, O2, O3, O4, O5 to get O for P with input I; } } ``` Assume *g* (*n*) basic operations for partitioning and combining and no basic operations for an instance of size 1. 1. Write a recurrence equation *T*(*n*) for the number of basic operations needed to solve *P* when the input size is *n*. 2. What is the solution to this recurrence equation if *g*(*n*) ∊ Θ (*n*)? (Proof is not required.) 3. Assuming that *g* (*n*) = *n*2, solve the recurrence equation exactly for *n* = 27. 4. Find the general solution for *n* a power of 3. 3. Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size *n* of a problem into 10 subinstances of size *n*/3, and the dividing and combining steps take a time in Θ (*n*2). Write a recurrence equation for the running time *T* (*n*), and solve the equation for *T* (*n*). 4. Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The Towers of Hanoi problem consists of three pegs and *n* disks of different sizes. The object is to move the disks that are stacked, in decreasing order of their size, on one of the three pegs to a new peg using the third one as a temporary peg. The problem should be solved according to the following rules: (1) when a disk is moved, it must be placed on one of the three pegs; (2) only one disk may be moved at a time, and it must be the top disk on one of the pegs; and (3) a larger disk may never be placed on top of a smaller disk. 1. Show for your algorithm that *S* (*n*) = 2*n*− 1. (Here *S* (*n*) denotes the number of steps (moves), given an input of *n* disks.) 2. Prove that any other algorithm takes at least as many moves as given in part (a). 5. When a divide-and-conquer algorithm divides an instance of size *n* of a problem into subinstances each of *size* *n/c*, the recurrence relation is typically given by  where *g* (*n*) is the cost of the dividing and combining processes, and *d* is a constant. Let *n* = *ck*. 1. Show that  2. Solve the recurrence relation given that *g* (*n*) ∊ Θ (*n*). #### Section 2.4 1. Use Quicksort ([Algorithm 2.6](LiB0018.html#177)) to sort the following list. Show the actions step by step.  2. Give the tree of recursive calls in Exercise 19. 3. Show that if  then  This result is used in the discussion of the worst-case time complexity analysis of [Algorithm 2.6](LiB0018.html#177) (Quicksort). 4. Verify the following identity  This result is used in the discussion of the average-case time complexity analysis of [Algorithm 2.6](LiB0018.html#177) (Quicksort). 5. Write a nonrecursive algorithm for Quicksort ([Algorithm 2.6](LiB0018.html#177)). Analyze your algorithm, and give the results using order notation. 6. Assuming that Quicksort uses the first item in the list as the pivot item: 1. Give a list of *n* items (for example, an array of 10 integers) representing the worst-case scenario. 2. Give a list of *n* items (for example, an array of 10 integers) representing the best-case scenario. #### Section 2.5 1. Show that the number of additions performed by [Algorithm 1.4](LiB0008.html#34) (Matrix Multiplication) can be reduced to *n*3− *n*2 after a slight modification of this algorithm. 2. In Example 2.4, we gave Strassen's product of two 2 × 2 matrices. Verify the correctness of this product. 3. How many multiplications would be performed in finding the product of two 64 × 64 matrices using the standard algorithm? 4. How many multiplications would be performed in finding the product of two 64 × 64 matrices using Strassen's method ([Algorithm 2.8](LiB0019.html#201))? 5. Write a recurrence equation for the modified Strassen's algorithm developed by Shmuel Winograd that uses 15 additions/subtractions instead of 18. Solve the recurrence equation, and verify your answer using the time complexity shown at the end of [Section 2.5](#ch02lev3sec5). #### Section 2.6 1. Use [Algorithm 2.10](LiB0020.html#218) (Large Integer Multiplication 2) to find the product of 1253 and 23,103. 2. How many multiplications are needed to find the product of the two integers in Exercise 30? 3. Write algorithms that perform the operations *u* × 10*m*; *u* divide 10*m*; *u* rem 10*m*, where *u* represents a large integer, *m* is a nonnegative integer, divide returns the quotient in integer division, and rem returns the remainder. Analyze your algorithms, and show that these operations can be done in linear time. 4. Modify [Algorithm 2.9](LiB0020.html#214) (Large Integer Multiplication) so that it divides each *n*-digit integer into 1. three smaller integers of *n*/3 digits (you may assume that *n* = 3*k*). 2. four smaller integers of *n*/4 digits (you may assume that *n* = 4*k*). Analyze your algorithms, and show their time complexities in order notation. #### Section 2.7 1. Implement both Exchange Sort and Quicksort algorithms on your computer to sort a list of *n* elements. Find the lower bound for *n* that justifies application of the Quicksort algorithm with its overhead. 2. Implement both the standard algorithm and Strassen's algorithm on your computer to multiply two *n* × *n* matrices (*n* = 2*k*). Find the lower bound for *n* that justifies application of Strassen's algorithm with its overhead. 3. Suppose that on a particular computer it takes 12*n*2μs to decompose and recombine an instance of size *n* in the case of [Algorithm 2.8](LiB0019.html#201) (Strassen). Note that this time includes the time it takes to do all the additions and subtractions. If it takes *n*3μs to multiply two *n* × *n* matrices using the standard algorithm, determine thresholds at which we should call the standard algorithm instead of dividing the instance further. Is there a unique optimal threshold? #### Section 2.8 1. Use the divide-and-conquer approach to write a recursive algorithm that computes *n*!. Define the input size (see Exercise 34 in [Chapter 1](LiB0008.html#16)), and answer the following questions. Does your function have an exponential time complexity? Does this violate the statement of case 1 given in [Section 2.8](#ch02lev3sec8) 2. Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size *n* of a problem into *n* subinstances of size *n*/3, and the dividing and combining steps take linear time. Write a recurrence equation for the running time *T* (*n*), and solve this recurrence equation for *T* (*n*). Show your solution in order notation. ### Additional Exercises 1. Write an efficient algorithm that searches for a value in an *n* × *m* table (two-dimensional array). This table is sorted along the rows and columns—that is,  2. Suppose that there are *n* = 2*k* teams in an elimination tournament, in which there are *n*/2 games in the first round, with the *n*/2 = 2*k*−1 winners playing in the second round, and so on. 1. Develop a recurrence equation for the number of rounds in the tournament. 2. (b) How many rounds are there in the tournament when there are 64 teams? 3. Solve the recurrence equation of part (a). 3. Write a recursive Θ (*n* lg *n*) algorithm whose parameters are three integers *x*, *n*, and *p,* and which computes the remainder when *xn* is divided by *p.* For simplicity, you may assume that *n* is a power of 2—that is, that *n* = 2*k* for some positive integer *k.* 4. Use the divide-and-conquer approach to write a recursive algorithm that finds the maximum sum in any contiguous sublist of a given list of *n* real values. Analyze your algorithm, and show the results in order notation.