concatenate string arrays - algorithm flowchart interpretation

Question

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

• Robert Harvey: 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.
• Edison: 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.

Answer 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 Z. n 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.)

• Edison: 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.
• Edison: 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?
• Erik Eidt: 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: 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!
• Edison: Awesome. Basically it was just their language that confused me then. Makes me feel much better. Great explanation. Thank you.