For problem 2b in exercise 2, should we use the floor or ceiling of the optimal jump size since optimal jump size=sqrt(n) and n=32? 5<sqrt(32)<6, so should we use 5 or 6?
The exercise states " Apply the algorithms exactly as presented in the lecture."
Now look at the slides where the optimal jump width is defined as m = ⌊√n⌋.
Now look at the slides where the optimal jump width is defined as m = ⌊√n⌋.
For problem 3, we should use INORDER-TREE-WALK(x) for the tree on slide 18 on lecture 3 notes but not use recursion. I however never get it to end without breaking before the next iteration in the big while loop when having two while loops here. Here is my code:
INORDER-TREE-WALK(x)
WHILE TRUE
S.push()
x=x.left
WHILE (x=NIL and S.top())
x=S.top()
print x.key
S.pop()
x=x.right
This means that the inner while loop runs as long as S.top() isn't empty but we still go out to the outer while-loop even after the inner ends and a break or end statement would end the program before we are done with the outer iterations, so how can we make it stop after it's done when we are only allowed to use pop, top and push?
INORDER-TREE-WALK(x)
WHILE TRUE
S.push()
x=x.left
WHILE (x=NIL and S.top())
x=S.top()
print x.key
S.pop()
x=x.right
This means that the inner while loop runs as long as S.top() isn't empty but we still go out to the outer while-loop even after the inner ends and a break or end statement would end the program before we are done with the outer iterations, so how can we make it stop after it's done when we are only allowed to use pop, top and push?
I think starting your loop with While True: might be the issue?
in essence, I do not grasp your algorithm, since it is not clear if you have two separated or nested WHILE loops. But as Kyle observed, you write "WHILE TRUE" which of course runs for ever, since you never updated the "TRUE" value. Where is this pseudo-code from?
Try to check if the stack is not empty in the outer while loop instead and you soon got it