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.

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.


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
   

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:

• A Timer class (in timer.h, timer.cpp) that works like a stop watch. With a Timer instance t, t.start() will start the timer and t.stop() will stop the timer, allowing you to get the recorded time with t.getRecordedTime().
• timerTest.cpp demonstrates the use of the Timer to measure the performance of an example function. The basic idea is, for each input size you want to measure:
  1. Start the timer.
  2. Run the function you want to measure the performance of on a single input size.
  3. Stop the timer.
  4. Print the input size and recorded time.
  timerTest.cpp also demonstrates some new C++ output formatting options and how to use long integers in your example functions.
• ex4results.txt: A sample data file that can be used as input to the pgraph program, which allows you to view your results graphically. To see a graph of these example results, run:

    $ pgraph ex4results.txt
  

  in your terminal window.

  When you create your own data files, please put your name(s) in the graph title and label your data with appropriate names. When you run pgraph you can save your results as a Postscript (.ps) file: click the save icon (the floppy disk, on the bottom right), type a filename (such as ex4results.ps), and select "Postscript (*.ps)" as the file type. You can then print your results from your terminal window using the lpr command. For example:

    $ lpr ex4results.ps
  

• You do not need to place all functions on the same plot. If two functions behave similarly enough, you can combine them in one graph. In either case, you should label your graphs so I know which function you are graphing.

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.

Home Page