Goal

Practice lists, stacks, Sets and Maps. Some runtime revision.

Questions

1.   (a)  Order the following functions by growth rates:

N, ,N , N 1 .5 , N2 , N log N, N log log N, N log2 N, N log(N2 ), 2/N, 2N , 2N/2 , 37, N3 , N2 log N .

Indicate which functions grow at the same rate.

(b)  Rank the following three functions: log N , log(N2 ), log2 N . Explain.

You should find all the mathematics you need in the class notes and in Kleinberg and Tardos, chapter 2. You may find it useful to remember that one way to compare the relative growth rates of f (n) and g(n) is to look at the ratio f (n)/g(n) as n · 二. If that ratio approaches 0, then g grows faster than f : f (n) = O(g(n)). If it approaches infinity then f grows faster than g. If the ratio approaches a constant different from both 0 and 二 then f and g grow at the same rate.

2.   (a)  Find a big-O estimate for the running time (in terms of n) of the following function (with expla- nation)

int mysterySum(  int  n  )

{

int  i,  j,  s=0;

for(i=0;  i  <  n;  i++)  {

for(j=0;  j  <  i;  j++)  {

s  +=  i*i;

}

}

}

(b) Is this version of mysterySum faster? Is the big-O analysis different?

int mysterySum1(  int  n  )

{

int  i,  j,  s=0;

for(i=0;  i  <  n;  i++)  {

int  i2  =  i*i;

for(j=0;  j  <  i;  j++)  {

s  +=  i2;

}

}

}

(c)  Replace the inner loop in mysterySum by an O(1) expression and compute the running time of the new program.

(d)  Find a single O(1) expression giving the same result.  Hint:  Evaluate the function by hand (or compile and run the code) for a few values of n and try to see the pattern.

Notice: You have to find a mathematical formula, not a piece of code. Start with the expression you derived in part c above (hint: It is a series) and find the sum of the series any way you want (including looking it up).

3.  The following program computes 2n :

int  power2(int  n)

{

if  (n==0)  return  1;

return  power2(n-1)+power2(n-1);

}

(a)  Find a recurrence formula as we learned in class. Find the runtime. What is the big problem with

this function?  (hint: We discussed something similar in class).

(b) Introduce a small modification that makes the function run in linear time. Show why the runtime

is linear.

(c)  (bonus) The following function also calculates 2n :

int  power2New(int  n)

{

if  (n==0)  return  1;

if  (n  %  2  ==  0)  {

int  result  =  power2New(n/2);

return  result*result;

}

else

return  2*power2New(n-1);

}

Explanation: If n is even, then 2n  = (2  )2 , so we can calculate 2  recursively and square, cutting half of n in one move.  Otherwise, we resort to the previous method.  Show that the runtime of power2New is logarithmic in n.  Hint:  It’s easy to show it when n is even, but sometimes n is odd... The trick is to show that the entire function is logarithmic nonetheless.

4.   (a)  Suppose a List<String> list1 has elements “A”, ”B”, “C”, and ”D”. What is returned by:

1.  list1.iterator().next();

2.  list1.listIterator().next();

3.  list1.listIterator(2).next();

4.  list1.listIterator(4).previous();

(b)  Say what is deleted (or what happens) to the above operations when followed by remove(). Explain

(answer each part separately. That is – assume the list is back intact after you answer part 1, and you start with a fresh copy of a 4-item list for part 2).

(c) If we had the following sequence of commands:

list1.listIterator(2).next(); list1.listIterator(2).remove(); list1.listIterator(4).previous(); what would be returned? What would the list look like following these operations?