algorithm 1. stackstuff(n) input: integer n 1) let s = empty stack 2) let x = -1 3) = 1 2n 4) s.push(i) 5) end 6) = 1 n 7) let x = s.pop() 8) end output: contents of x 1) algorithm written in pseudo code doing? to understanding, s.push(i) adds item on top of stack s. x = s.pop() removes item top of stack s , assigns x.
2) computational complexity o(n) algorithm 1, stackstuff? i believe answer be: o(3n)
the first loop 2n , second loop n, 2n+n=3n.
or... answer o(n^2) since have n*n?
3) if n > 0 returned algorithm? n < 1 a) 2n b) -1 c) n-1 d) n+1 e) none of above this last bit confuses me. understanding, if n greater 0, algorithm return n+1, , if n less 1, algorithm return n-1. pure guess work...
if thought logically, let's n 3 example. since first loop 1 2n, mean end following stack s={1,2,3,4,5,6} added every number double n s. second loop pops 3 numbers x ends looking x={6,5,4}. if correct there... should assume trick question , answer e, none of above?
i wanted make sure understanding here correct before continued studying. help.
1) algoritm adds 1..2n stack, pops n elements. meaning 1..n left in stack , last popped element remains in x.
2) correct. algoritm has complexity: 2 + (2n * 1) + (n * 1) = 3n + 2 = o(3n) = o(n).
3) algoritm storing last popped element in x , returning x , last popped element n + 1, answer should d) n+1.
edit
explanation on 3:
if n > 0:
x := -1 push 2n stack stack = {1, 2, .. n, n + 1, ..., 2n} pop n elements stack , store popped element in x first iteration: x := stack.pop() stack = {1, 2, .. n, n + 1, ..., 2n - 1} x = 2n ... until have popen n numbers. stack = {1, 2, .. n} x = n + 1 if n < 1
x := -1 because n < 1 won't iterations in loops x not change , still -1 
Comments
Post a Comment