Exercise 3

 

  1. Pen-and-paper (PDF) exercises:
    1. Analyze the following pseudocode and provide a "Big-Oh" estimate of its running time in terms of n. Explain your analysis. 
          for i=1 to n
        k = 1
        sum = 0
        for j=1 to i
            k = 2*k;
        for p=1 to k
	    sum = sum + p
    2. Show that log(n!) = O(n log(n)).
    3. Given an array of integers, some of them negative integers, sorted in increasing order, we are interested in whether the array has two integers a and b such that a+b=0
      • Write pseudocode for the obvious O(n2) algorithm that tries all pairs.
      • Write pseudocode for a faster O(n) algorithm and explain why it runs in time O(n).

    4. Consider an array A with n unique numbers. Then, define a flip as follows: a pair (i,j) is a flip if A[i]>A[j] and i<j. Clearly, an array can have multiple flips. For example:

      Now define the flip-count of an array as the number of flips that an array has. Clearly, an array sorted in increasing order has no flips and has flip-count zero.

      1. What is the flip-count of an array of n elements in decreasing order?
      2. Write down (pseudocode) a straightforward O(n2)algorithm to determine the flip-count of an array. Explain your running-time analysis.
      3. Adapt merge-sort to devise an O(n log(n)) algorithm to determine the flip-count of an array. Explain how it works, write out pseudocode, and explain why the running time is O(n log(n)).
    5. Look up Don Knuth and explain three of his most important contributions to computer science.
    Note: Credit will not be given only for answers - show all your work: your reasoning, steps you took to get your answer etc.

Submission: