CS35 Lab 3: Analysis of Algorithms

Due on paper 11:59 p.m. Wednesday night, September 26

Run update35 to copy some useful files to your cs35/labs/03 directory. You will not turn in any code this week, and will instead turn in written solutions to the box outside of my office (Science Center 253). Note that although your solutions are written and not electronically submitted, the deadline is still Wednesday night at 11:59 p.m.



Write solutions to the following problems:
  1. Show that 3n^4 + 3*lg n + 205n^3 is O(n^4)

  2. Answer question C-4.20.

  3. Based on C-4.26 The image below shows an n by n grid that is stored in memory as a two dimensional array. The element at row i column j can be indexed in constant time using grid[i][j]. Each cell in the grid contains either a 1 or a 0 (indicated in the figure with green and white blocks). In any column, all the one's appear before any of the zeros. Given such a grid, design an O(n) algorithm for finding the column with the most ones (tallest green tower). Note there are O(n^2) cells, so you cannot check every cell in the grid.
    grid graph

  4. Prove the following claim using induction. Prove for all n>=1. Be sure to clearly enumerate each step in your proof

  5. Describe an algorithm for finding both the minimum and maximum (simultaneously) of n numbers using fewer than 3n/2 comparisons. The following pseudocode finds the max using n-1 comparisons.
    findMax(Array A, size n>0):
      max=A[0]
      for i in 1 to n   (inclusive)
        if(A[i] > max)
          max=A[i]
      return max
    
  6. Give the best Big-O bounds on the runtime of the following functions. By "best" Big-O bounds we mean the bounds that most-closely describe the actual run time of the function. E.g., for a linear algorithm the best Big-O bound is O(n), not O(n^2), even though linear algorithms are O(n^2) as well.
    Ex1(n)
     for(i=0; i<n; i++)
       a = i
    
    Ex2(n)
     for(i=0; i<n; i+=2)
       a = i
    
    Ex3(n)
     for(i=0; i<n*n; i++)
       a = i
    
    Ex4(n)
     for(i=0; i<n; i++)
       for(j=0; j<=i; j++)
         a = i
    
    Ex5(n)
     for(i=0; i<n*n; i++)
       for(j=0; j<=i; j++)
         a = i
    
    Ex6(n)
     k=1
     for(i=0; i<n; i++)
       for(j=0; j<k; j++)
         a = j
       k=k*2
    


Experimentally measure algorithm performance:

Perform an experimental analysis that compares the relative running times of the functions you considered in Ex1 through Ex6 above.

To run these experiments you will need to use different sizes of n, depending on the example being tested. For fast algorithms you will need to use very large n, starting with 100000 or 1 million. Slower algorithms might require you to test with n as small as 10 or 100. When you implement the functions above, we recommend that you use long integers instead of ints. longs in C++ can store larger numbers than ints.

After you run update35 your cs35/labs/03 directory will contain some helpful files:


Submitting your work
Hand in your work to the box outside Ameet's office by 11:59 p.m. Wednesday night. Do not turn in any work with handin35.