August 17, 1999  CS I section
In this section of the exam, there are six (6) problems, some
with multiple parts. You are to do all of them. The weight of
each problem in this section, is indicated with the problem. The
parts of a multipart problem are equally weighted.
The algorithms in this exam are written in a combination of pseudocode and programming language notation. The algorithms that you are asked to produce should use a syntax that is clear and unambiguous.
Partial credit can not be given unless all work is shown.
As always, be complete, yet concise, and above all be neat, credit can not be given when your results are unreadable.
(1, 20%) Given the following array of numbers and the algorithm
below, answer the questions below. Assume that the global array
X[1..n] is correctly declared and contains the values shown.
procedure M(a, b : integer)
c < 0;
d < 0;
i < a  1;
j < c + 1;
while (i > j) do
a) Show the array X after the procedure was called with
M(8,4)?
b) What value will the following variables contain after
the while loop is finished?




(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} + * = _________________



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



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 / +  Valid Invalid
d) 3 2 5  + * 6 2 1 + * Valid 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.
b) For an O(n) algorithm, an instance with n = 12 takes 21 seconds.
c) For an O(log_{2}n) algorithm, a friend tells you that his instance took
36 seconds to run.
You run the same program, on the same machine,
and your instance with n = 16 takes 24 seconds.
Given the following pseudocode segment, answer the questions below
for an arbitrary n:
for i < 1 to (2*n) do
d) What is the Order of this code segment? ____________________
e) What will be the value of x when the for loops end? ____________________
In the space below, write a RECURSIVE algorithm that correctly finds n!.
Factorial(n)
(5, 20%) Find the closed form or exact value for the following: ( n is an arbitrary positive integer):
a) å (3i + 3) (where i ranges from 1 to n) = ______________________
b) å (4i  3) (where i ranges from 30 to 80) = ______________________
c) S = 2 + 4 + 6 + ... + 2(n2) + 2(n1) = _____________________
d) t(n) = t(n1) + 2, where t(0) = 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 ?
the O(n!) algorithm  the O(n^{2}) algorithm  both will take the same time 
b) Which will take longer when n is very large?
the O(n!) algorithm  the O(n^{2}) algorithm  both will take the same time 
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 _________________
Reverse a character string of n characters _________________
Find a cycle containing every node in a graph _________________
Fitting a set of final exams into the shortest number of days _________________
Sort a list of n values _________________
Towers of Hanoi _________________
Find a subset of numbers which sum exactly to X _________________