Reference no: EM1353496
The recent discovery of the following fragment of uncommented procedural C code in the Sunlab has caused a big scandal.
foo(int a[],int l,int r,int k)
{ int i;
i = partition(a,l,r);
if (i == k) return a[k];
else if (i < k) return foo(a,i+1,r,k);
else return foo(a,l,i-1,k); }
Since the author of the code is still hiding, we will have to decipher it. The TAs have already determined that function partition(int a[],int l,int r) works as follows: let v=a[r]; partition rearranges the subarray a[l] through a[r] such that the elements equal to v precede those greater than v and follow those smaller than v, 4-1CS 401 Homework 4 Due October 18 in Class and returns an index i such that a[i]=v. Thus, partition works in the same manner as the function Partition of Quicksort discussed in class, returning the position of the partitioning element v in the rearranged subarray a[l...r]. Let a be an array of size N of integers, and 1 k N.
(a) What will foo(a,1,N,k) return?
(b) What is the worst-case time complexity of foo(a,1,N,k), and for which inputsdoes it occur?
(c) Can the running time of foo(a,1,N,k) be improved? If so, how? If not, why?
|
Perceptions of american culture
: We have been called 'ugly Americans' by people in other countries because some Americans at times do portray
|
|
How farmer jones carrots and buys beets
: How Farmer jones carrots and buys beets. His income eLasticity of demand for both carrots and beets is posotive.an increase in the price of carrots causes him to.
|
|
Explain funding and closing of the library capital
: Describe Below is selected information related to the funding and closing of the Library Capital Project Fund and The construction was funded by a number of sources
|
|
Determine the value of the firms current liabilities
: A company's balance sheet shows current assets of $95, net fixed assets of $250, long-term debt of $40, and owners equity of $200. Determine the value of the firm's current liabilities if that the only remaining balance sheet item.
|
|
Determining worst-case time complexity
: The recent discovery of the following fragment of uncommented procedural C code in the Sunlab has caused a big scandal. What is the worst-case time complexity of foo(a,1,N,k), and for which inputsdoes it occur?
|
|
Employee empowerment culture
: In the human resources area, discuss their theory of moving towards an employee empowerment culture. In marketing, discuss their theory of penetration pricing.
|
|
What are your thoughts
: However, if the "new" leader does not implement and/or show signs of change within the first 90 days, employees may tend to relax and continue with status quo.
|
|
Hedging interest rate risk
: A bond manager who wants to hold the bond with the greatest potential volatility would be wise to hold;
|
|
What does the change in his consumption reflect
: What does the change in his con- sumption reflect a substitution or an income effect.
|