CS 307 – Midterm 1 – Fall 2001



Points off 1 2 3 4 5 6 Total off Net Score

| | | | | | | | |

CS 307 – Midterm 2 – Spring 2003

Name____________________________________

Last 4 digits of SSN / Student ID ______________

Section Leader's Name ___________________________

Instructions:

1. There are 4 questions on this test.

2. You have 2 hours to complete the test.

3. You may not use a calculator on the test.

4. When code is required, write Java code.

5. The style guide is not in effect except where noted.

6. Efficiency is not graded except where noted.

7. Ensure your answers are legible.

8. When writing code you may not use any methods or classes from the Java Standard Library except as noted and the System.out.print, System.out.println, and the equals method.

1. (2 points each, 30 points total) Short answer. If an error would occur answer "syntax error" or "runtime error" depending on what type of error it would be.

Recall that when asked for Big O your answer should be the most precise Big O function. For example Selection Sort has an average case Big O of O(N^2), but per the formal definition of Big O it is technically correct to say Selection Sort also has a Big O of O(N^3). On this test I want the most precise Big O function. (Closest without going under.)

A. A method has a Big O of (N^2). It takes 20 seconds for this method to complete when working with a data set of 2000 elements. (N = 2000). What is the predicted time for the method to complete when the data set has 4000 elements?

_____________________________________________________________________________

B. A method has a Big O of (N^3). It takes 15 seconds for this method to complete when working with a data set of 1000 elements. (N = 1000). What is the predicted time for the method to complete when the data set has 4000 elements?

C. A programmer claims to have developed a sort that is sub-quadratic. (Performs in a Big O of less than O(N^2). If the average case Big O for an algorithm is O(N^1.25), then the algorithm's Big O is less than O(N^2) and it is a sub-quadratic algorithm.) It takes 5 seconds to sort a data set of 1000 items, 15 seconds to sort a data set of 2000 items, and 45 seconds to sort a data set of 4000 items. Does the data support the programmer's claim? Why or why not?

_____________________________________________________________________________

D. What is the average case Big O for replacing an item in a List when the internal storage container is an array of Objects?

/* pre: 0 = 0; i--)

for(int j = 0; j < N; j++)

System.out.println( j + i );

_____________________________________________________________________________

G. What is the Big O of the following code? Method dogbert has a Big O of O(N) where N is the magnitude of the argument sent to the method.

for(int i = 0; i < N; i++)

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

dogbert(i);

_____________________________________________________________________________

H. What is the Big O of the following code?

int total = 0;

for(int i = 0; i < N; i++)

for(int j = 0; j < 5; j++)

for(int k = 0; k < N; k++)

for(int m = 1; m 1 )

{ System.out.print( pointy.charAt(1) );

dilbert( pointy.substring(2) );

System.out.print( pointy.charAt(0) );

}

}

What is output by the following line of code?

dilbert("Catbert");

Description of methods from String class

|char |charAt(int index) |

| |          Returns the character at the specified index. An index ranges from 0 to length() - 1. The first character of |

| |the sequence is at index 0, the next at index 1, and so on, as for array indexing. |

| String |substring(int beginIndex) |

| |          Returns a new string that is a substring of this string. The substring begins with the character at the |

| |specified index and extends to the end of this string. |

_____________________________________________________________________________

J. Consider the following method:

public int philPrinceOfInsufficientLight(int num)

{ if( num ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download