Each answer must fit in the box provided. The graders will ignore any writing outside the box. You may write your answers by hand and upload a scan. Or, you can typeset your answers into the PDF and upload that.

4.1 Exact running time (2 points)

A sequential algorithm uses exactly [1345786.7 . lg n] operations for input size n. Each oper- ation takes 1 us. What is the running time for n = 1000000000? Show your work. Your final answer must be a floating-point number.

4.2 Exact running time (2 points)

A sequential algorithm uses exactly [5n2.8 + 2n2 _ 20] operations for input size n. Each oper- ation takes 1 us. What is the running time for n = 1000? Show your work. Your final answer must be a floating-point number.

4.3 Exact running time (2 points)

A sequential algorithm uses exactly [1.7 . 3n] operations for input size n. Each operation takes 1 us.  What is the running time for n  = 10?  Show your work.  Your final answer must be a floating-point number.

4.4 Exact number of operations (2 points)

A sequential algorithm uses exactly  [1.7 . 3n] operations for input size n.  What is the exact number of operations used for n = 30? Show your work. Your final answer must be an integer.

4.5 Exact number of operations (2 points)

A sequential algorithm uses exactly [ . n lg n] operations for input size n. What is the exact number of operations used for n = 2000000? Show your work. Your final answer must be an integer.

4.6 Exact maximum size within time constraint (2 points)

A sequential algorithm uses exactly [1.7 . 3n] operations for input size n. Each operation takes 1 us. What is the exact largest input size n that can be handled within one hour? Show your work. Your final answer must be an integer.

4.7 Exact maximum size within time constraint (2 points)

A sequential algorithm uses exactly [1345786.7 . lg n] operations for input size n. Each oper- ation takes 1 us. What is the exact largest input size n that can be handled within 10 s? Show your work. Your final answer must be an integer.

4.8 Exact maximum size within time constraint (2 points)

A sequential algorithm uses exactly [1345786.7 . lg n] operations for input size n. Each opera- tion takes 1 us. What is the exact largest input size n that can be handled within one minute? Show your work. Your final answer must be an integer.

4.9 Exact maximum size within time constraint (2 points)

A sequential algorithm uses exactly  [ . n lg n] operations for input size n.  Each operation takes 1 us. What is the exact largest input size n that can be handled within one minute? Show your work. Your final answer must be an integer.

4.10 Asymptotic complexity - logarithmic (6 points)

Provide an example of an algorithm with logarithmic worst-case asymptotic time complexity. (1) Either name a well known algorithm from CLRS or describe your own. (2) Briefly explain why this algorithm has logarithmic complexity. Make sure to state the worst-case asymptotic time complexity using the standard o-notation.

4.11 Asymptotic complexity - polynomial (6 points)

Provide an example of an algorithm with polynomial worst-case asymptotic time complexity. (1) Either name a well known algorithm from CLRS or describe your own. (2) Briefly explain why this algorithm has polynomial complexity. Make sure to state the worst-case asymptotic time complexity using the standard o-notation.

4.12 Asymptotic complexity - exponential (6 points)

Provide an example of an algorithm with exponential worst-case asymptotic time complexity. (1) Either name a well known algorithm from CLRS or describe your own. (2) Briefly explain why this algorithm has exponential complexity. Make sure to state the worst-case asymptotic time complexity using the standard o-notation.

4.13 Asymptotic complexity - insertion sort (8 points)

A possible implementation of insertion sort is given by the following Python code:

def  insertion_sort(xs,key=identity):

for  i  in  range(1,len(xs)):

e  =  xs[i]

k  =  key(e)

j  =  i  -  1

while  j  >  -1  and  key(xs[j])  >  k:

xs[j+1]  =  xs[j]

j  =  j  -  1

xs[j+1]  =  e

Rigorously prove that the worst-case asymptotic time complexity of this insertion sort is T(n) = o(n2 ). (Answer on next page.)

4.14 Asymptotic complexity - binary insertion sort (8 points)

Referring to the preceding question about insertion sort:

1. Modify the insertion sort Python code such that the location where the element e is in- serted is found with a binary search.

Analyze the worst-case asymptotic time complexity of this modified insertion sort. You do not need to provide a detailed proof.  Make sure to state the worst-case asymptotic time complexity using the standard o-notation.

4.15 Asymptotic complexity - algorithm analysis (10 points)

Analyze the worst-case asymptotic time complexity of the following C implementation of an algorithm r, which takes an array of numbers and the length of that array as arguments. Make sure to state the worst-case asymptotic time complexity using the standard o-notation.  (An- swer on next page.)

void  r  (int  a[],  int  l)

{

if  (l  ==  1)

{

return;

}

else

{

for  (int  i  =  0;  i  < l-1; i++)

{

if  (a[i]  >  a[i+1])

{

int  t  =  a[i];

a[i]  =  a[i+1];

a[i+1]  =  t;

}

}

r(a,  l-1);

}

}

4.16 Asymptotic complexity - algorithm analysis (10 points)

Analyze the worst-case asymptotic time complexity of the following Python implementation of an algorithm q, which takes a Python list of numbers as an argument, e.g., q([1,2,3]). Make sure to state the worst-case asymptotic time complexity using the standard o-notation. (Answer on next page.)

def  q(a):

r  =  []

p(a,0,[],r)

return  f(d,r)

def  p(a,b,c,r):

if  b  >=  len(a):

r .append(c)

return

for  i  in  range(b,len(a)):

s(a,b,i)

p(a,b+1,c+[a[b]],r)

s(a,b,i)

def  s(a,i,j):

t  =  a[i]

a[i]  =  a[j]

a[j]  =  t

def  d(a):

for  i  in  range(len(a)-1):

if  a[i]>a[i+1]:

return  False

return  True

def  f(p,a):

for  i  in  range(len(a)):

if  p(a[i]):

return  a[i]

4.17 Algorithmic recurrences (10 points)

(CLRS Exercise 4.4-1a.) For the algorithmic recurrence

T(n) = T ╱ 、+ n3

1. Sketch its recursion tree and guess a good asymptotic upper bound on its solution.

2. Use the substitution method to verify your answer.

4.18 Heaps (10 points)

(CLRS Problem 6-2) A d-ary heap is like a binary heap, but (with one possible exception) nonleaf nodes have d children instead of two children. In all parts of this problem, assume that the time to maintain the mapping between objects and heap elements is O(1) per operation.

1. Describe how to represent a d-ary heap in an array.

2. Using o-notation, express the height of a d-ary heap of n elements in terms of d and n.

3. Give an efficient implementation of EXTRACT-MAX  in a d-ary max-heap.  Analyze its running time in terms of d and n.