Homework 1

Reading assignment

Please read chapter 1 (Introduction) and chapter 2 (Growth of Functions). Please also look over chapter 3 (Summations) and sections 4.1 and 4.2 of chapter 4 (Recurrences).

Written assignment (assigned September 26, due October 3)

1. Do exercise 1.2-1 on page 10. (5 points)
   Optional exercises: 1.1-2 and 1.1-3 on pages 5-6.
   (Do the optional problems and hand them in if you had any trouble with exercise 1.2-1.)

2. Do exercise 1.3-5 on page 15. (5 points)

3. Do exercise 1.4-2 on page 17. (5 points)
   Hint: you may want a computer to do the job for you.

4. Do problem 1-1 page 17. (10 points)
   Hint: same as for problem 3.

5. Assume T is the maximum amount of time you can run your programs on a given computer (perhaps you are charged by the hour, and this is how much time you can buy). You have eight different programs, whose running times are those specified in problem 4 (lg n, sqrt(n), n, n lg n, etc.).
   You are given the good news that the provider obtained a computer that is 10 times faster than the model they had before. For each of the running times, if the size of the largest program that you could run in time T on the "old" machine was N, determine the size of the largest program you can run now (as a function of N). (5 points)

6. Do problem 2-1 part (a) on page 38. (5 points)

7. Do problem 2-4 part (a) on page 39. (5 points)

8. Write an algorithm in pseudocode that outputs the index of the first term of a finite sequence of positive integers that is less than the immediately preceding term of the sequence. If the terms of the sequence are in increasing order, the algorithm should output 0. Analyze the worst-case time complexity of this algorithm. (5 points)

9. Analyze the average-case performance of the linear search algorithm:
   • if exactly half the time the element key is in the first position and exactly half the time it is in the last position;
   • if the element key is always in the list and is equally likely to be in any position;
   • if exactly half the time the element key is not in the list and if key is in the list it is equally likely to be in any position;
   • if exactly half the time the element key is not in the list and exactly half the time it is in the first position;
   • if 99% of the time the element key is in the first position and 1% of the time it is not in list.
   (This problem is worth 5 points.)