Discussion Forum

Hw2 Q5 Clarrification on instructions vs pseudo code.

Hw2 Q5 Clarrification on instructions vs pseudo code.

by Kyle Aidan Tenn -
Number of replies: 4

Hey,

In the q5 it states about the algo: "This process continues until either the stack or the queue is empty."

But in the pseduocode it has for the looping iteration:

"WHILE (Q and S are not empty) DO" (bold is my own emphasis.)

So either should we refer to the pseudo code that states a requirement of both stack AND queue being empty, or should we refer to the writing which states an "either or" clause (in this case a logically exclusive or?).  

Since for question 5c, it is asking us for worse case O complexity for a program that terminates, but it also states the "input" is number of elements S + number of elements Q.

Then either:

option 1? The S and Q are uneven they would only terminate with the written instructions and not with the "WHILE AND" pseduocode instructions. So based on the written instructions, the termination complexity does not really entirely depend on the "input" N=S+Q, but more like the "smaller" of the two arrays. So the input is "S", or "Q" whichever seems shorter.

option 2? Or if S and Q are an even amount and terminate both instructions seem valid... Then the "input" does not really rely on N, since N=S+Q. But more like the sum of the lengths of the arrays divided by two, or (S+Q)/2 or "S" or "Q" since S=Q.

  1. So which interpretation of the code should we follow? Written? Psudocode?
  2. Given we need to treat N inputs to do the O complexity analysis, per the instruction are we allowed to substitute N size for simply S or Q length?

In reply to Kyle Aidan Tenn

Re: Hw2 Q5 Clarrification on instructions vs pseudo code.

by David Polos -
"Q and S are not empty" is the same as "Q is not empty and S is not empty" and the negation is actually "Q is empty or S is empty". See De Morgan's laws. It would be consistent with the preamble if the 'or' there wasn't exclusive but inclusive, which I think was the intention. Otherwise part (b) wouldn't make much sense. This is my interpretation and what I went with at least.

As for substituting N for S or Q (|S| or |Q|), you say that it seems to depend on (S+Q)/2, but if this is the case then you can express it in terms of N since N = Q + S so N/2 = (Q+S)/2. You also say that the input seems to depend on whichever is smaller, S or Q, i.e min(|S|,|Q|). In the worst case we are maximizing the running time of the algorithm which may have min(|S|,|Q|) depend on N. We are not trying to find the worst case running time given S and Q but rather given N.

This is just my take as a student, hope it helps.
In reply to David Polos

Re: Hw2 Q5 Clarrification on instructions vs pseudo code.

by Kyle Aidan Tenn -

for the first point hmmm i think i followed, I see the phrasing of having the negation at the end i guess is what caused me to miss this.

for the second, we are trying to find the worse case. But I guess what I am confused here, is that the worst case, or best case, in general depend on the smaller S or Q. So I guess what you're saying is you can get a worse run time just by increasing the larger set even larger is what you're saying? Which I guess is in other words increasing N?  I guess since N is a function of two inputs what I'm looking for is the derivative in respect to S or Q and thats what makes it unclear for me to parse. But is this similar to what you are thinking about?

In reply to Kyle Aidan Tenn

Re: Hw2 Q5 Clarrification on instructions vs pseudo code.

by David Polos -
I think it is better if you think of N as fixed. If N = n how many steps does it take for the algorithm to terminate? Say this depends on min(S,Q). Note that 0 \leq min(S,Q) \leq n/2 so it is restricted by n, but that restriction changes as n changes. Can you express the running time in terms of min(S,Q)? If so then you might be able to decide what value of min(S,Q) maximizes the running time, and this value might depend on n.

You are in some sense given n and can choose S and Q. Consider the best case for the algorithm. If N = n then the best case is that S = n and Q = 0 or S = 0 and Q = n, since the loop is never run so the algorithm runs in constant time for all n. 

Another example is, say the running time for some algorithm is T(n) = x and we restrict x such that 1 \leq x \leq n. Then the worst case running time for this algorithm is when x is chosen such that T(n) is maximized, and we can see that it happens when x=n. That is, the worst case running time is T(n) = n. We can also see that the best case is when x = 1. Here x may be seen as the length of some list.
In reply to David Polos

Sv: Re: Hw2 Q5 Clarrification on instructions vs pseudo code.

by Marc Hellmuth -
hi,

thanks for the question and I agree here with David.

In English, "either … or" is not always exclusive and depends on the context. In our case (as negation of ".. AND ..") it is inclusive, listing possibilities rather than forcing a single choice.

For the runtime: n = |S| + |Q|. Note that you have determined in (a) necessary and sufficient condition for S and Q so that the program terminates. Maybe this helps? One may ask (but this is only one of many ways), what is the runtime depending on one of |Q| resp |S| and then ask for which |S|, resp, |Q| get the runtime maximized. But this is only one of many ways.