Algorithm Problem

Analyze each of the following statements to indicate whether the statement is true or false, respectively. If the statement is correct, briefly state why. If the statement is wrong, correct it. Please elaborate on your justification or correction, but be brief. One-sentence explanations should suffice. T F For any asymptotically nonnegative function f (n). we have f(n) + o( f (n)) = O( f (n)). T F By Case 2 of the Master Theorem, the solution to the recurrence T (n) = 3T(n/3) + O(1g n) is T (n) =  (n 1g n). T F By reducing the problem of sorting to the problem of building a heap, one can prove that building an n-element heap takes time =... click for more

Show that "q^2 + (n-q-1)^2" achieves a maximum over q = 0, 1, ..., n-1 when q = 0 or q = n-1.

Show that "q^2 + (n-q-1)^2" achieves a maximum over q = 0, 1, ..., n-1 when q = 0 or q = n-1.

Obtain asymptotically tight bounds on lg(n!) without using Stirling's approximation.

Obtain asymptotically tight bounds (Big-Oh and Big-Omega) on lg(n!) without using Stirling's approximation. Instead, evaluate these using the expansion of lg(n!) as a summation.

Algorithm Problem

Argue briefly that to test whether a given n-element permutation can be sorted by an n-input comparison network, it suffices to test the network on n—1 sequences of 0’s and 1’s.

What is the effect of calling HEAPIFY(A, i) when the element A[i] is larger than its children?

Consider the following definition of HEAPIFY. HEAPIFY(A, i) 1 l = LEFT(i) 2 r = RIGHT(i) 3 if l < heap-size[A] and A[l] > A[i] 4 then largest = l 5 else largest = i 6 if r < heap-size[A] and A[r] > A[largest] 7 then largest = r 8 if largest != i 9 then exchange A[i] and A[largest] 10 HEAPIFY(A,largest) What is the effect of calling HEAPIFY(A, i) when the element A[i] is larger than its children?