java
Write your answers in the text boxes provided.
Be clear with your answers!
Governors State University
CPSC 4355 Spring 2021 Midterm
NAME: _________________________________________________
1. Show that 3n3 + n2 is big-Oh of n3. You can use either the definition of big-Oh (formal) or the limit approach. Show your work! (5 pts.)
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? (hint: see Running Time Estimation in notes on Algorithm Analysis)
Show your work! (20 pts.)
a. linear
b. O(NlogN)
c. quadratic
d. 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? (hint: see Maximum Problem Size in notes on Algorithm Analysis)
Show your work! (15 pts.)
a. linear
b. quadratic
c. cubic
4. Consider the following algorithm:
int j = 1;
int k = 1;
for (i = 1; i <= 10; i++)
j = j * 100; consider this a basic operation
for (i = 1; i <= 20; i++)
k = k * 2; consider this a basic operation
What is the running time, T(n)? Give both the exact function T(n), and then give a big- Theta estimate of T(n). Show your work. For example, if T(n) is exactly n2 + 3n, then T(n) is big-Theta of n2. Show your work! (10 pts.)
5. Consider the following algorithm:
sum = 0;
for ( i = 0; i < n; i++ )
for ( j = 0; j < i * i ; j++ )
for ( k = 0; k < j ; k++ )
sum++;
What is the general running time, T(n)? Give a big- Theta estimate of T(n). Show your work! (10 pts.)
6. If f(n) is big-theta of g(n), then the value of f may be infinitely away from that of g. (True or False) Explain! (5 pts.)
7. If the worst case time of algorithm A is big-oh of that of B, then B is
never
faster than A for large problems. (True or False) Explain! (5 pts.)
8. Hardware vendor XYZ Corp. claims that their latest computer will run 100 times faster than that of their competitor, Prunes, Inc. If the Prunes, Inc. computer can execute a program on input of size n in one hour, what size input can XYZ’s computer execute in one hour for each algorithm with the following growth rate equations? (10 pts.) Show your work!
a. 2/N
b. Log N
9.
Bonus
: On the Sorting Algorithms Animations site (see Sorts folder in Course Content), the QuickSort3 sort consistently performed better than standard QuickSort.
Explain
how QuickSort is modified in QuickSort3 to deliver greater performance?
Note: Click the Sort name under the Algorithms heading for detail on each sort. (10 pts.)
Page 5 of 7