Foundation Exam - August 17, 1999

Computer Science Foundation Exam

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)

`Array X`	`4`	`5`	`2`	`3`	`4`	`3`	`3`	`1`
`position`	`1`	`2`	`3`	`4`	`5`	`6`	`7`	`8`

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

2

3

6

A

1

-2

6

B

3

-5

6

C

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

4

3

2

1

A

5

-13

B

4

-13

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  /  +  -        Invalid

Wrong number of operands

   d)  3  2  5  -  +  *  6  2  1  +  *           Invalid

The first multiply operation only has 1 number to act upon.

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

n = 2

16 sec

(3³ / 54) = (2³ / x)
(27 / 54) = (8 / x)
(1 / 2) = (8 / x)
x = 16

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

n = 8

(12 / 21) = (x / 14)
(4 / 7) = (x / 14)
7*x = 14*4
x = 8

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.

n = 64 sec

(log₂(x) / 36) = (log₂(16) / 24)
(log₂(x) / 36) = (4 / 24) = (1 / 6)
6*log₂x = 36
log₂x = 6
x = 64

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? O(n²)

e) What will be the value of x when the for loops end? 2*(2n)(n+2)

(4, 10%) The factorial function (n!) is defined as the product of the sequential terms from 1 to n, with 0! = 1, i.e. n! = 1 * 2 * 3 * ... * (n-1) * n. Assume that the value of n was already initialized and that the factorial function will be called as shown:

x <- Factorial(n)

In the space below, write a RECURSIVE algorithm that correctly finds n!.

Factorial(n)

There are several ways to do this, but the following is one common solution:

         Factorial(n)
      
            if n <= 1 then
               return 1
            else
               return Factorial(n-1) * 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² + 9n)/2

å (3i+3) = å 3i + å 3 = 3å i + 3å 1

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² + 3n)/2 + 6n/2 = (3n² + 9n)/2

b) å (4i - 3) (where i ranges from 30 to 80) = 11067

å (4i-3) = å 4i - å 3 = 4å i - 3å 1

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(n-2) + 2(n-1)= n² - n

S = 2(1 + 2 + 3 + 4 + … + (n-2) + (n-1)) = 2å i _{(i = 1 to (n-1))} =
2(å i _{(i = 1 to n)} - n)= 2(n² + n)/2 - 2n = n² + n - 2n = n² - n

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

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) = 3. To solve, you must substitute values for each n in the equations. In other words, when you have n = 2, you replace each instance of n with 2 giving t(2) = t(2-1) + 2 which equals t(2) = t(1) + 2. Since each of the n terms from t(1) = t(0) + 2 to t(n) = t(n-1) + 2 adds the value 2 to the previous sum, we know that the sum of those n terms will be 2n. The t(0) = 3 term adds 3 to that sum, giving 2n + 3 as the final sum.

(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

3! = 3 * 2 * 1 = 6
3² = 9
since 6 < 9, 3! < 3²

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

the O(n!) algorithm

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² = 100
since 3628800 is much larger than 100, we can be pretty sure that n! > n² 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?

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

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