Foundation Exam - CS I Section

October 16^th Foundation Exam

CS I Solutions

(1, 15%) The following (INCORRECT) algorithm is intended to be the iterative bubble sort algorithm. Assume that swap is a global procedure that exchanges the contents of its two parameters.

algorithm Bsort(n)

procedure B(k)

1) set j <- 1

2) while j < k do

3) if a[j] > a[j+1] then

4) swap(a[j], a[j+1])

5) set j ß j + 1

endprocedure

begin

6) for i = 1 to n-1 do

7) B(n-i);

endalgorithm

It SHOULD take this first list…

…and produce this list.

1a) But, it doesn't. What does it produce?

1b) There is one error in the algorithm. In which line does it occur?

1c) Write the correct pseudo-code for the line identified in 1b).

There are three possible ways to fix the problem in this algorithm. Therefore, there are three correct answers to parts 1b) and 1c).

error in line 2 - change to:    while j <= k do
error in line 6 - change to:    for i = 0 to n-2 do
error in line 7 - change to:    B(n - i + 1)

(2, 20%) The following are Postfix strings. All values are single decimal digits and the operations are binary add "+", binary subtract "-",and binary multiplication "*".

Indicate which are invalid, if any. For those that are valid, compute the result.

a) 9 4 + 2 3 * - 6 3 - 5 * + 7 - = 15

9 + 4 = 13 2 * 3 = 6 13 - 6 = 7 6 - 3 = 3 3 * 5 = 15 7 + 15 = 22 22 - 7 = 15

b) 8 3 2 4 * + - 7 8 2 3 * - + is invalid

There are not enough operators. 8 3 2 4 * + - gives the answer -3 and 7 8 2 3 * - + gives the answer 9, but there is no operator remaining to finish the calculation.

c) 3 2 + 4 2 * 7 5 - 2 3 * + - + = 5

3 + 2 = 5 (many of you did 3 * 2 = 6 here) 4 * 2 = 8 7 - 5 = 2 2 * 3 = 6 2 + 6 = 8 8 - 8 = 0 5 + 0 = 5

d) Given the following Postfix expression, show in the boxes below what the stack would contain immediately before the - operation is processed. Do not find the final result. Assume that the stack is initially empty.

2 6 + 5 3 2 * - 5 * +

The following operations are done before the - is reached:

2 is pushed onto the stack
6 is pushed onto the stack
when the + is read, 6 and 2 are popped from the stack and
the operation 2 + 6 = 8 is performed
the result, 8, is pushed onto the stack
5 is pushed onto the stack
3 is pushed onto the stack
2 is pushed onto the stack
when the * is read, 2 and 3 are popped from the stack and
the operation 3 * 2 = 6 is performed
the result, 6, is pushed onto the stack

The stack then contains the following items just before the - is processed:

(top of stack)

6

5

8

(3, 15%) The following insertion algorithm, Insert, must be invoked from the algorithm you are to write below. Assume that the variables j and x are local to the procedure and that k is an integer parameter.

Procedure Insert(k)

set j <- k

set x <- a[j]

while (j > 1) and (x < a[j-1]) do

set a[j] <- a[j-1]

set j <- j-1

set a[j] <- x

end

Write a recursive "InsertionSort" algorithm using Insert. You may assume a globally defined array a[1..n] of integer values that is already initialized.

procedure InsertionSort(n)

if (n > 1) then InsertionSort(n - 1) Insert(n) endif

endprocedure

(4, 20%) Find the closed form or exact value for each of the following: ( n is an arbitrary positive integer):

4a) å (3i+2) = (i ranges from 0 to n.) = 3n²/2 + 7n/2 + 2

å (3i+2) = å 3i + å 2 = 3å i + 2å 1
Since å i _{(i = 0 to n)} = (n(n+1))/2 and å 1 _{(i = 0 to n)} = n+1 then
å (3i+2) _{(i = 0 to n)} = 3(n(n+1))/2 + 2(n+1) = 3n²/2 + 7n/2 + 2

4b)   å (2i-3) =    (i ranges from 50 to 200.)   = 37297

å (2i-3) = å 2i - å 3 = 2å i - 3å 1
2å i _{(i = 50 to 200)} = 2å i _{(i = 1 to 200)} - 2å i _{(i = 1 to 49)} =
2( 200(201)/2 - 49(50)/2 ) = 200(201) - 49(50) = 40200 - 2450 = 37750 and
3å i _{(i = 50 to 200)} = 3å i _{(i = 1 to 200)} - 3å 1 _{(i = 1 to 49)} = 3( 200 - 49 ) = 3(151) = 453 and
37750 - 453 = 37297

4c)  S = 5 + 6 + 7 + 8 + … + (n-2) + (n-1)    = (n² - n)/2 - 10

S = 5 + 6 + 7 + 8 + … + (n-2) + (n-1) = å i _{(i = 5 to n-1)} =
å i _{(i = 1 to n)} - å i _{(i = 1 to 4)} - n = (n(n + 1))/2 - 4(4+1)/2 - n = (n² - n)/2 - 10

4d)   t(n) = t(n-1) + 2, where t(0) = 1    = 2n + 1

There are n + 1 terms in this recursive formula, n terms of the form t(n) = t(n-1) + 2 and one term where t(0) = 1. Since each of the terms from t(n) = t(n-1) + 2 to t(1) = t(0) + 2 adds the value 2 to the total, those terms sum to 2n. The t(0) = 1 term adds 1 to that sum, giving 2n + 1 as the final sum.

(5, 15%) Answer each of the following "timing" questions concerning an algorithm of a particular order and an instance of a particular size.
a) For an O(n) algorithm, an instance with n = 50 takes 4 seconds.
   How long will it take with n = 250?
(50/4) = (250/x) thus, x = 20
b) For an O(n³) algorithm, an instance with n = 30 takes 20 seconds.
   How long will it take when n = 60?
(30³/4) = (60³/x) thus, x = 160
c) For an O(2ⁿ) algorithm, an instance with n = 2 takes 12 seconds.
   How long will it take when n = 3?
(2²/12) = (2³/x) thus, x = 24
Or, 3 = 2 + 1 and anytime you increase the power of 2 by 1, it doubles the amount.
So, increasing n by 1 doubles the time.

(6, 5%) Given the following procedure, fill in the blanks below to show the order in which the values of x will be output if the procedure is called with Print_it(5).

procedure Print_it(x)
if (x = 1) then
print(x)
else
Print_it(x-1)
print(x)
endif
endprocedure

Show, in order, the output from executing the procedure:

If n = 1 is false, the procedure makes a recursive call to Print_it with the parameter (n - 1). It must then wait on the completion of that call before it can print its own number (n). If n = 1 is true, that "clone" of the procedure can print its number (which is 1) and does not make a recursive call to Print_it. Thus the recursion ends and Print_it(2) can print its number (which is 2) and end also. Then Print_it(3) gets to print, etc., until Print_it(5) prints and ends. So, the numbers are printed in the following order.
     1      2     3      4     5

(7, 10%) 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    P

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

Finding the closest pair in a list of n items    P

Search a list of n items for a given value    P

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

Back to the Oct 16 Foundation Exam page.

October 16th Foundation Exam

CS I Solutions

October 16^th Foundation Exam