## Exercises #### Section 1.1 1. Write an algorithm that finds the largest number in a list (an array) of *n* numbers. 2. Write an algorithm that finds the *m* smallest numbers in a list of *n* numbers. 3. Write an algorithm that prints out all the subsets of three elements of a set of *n* elements. The elements of this set are stored in a list that is the input to the algorithm. 4. Write an Insertion Sort algorithm (Insertion Sort is discussed in [Section 7.2](LiB0053.html#633)) that uses Binary Search to find the position where the next insertion should take place. 5. Write an algorithm that finds the greatest common divisor of two integers. 6. Write an algorithm that finds both the smallest and largest numbers in a list of *n* numbers. Try to find a method that does at most 1.5*n* comparisons of array items. 7. Write an algorithm that determines whether or not an almost complete binary tree is a heap. #### Section 1.2 1. Under what eircumstances, when a searching operation is needed, would sequential Search ([Algorithm 1.1](LiB0008.html#27)) not be appropriate? 2. Give a practical example in which you would not use Exchange Sort ([Algorithm 1.3](LiB0008.html#32)) to do a sorting task. #### Section 1.3 1. Define basic operations for your algorithms in Exercises 1–7, and study the performance of these algorithm has an every-case time complexity, determine the worst-case time complexity. 2. Determine the worst-case, average-case, and best-case time complexities for the basic Insertion Sort and for the version given in Exercise 4, which uses Binary Search. 3. Write a Θ(*n*) algorithm that sorts *n* distinct integers, ranging in size between 1 and *kn* inclusive, where *k* is a constant positive integer. (Hint: Use a *kn*-element array.) 4. Algorithm A performs 10*n*2 basic operations, and algorithm B performs 300 ln *n* basic operations. For what value of *n* does algorithm B start to show its better performance? 5. There are two algorithms called Alg1 and Alg2 for a problem of size *n.* Alg1 runs in *n*2 microseconds and Alg2 runs in 100*n* log *n* microseconds. Alg1 can be implemented using 4 hours of programmer time and needs 2 minutes of CPU time. On the other hand, Alg2 require 15 hours of programmer time and 6 minutes of CPU time. If programmers are paid 20 dollars per hour and CPU time costs 50 dollars per minute, how many times must a problem instance of size 500 be solved using Alg2 in order to justify its development cost? #### Section 1.4 1. Show directly that *f*(*n*) = *n*2 + 3*n*3∊ Θ(*n*3). That is, use the definitions of *O* and Ω to show that *f*(*n*) is in both *O*(*n*3) and Ω (*n*3). 2. Using the definitions of *O* and Ω, show that  3. Using the Properties of Order in [Section 1.4.2](LiB0011.html#85), show that  4. Let *p*(*n*) = *a**k**n**k* + *a**k*-1*n**k*-1 + … + *a*1*n* + *a*0, where *a**k* > O. Using the Properties or order in [Section 1.4.2](LiB0011.html#85), show that *p*(*n*) ∊ Θ(*n**k*). 5. Group the following function by complexity category.  6. Establish Properties 1,2,6, and 7 of the Properties of Order in [Section 1.4.2](LiB0011.html#85) 7. Discuss the reflexive, symmetric, and transitive properties for asymptotic comparisons (*O*, Ω, Θ, *o*). 8. Suppose you have a computer that requires 1 minute to solve problem instances of size *n* = 1,000. Suppose you buy a new computer that runs 1,000 times faster than the old one. What instance sizes can be run in 1 minute, assuming the following time complexities *T*(*n*) for our algorithm? 1. *T*(*n*) = *n* 2. *T*(*n*) = *n*3 3. *T*(*n*) = 10*n* 9. Derive the proof of [Theorem 1.3](LiB0011.html#120). 10. Show the correctness of the following statements. 1. lg *n* ∊ *O* (*n*) 2. *n* ∊ *O* (*n* lg *n*) 3. *n* lg *n* ∊ *O* (*n*2) 4. 2*n*∊ Ω (5In *n* 5. lg3*n* ∊ *o* (*n*0.5) ### Additional Exercises 1. Presently we can solve problem instances of size 100 in 1 minute using algorithm A, which is a Θ(2*n*) algorithm. On the other hand, we will soon have to solve problem instances twice this large in 1minute. Do you think it would help to buy a faster (and more expensive) computer? 2. What is the time complexity *T*(*n*) of the nested loops below? For simplicity, you may assume that *n* is a power of 2. That is, *n* = 2*k* for some positive integer *k.* ``` : for (i = 1; i = n; i++){ j = n; while (j > = 1){ < body of the while loop > //Needs Θ (1). j = [j/2]; } } : ``` 3. Give an algorithm for the following problem and determine its time complexity. 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. What is the time complexity *T*(*n*) of the nested loops below? For simplicity, you may assume that *n* is a power of 2. That is, *n* = 2*k* for some positive integer *k.* ``` i = n; while (i >= 1){ j = i; while (j >= n){ < body of the while loop> //Needs Θ (1). j = 2 * j; } i =[i/2]; } ``` 5. Give a Θ (*n*lg *n*) algorithm that computes the reminder when *x**n* is divided by *p.* For simplicity, you may assume that *n* is a power of 2. That is, *n* = 2*k* for some positive integer *k.* 6. Explain in English what functions are in following sets. 1. *n**O*(1) 2. *O*(*n**O*(1)) 3. *O* (*O*(*n**O*(1))) 7. Show that the function *f*(*n*) = |*n*2 sin *n*| is in neither *O*(*n*) nor Ω (*n*). 8. Justify the correctness of the following statements assuming that *f*(*n*) and *g*(*n*) are asymptotically positive functions. 1. *f*(*n*) + *g*(*n*) ∊ *O* (*f*(*n*)), *g*(*n*)) 2. *f*2(*n*) ∊ Ω(*f*(*n*)) 3. *f*(*n*) + *o*(*f*(*n*)) ∊ Θ(*f*(*n*), where of *o*(*f*(*n*)) means any function *g*(*n*) ∊ *o*(*f*(*n*)) 9. Give an algorithm for the following problem, 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 integers in the two sublists is minimized. Determine the time complexity of your algorithm. You may assume that *n* is a multiple of 2 10. [Algorithm 1.7](LiB0009.html#51) (*n*th Fibonacci Term, Iterative) is clearly linear in *n*, but is it a linear-time algorithm? In [Section 1.3.1](LiB0010.html#58) we defined the input size as the size of the input. In the case of the *n*th Fibonacci term, *n* is the input, and the number of bits it takes to encode *n* could be used as the input size. Using the measure, the size of 64 is lg 64 = 6, and the size of 1,024 is lg 1,024 = 10. Show that [Algorithm 1.7](LiB0009.html#51) is exponential-time in terms of its input size. Show further that any algorithm for computing the *n*th Finonacci term must be an exponential-time algorithm because the size of the output is exponential in the input size. (See [Section 9.2](LiB0075.html#887) for a related discussion of the input size.) 11. Determine the time complexity of [Algorithm 1.6](LiB0009.html#45) (*n*th Fibonacci Term, Recursive) in terms of its input size (see Exercise 34). 12. Can you verify the correctness of your algorithms for Exercises 1 to 7?