August 17, 1999  CS I section
SOLUTION
(1, 20%) Given the following global array of numbers and procedure,
answer the questions below.
(Note: each box in part a) is worth 1 point and and each box in b) is worth 3 points)
b. What value will the following variables contain after the while is finished?
c  6  d  24  i  4  j  4 
(2, 18%) The following are Postfix expressions. All values are single decimal digits and the
operations are addition "+", subtraction "", multiplication "*" and division "/". In each box below the Postfix expression, show ONLY the contents
of the stack at the indicated point in the Postfix string (point A, B or C). Put the final answer in the blank. If the Postfix string is invalid, carry the operations as far as possible and write "invalid" as the answer.
a) 6 4 1  2 ^{A} + 7  1 ^{B} + 5 * 3 ^{C} + * = 12



b) 1 2 3 4 ^{A} + *  5 ^{B} 6 + 7  ^{C} 8 * + = 19



Next to each Postfix expression, circle one answer to indicate if it is a valid Postfix string or not:
(no extra credit for providing the answer, if it is valid)
c) 4 3 + 5 2  * 6 2 / +  Invalid
d) 3 2 5  + * 6 2 1 + * Invalid
(3, 20%) Answer each of the following "timing" questions concerning an algorithm of a particular order and a data instance of a particular size. Assume that the run time is affected by the size of the data instance and not its composition.
a) For an O(n^{3}) algorithm, an instance with n = 3 takes 54 seconds.
for i < 1 to (2*n) do
d) What is the Order of this code segment? O(n^{2})
e) What will be the value of x when the for loops end? 2*(2n)(n+2)
In the space below, write a RECURSIVE algorithm that correctly finds n!.
Factorial(n)
Factorial(n) if n <= 1 then return 1 else return Factorial(n1) * n
(5, 20%) Find the closed form or exact value for the following: (assume that n is an arbitrary positive integer):
a) å
(3i + 3) (where i ranges from 1 to n) =
(3n^{2} + 9n)/2
Since å i _{(i = 1 to n)} = (n(n+1))/2 and å 1 _{(i = 1 to n)} = n then
å (3i+3) _{(i = 1 to n)} = 3(n(n+1))/2 + 3(n) = (3n^{2} + 3n)/2 + 6n/2 = (3n^{2} + 9n)/2
b) å
(4i  3) (where i ranges from 30 to 80) =
11067
4å i _{(i = 30 to 80)} = 4å i _{(i = 1 to 80)}  4å i _{(i = 1 to 29)}
= 4( 80(81)/2  29(30)/2 ) = 2(80(81)  29(30)) = 2(6480  870) = 11220 and
3å i _{(i = 30 to 80)} = 3å i _{(i = 1 to 80)}  3å 1 _{(i = 1 to 29)} = 3(80  29 ) = 3(51) = 153 and
= 11220  153 = 11067
c) S = 2 + 4 + 6 + 8 + … + 2(n2) + 2(n1)= n^{2}  n
d) t(n) = t(n1) + 2, where t(0) = 3, =
2n + 3
(6, 12%) Answer the following questions:
Suppose you have two algorithms that both correctly solve a problem. One algorithm takes O(n!) steps and the other takes O(n^{2}) steps. Assume that no other factors (constants, the configuration of the data, etc.) affect the number of steps executed.
a) Which will take longer when n = 3 ?
3! = 3 * 2 * 1 = 6
3^{2} = 9
since 6 < 9, 3! < 3^{2}
b) Which will take longer when n is very large?
Although proving this for all cases is more complex, we can get a good idea
of which will take longer for large values of n by just trying a larger value of n, say 10:
10! = 10 * 9 * ... * 3 * 2 * 1 = 3628800
10^{2} = 100
since 3628800 is much larger than 100, we can be pretty sure that n! > n^{2}
for large values of n.
P is the class of problems known to be solvable in polynomial time, NP is the class that is verifiable in polynomial time (i.e., given the correct solution to an instance, we can verify its validity in polynomial time), and EXP are problems we know require exponential time to solve and to verify.
Which is the most appropriate set for each of the following?
Finding the most distant pair in a list of n items P
Reverse a character string of n characters P
Find a cycle containing every node in a graph NP
Fitting a set of final exams into the shortest number of days NP
Sort a list of n values P
Towers of Hanoi EXP
Find a subset of numbers which sum exactly to X NP