0

I would like help interpreting this flowchart. I don't know what k means even though they say what it represents in the question.

I can quickly see that since dimension m corresponds to variable X that the first loop has to be iterating on X. Therefore A has to be X(k) → Z(k).

Since I know the first loop is on X, obviously the second loop is on Y. Therefore B is Y(k) → Z(?+k).

Where I get stuck is choosing (m+k) or (n+k). What exactly does k represent?
The question says that variable k varies from 1 to m by 1.

m is the number of elements in the array (the dimension).
k is the iterator?
variable k varies from 1 to m by 1means that k varies from 1 element to m elements right?
I know the answer is (m+k) but why isn't it (n+k)?

If possible could you please explain it in both C & Java using the same variable names? Thank you.


enter image description here

  • The note to the right of the flowchart says that variable K varies by 1 to m in loop two (just like loop 1), but that's not entirely true; it varies by 1 to n. – Robert Harvey Aug 7 at 20:17
  • I thought the same thing. It's just their wording. They mean to say that just like Loop 1 varies by m, Loop 2 varies by n. – tem Aug 7 at 20:22
1

Let's decouple, a bit, the iteration ranges (e.g. for loop control variable k) and what they are iterating over.

Technically, the loop control variable(s) iterate over a range of integers, e.g. 1..m or 1..n (rather than over elements of the arrays).

So, a loop, via its loop control variable, nominally iterates over a range of integers, not necessarily elements of an array, though it can be used to iterate through array elements, within the body of the loop, by using subscripting/indexing expressions like X(k) and Z(k) in terms of the loop control variable.

What exactly does k represent?

There is no reason that the question has to have used the same variable name, k, for both for-loops — but because it does use k twice (rather than, say, k1 first loop and k2 later), k means two different things in two different places.  In Loop 1 k is an index ranging from 1 to m, which is the range of X, and in Loop 2, k is an index ranging from 1 to n, which is the range of Y.

m is the number of elements in the array (the dimension)

Specifically, in the array X — whereas n is the number in Y.

You already realize that the concatenation operation is concatenating X with Y not vice versa.  Loop 1 then merely copies X into (the first part of) Z, character by character, and thus at each k, a copy from X into the same position in Z.

Next, Loop 2 copies Y into Z — but where to place the elements in Z, given that X has already been copied into Z?

In words, the answer is that the copy of (concatenation of) Y should go after the copy of X in Z.

In variables, that translates such that the first element of Y should go to the Z position at m because m is (firstly) the length of X, and also (secondly), it is where Loop 1 left off/stopped in Z — in other words, just after loop 1 finishes, m identifies the boundary between the last position used and the first free position in Z.  Since we want to copy the whole of Y into Z, then all the characters of Y come from k but go to m + k in Z.

So, to recap, m is not only the size of X, but also where Loop 1 finished copying into Zn is merely the size of Y.  Note that X's copy in Z after Loop 1 now occupies Z(1..m), so then, the location where we want Y(1) to go is Z(m + 1), Y(2) to Z(m + 2), and so on, so that characters of Y are all placed after the entire copy of X in Z.

The copy of X in Z occupies Z(1..m) and the copy of Y in Z occupies Z(m..m+n), which is saying that the copy of X's comes first and the copy of Y comes directly after the copy of X.

(If you work through a real example, e.g. concatenate "hi " with "world", you'll see how this comes together.)

  • Thanks for your answer. I already understand how the algo works, but didn't get what k was doing since I'm not actually seeing it in code. I'm not a CS student so often if I don't see it in code, I think of it as a trick question lol. I guess I already correctly guessed what k was. k is the iteration index position so basically after all m elements are added to Z, n elements get added according to k position? Is that correct? And n has no purpose anymore since it's just the dimension of Y. – tem Aug 7 at 22:45
  • So in my experience a loop control variable is often i. Of course it can be anything but i seems to be most prevalent at least in my web/mobile world. This question mentions the i-th character and i-th element which to me seems like they're using i as the loop control variable. Why did they use k instead of i in the loop flowchart? Is k often used in flowcharts to represent i in code? – tem Aug 7 at 23:24
  • 1. Yes, that is correct. As I mentioned, it is unnecessarily confusing to use k twice for both loop 1 & 2: they could have used i for loop 1 and j for loop 2 and that might have been easier to follow. However to be clear, it is common practice especially in older code to reuse a variable when the two usages don't conflict. In newer code, k might have the same name but actually be two separate variables, one each in the context of the separate loops. – Erik Eidt Aug 7 at 23:48
  • 2. I can't explain why they choose k. It is common since the days of Fortran in the ~50's, ~60's and ~70's, to use integer (index) variables named i, j, k. This is also common in math & logic, and they are evoking this in their description of i-th element (e.g. forall i : if i < m then X[i] == Z[i]). They could have used k there as well, but for some reason didn't! – Erik Eidt Aug 7 at 23:51
  • Awesome. Basically it was just their language that confused me then. Makes me feel much better. Great explanation. Thank you. – tem Aug 7 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.