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 multi-part 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, d, i, j : integer;

c <- 0;
d <- 0;
i <- a - 1;
j <- c + 1;
while (i > j) do

if (X[i] >= X[j]) then
c <- c + (X[i] - X[j]);
j <- j + 1;
else
c <- c + (X[j] - X[i]);
i <- i - 1;
endif
if (X[i] < b) then
X[i] <- X[i] + 1;
else
X[i] <- X[i] - 1;
endif
d <- d + X[j];
endwhile

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

A

B

C

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

A

B

C

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³) algorithm, an instance with n = 3 takes 54 seconds.

How long will it take with n = 2? ____________________

b) For an O(n) algorithm, an instance with n = 12 takes 21 seconds.

If you used a different-sized data instance and it
took 14 seconds, how large must that instance be? ____________________

c) For an O(log₂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.

What size was his data set? ____________________

Given the following pseudocode segment, answer the questions below for an arbitrary n:

x <- 0

for i <- 1 to (2*n) do

for j <- 1 to (n+2) do
x <- x + 2

d) What is the Order of this code segment? ____________________

e) What will be the value of x when the for loops end? ____________________

x <- Factorial(n)

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) = ______________________

(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²) 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(n2) algorithm

both will take the same time

b) Which will take longer when n is very large?

the O(n!) algorithm

the O(n2) 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?

Evaluate a postfix expression _________________

 

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 _________________