UML CS Analysis of Algorithms 91.404 Spring, 2001
Homework Set #1 & SOLUTIONS
Prepared by TA Wenhua (Michelle) Shi
Assigned: Friday, 2/2 Due: Friday, 2/9 (start of lecture)
This assignment covers textbook material in Chapters12.
Note: Partial credit for wrong answers is only given if work is shown.

(10 points) Let R be a problem. Suppose that the worstcase asymptotic time complexity of R is in O(n^{2}) and also in (n lg n). Now, let A be an algorithm that solves R. Which of the following statements about A are consistent with this information about the asymptotic time complexity of R? (Note: The answer might include more than one of the choices.)
A has worstcase time complexity O(n^{2}).
A has worstcase time complexity O(n^{3/2}).
A has worstcase time complexity O(n).
A has worstcase time complexity ( n^{2}).
A has worstcase time complexity ( n^{3}).
Answer: Statements 1, 2, 4 and 5 are consistent.
Note: For probem R, O(n^{2}) can be tight or loose upper bound and (n lg n) can be tight or loose lower bound. An algorithm that solves R can be so efficient that it achieves its complexity as the same as the problem ( but can not be smaller), or it can be so inefficient that it is much more complex (say, exponential) than the problem.

(10 points) For (a) and (b), answer yes or no and briefly explain.
(a) If I prove that an algorithm takes O(n^{2}) worstcase time, is it possible that it takes O(n) time on some inputs?
Answer: Yes. Note that O(n^{2}) worstcase time is an upper bound and we have not given a lower bound limit. Because (n) is smaller than (n^{2}), it is possible that an algorithm satisfies both O(n^{2}) worstcase time and O(n) time on some inputs.
(b) If I prove that an algorithm takes (n) bestcase time, is it possible that it takes (n lg n) time on all inputs?
Answer: Yes. Note that (n) bestcase time can be a loose lower bound. If an algorithm takes (n lg n) time on all inputs, it is absolutely right that it is larger than (n).

(20 points) Rank the following 5 functions by order of asymptotic growth. That is, find an arrangement g_{1}, g_{2}, g_{3}, g_{4}, g_{5}_{ }of the functions satisfying
g_{1} = ( g_{2 }), g_{2} = ( g_{3 }), ..., g_{4} = ( g_{5 }). Justify your answer mathematically.
^{ }6n^{4 }+ 5n^{3 }2^{n }+ 3n ^{ }6n^{ }(lg^{2} n) (1/4)^{n} 999log n + 65,000
Answer: (1/4)^{n} < 999log n + 65,000 < 6n^{ }(lg^{2} n) < 6n^{4 }+ 5n^{3 } < 2^{n }+ 3n
Justification: let’s ignore all coefficients and minor parts, since
(1/4)^{n} = (1/4)^{n} )
999log n + 65,000 = lg n )
6n^{ }(lg^{2} n) = n^{ }(lg^{2} n) )
6n^{4 }+ 5n^{3 } = n^{4} )
2^{n} + 3n = 2^{n} ) .
Let g_{1} = (1/4)^{n} , g_{2} = lg n, n_{0 }= 2 and c =1,
Then, 0 <= (1/4)^{n} <= lg n, n>=2.
Let g_{2} = lg n, g_{3} = n^{ }(lg^{2} n), n_{0 }= 2 and c =1,
Then, 0 <= lg n <= n^{ }(lg^{2} n), n>=2 since 1 <= n^{ }lg n n>=2.
Let g_{3} = n^{ }(lg^{2} n), g_{4} = n^{4}, n_{0 }= 2 and c =1,
Then, 0 <= n^{ }(lg^{2} n) <= n^{4}, n>=2 since (lg^{2} n) <= n^{3}, which is true n>=2.
Let g_{4} = n^{4}, g_{5} = 2^{n}, n_{0 }= 2 and c =1,
Then, 0 <= n^{4} <= 2^{n}, n>=2^{4} since lg (n^{4}) <= lg (2^{n}) 4 lg n <= n lg 2
4 lg n <= n , which is true n>=2^{4}.
4. (10 points) Find the smallest (positive) integer value for which 50n^{3} < 3^{n}
Answer: n=10 is the smallest integer value for which 50n^{3} < 3^{n}.
Note that we have : n 50n^{3} 3^{n}
9 36,450 19,683
10 50,000 59,049
5. (25 points) Textbook, (1^{st} edition) exercise 1.35 on p.15. Consider the problem of searching for a value v in a sequence that is already sorted. Since the sequence is sorted, we can compare with v the value at the midpoint of the sequence and eliminate half of the sequence from further consideration. Binary search is an algorithm that repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode for binary search. Explain why your pseudocode is correct. Show that its worstcase running time is in (lg n).
Answer:
BinarySearch(A, v)

left 1

right length[A]

while left <= right
4. do middle (left + right)/2
5. if v = A[middle] then Return middle

else if v < A[middle]
7. then right middle –1 //reduces to left half of the array
8. else
9. left middle +1 //reduces to right half of the array
10. Return NIL
Correctness: Since the pseudocode contains a while loop, we need to show that the loop terminates and that when it terminates the correct answer is produced. The values in the array appear in sorted order; this allows us to discard ½ the remaining possibilities each time through the loop. If v is somewhere in the array, then we will encounter it as the middle element in some iteration. This takes at most lg(n) iterations, because after throwing away ½ the elements lg(n) times we have only 1 element left to examine, and left=right=middle. So, if v is in the array we return out of the loop and stop. If v is not in the array, then after lg(n) iterations we won’t find it in that one remaining element. In this case, left or right will be adjusted so that left > right. This adjustment causes the while condition to fail so that the pseudocode terminates and returns NIL (i.e. failure).
Running Time: We argue that the worstcase running time of binary search is lg n ). The correctness argument above shows that the loop executes at most lg(n) times. This gives us an upper bound of O(lgn). The case in which v is not in the array is a worstcase input for binary search because in this case the loop is not exited early and lg(n) iterations are required. This worstcase input provides a worstcase lower bound of (lgn). Together the matching lgn lower and upper bounds allow us to conclude that the worstcase running time of binary search is lg n ).
6. (25 points) This problem refers to the Mystery( ) pseudocode below:
Mystery(A, n)
for i 1 to n
do for j 1 to n
do if A[i][j] equals 1
then print "*" without newline
else print " " without newline
print newline

Given the following inputs, what is the output of a call Mystery(A, n) ? Inputs: n=5 and 2dimensional nxn array A is initialized as follows (row elements are listed in increasing column order):
row 1: 0, 0, 1, 0, 0 row 2: 0, 1, 0, 1, 0 row 3: 0, 1, 1, 1, 0 row 4: 1, 0, 0, 0, 1 row 5: 1, 0, 0, 0, 1
Answer:

Give a function f(n) that is an upper bound on the worstcase running time of Mystery. Justify your answer.
Answer: The upper bound worstcast running time is O(n^{2}) since each element of array is checked at most once by two for loops that each iterate a maximum of n times.

Give an example of a worstcase input for array A for Mystery when n=5.
Answer: All elements of array equal to 0. Its running time is n^{2}). Actually, every example forces the running time to be proportional to n^{2}, since there is no way to exit the for loops early.

Can you conclude from your answers to (b) and (c) that Mystery’s worstcase running time is = (f(n))? Why or why not?
Answer: Yes. From (b), we get an upper bound on the worstcase running time O(f(n)), and from (d), we get an lower bound on the worstcase running time f(n)). So, we can conclude that the worst case running time is (f(n)). 