1. Programs A and B are analyzed and are found to have worst-case running times no greater than 150 N log N and N² , respectively. Answer the following questions, if possible:

  1. Which program has the better guarantee on the running time for large values of N (N > 10 000)?
  2. Which program has the better guarantee on the running time for small values of N (N < 100)?
  3. Which program will run faster on average for N = 1000?
  4.  Is it possible that program B will run faster than program A on all possible inputs?

2. An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following:

  1. linear
  2. O (N log N)
  3. quadratic
  4. cubic

3. An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following:

  1. linear
  2. O (N log N)
  3. quadratic
  4. cubic

4. Order the following functions by growth rate, and indicate which, if any, grow at the same rate.:
N, square root of N, N^1.5, N² , N log N, N log log N, N log² N, N log (N²), 2/N, 2N, 2N/2, 37,N³, N² log N.

5. For each of the following six program fragments, do the following:

  1. Give a Big-Oh analysis of the running time (you can do this before you come to lab!)
  2. Implement the code in a simple main class and run it for several interesting values of N.
  3. Compare your analysis with the actual running times for your report.
 

// Fragment #1 for ( int i = 0; i < n; i ++)     sum++; // Fragment #2 for ( int i = 0; i < n; i ++)     for ( int j = 0; j < n; j ++)         sum++; // Fragment #3 for ( int i = 0; i < n; i ++)     sum ++;     for ( int j = 0; j < n; j ++)         sum ++; // Fragment #4 for ( int i = 0; i < n; i ++)     for ( int j = 0; j < n*n; j ++)     sum++; // Fragment #5 for ( int i = 0; i < n; i ++)     for ( int j = 0; j < i; j ++)         sum++; // Fragment #6 for ( int i = 1; i < n; i ++)     for ( int j = 0; j < n*n; j ++)         if (j % i == 0)            for (int k = 0; k < j; k++)                sum++;

6. A prime number has no factors besides 1 and itself. Do the following:

1. Write a program to determine if a positive integer N is prime. In terms of N, what is the worst-case running time of your program?
2. Let B equal the number of bits in the binary representation of N. What is the value of B?
3. In terms of B, what is the worst-case running time of your program?
4. Compare the running times needed to determine if a 20-bit number and a 40-bit number are prime by running 100 examples of each through your program. Report on the results in your lab report.

7. A rational number can be expressed as a fraction numerator / denominator. A class for modelling rational numbers could look like this:

 
public class Ratio{
// For creating an object that can store a rational number.
// A rational number can be expressed as a fraction 
// numerator / denominator

  protected int numerator;
  protected int denominator;

  public Ratio (int top, int bottom)
  // pre:  bottom != 0
  // post: constructs a ratio equivalent to top / bottom
  {
     numerator = top;
     denominator = bottom;
  }

  public int getNumerator()
  // post: returns the numerator of the fraction
  {
     return numerator;
  }

  public int getDenominator()
  // post: returns the denominator of the fraction
  {
     return denominator;
  }

  public double value()
  // post: returns the value of the fraction as a real number
  {
     return (double) numerator / (double) denominator;
  }

 
 

1. Implement a class for this data type that supports standard math operations: addition, subtraction, multiplication and division. Offer a print() method that returns a nicely formatted String. You should also be able to construct Ratios from either a numerator-denominator pair, or a single integer, or with no parameter as all (what would a reasonable default value be?). You are going to have to test your Ratio, so think about good test cases and implement a test harness so that you can run the tests.
2. If you get that done before class is out, add in relational methods for testing equality, inequality, greater than and less than.

For the bored

1. The Sieve of Eratosthenes is a method used to compute all primes less than N. Begin by making a table of integers 2 to N.
   Find the smallest integer i that is not crossed out. Print i (it is prime!) and cross out i , 2i , 3i , .... Terminate when i is greater than the square root of N. The running time has been shown to be O (N log log N). Write a program to implement the Sieve and verify that the running time is as claimed. If you are really bored, animate this with a GUI!
2. Offer a method that takes a String as a parameter and returns a Ratio. There can be blanks around the / sign. What will you do if the String does not represent a Ratio?  In order to maintain a Ratio in reduced terms, you would find it useful to be able to determine the greatest common divisor of two values. Assuming that this method is a part of the Ratio class, should it be declared public or private?
3. (only if you are very bored) Write a program that asks the user to enter a sequence of rational numbers from the keyboard, reads these numbers into an array of Ratios, then calculates the largest, the smallest, the average and the maximum value.