Solved

# concept check please

Posted on 2004-09-26

1. A stack can be used to permute numbers. For example, assume you have '1

2 3' as an input stream (reading from the right) into your stack. Assume

you can push or pop in any order at any time (with the restriction that

you cannot pop from an empty stack). Thus, if you push all three and

pop_top all three, your output is '1 2 3'. What are all the possible

permutations for output you can achieve for this input stream?

ANSWER: 5

321 312 231 213 123

The choices in this case are limited by the fact that you cannot execute

a pop on an empty stack and you cannot push from an empty input stream.

Thus allowable choices can be shown by using a binary decision tree.

<EXAMPLE>

PUSH

/ \

POP PUSH

/ / \

PUSH POP PUSH

/ \ / \ \

POP PUSH POP PUSH POP

/ \ / \ \

PUSH POP PUSH POP POP

| | | | |

POP POP POP POP POP

321 312 231 213 123

2. Prove by induction that for any n >= 1, 1^3 + 2^3 + 3^3 + ... + n^3 =

(1 + 2 + 3 + ... + n)^2.

Call this summation SUM3.

*1. Establish a base case: SUM3(1) = 1^3 = 1.

*2. Now assume SUM3 true for some k. Recall that we proved by induction

(in class) that 1 + 2 + 3 + ... + k = 2 | k(k+1) (meaning 2 divides

k(k+1) ) thus:

SUM3(k) = ( 2 | k(k+1) ) ^2

*3. Show that if true for k, true for k+1.

SUM3(k + 1) = ( 2 | k(k+1) ) ^2 + (k+1)^3

= ( 2 | k^2 + k ) ^2 + (k+1)^3

= ( 2 | k+1(k+2) ) ^2 = ( 2 | k^2 + 3k + 2) ^2

SUM3(k+1) = SUM3(k) + (k+1)^3

( 2 | k(k+1) ) ^2

3. Prove by induction that the sum 1 + 3 + 5 + 7 + ... + 2n-1 is n^2; e.g. // not sure on this one...please advise.

for n=3, 1 + 3 + 5 = 3^2

1 + 3 + 5 + ... + (2n - 1) = n^2

Assume true for sample n;

1 + 3 + 5 + ... + (2n - 1) - 2(n - 1) = (n - 1)^2

n^2 - 2(n - 1) = (n - 1)^2

n^2 - 2n + 2 - 1 = n^2 - 2n +1

n^2 - 2n + 1 = n^2 - 2n + 1

Since true for n + 1,..true for any n.