Foundation Exam - CS I Section

October 16^th Foundation Exam

CS I Questions

(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).

(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 - ___________________________

b) 8 3 2 4 * + - 7 8 2 3 * - + ________________________

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

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

(top of stack)

(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.

(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.) _______________________

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

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

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

(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?     ____________________

b) For an O(n³) algorithm, an instance with n = 30 takes 20 seconds.

   How long will it take when n = 60?     ____________________

c) For an O(2ⁿ) algorithm, an instance with n = 2 takes 12 seconds.

   How long will it take when n = 3?     ____________________

(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:

     ___________      ___________      ___________      ___________      ___________

(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 _________________

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 _________________

Finding the closest pair in a list of n items _________________

Search a list of n items for a given value _________________

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 _________________

Solutions to the CSI questions.

October 16th Foundation Exam

CS I Questions

October 16^th Foundation Exam