Articles – Page 2 – The Renegade Coder

Today, I'm kicking off a series of new articles that take a look at real computer science multiple choice questions and attempt to give some tips for solving them. Right now, I want to start by talking about loops and how to trace them. Let's get into it! Multiple Choice Question What value does `x` have at the end of the following loop? int x = 0; int i = 1; while (i < 5) { x += i; i++; } Select one of the following: A. 15B. 10C. 1D. 16 Problem Solution As with any multiple choice question, there are multiple ways to go about solving it. For this problem, I would actually recommend tracing the loop before trying any of the usual multiple choice tricks. There are plenty of ways to go about tracing, but the following is the approach I use with my students: StatementState`int x = 0;`x = 0`int i = 1;`x = 0i = 1`while (i < 5) {`x = 0, 1, 3, 6i = 1, 2, 3, 4`x += i;`x = 1, 3, 6, 10i = 1, 2, 3, 4`i++;`x = 1, 3, 6, 10i = 2, 3, 4, 5`}`x = 10i = 5 If you've never seen a table like this (and perhaps I'll write an article on how to make them), the idea is that we have each line of the program in every other row of the "statement" column of the table. Alternating rows with each statement is the "state" of the program. In other words, when a line of code is executed, we report the change in state in the other column. Things get a bit more complicated when statements are executed multiple times—such as in loops. That said, the idea remains. Every time state changes, we update it. To be extra clear, we cross out old values. If you follow through the entire trace, you'll find that `x` is 10 when the code finishes executing. Alternative Problem Solving Techniques Let's say for a second that you didn't know how to trace this loop. Could you still solve this problem? I'd like to think you could. My usual approach is to use process of elimination. In other words, which answers are unlikely? To do that, we'd need to think about everything that we know. For example, we know that `x` starts at 0 and `i` starts at 1. Unfortunately, this information alone doesn't really help us eliminate any answers. If we dig into the loop a bit, we can uncover some more information. For example, we know that `i` will eventually be 5 or greater. Otherwise, the loop won't terminate. On top of that, we know that `i` increments in steps of 1 (i.e., `i++`), so we can actually predict the whole sequence of values for `i`: 1, 2, 3, 4, 5. If we know the entire sequence for `i`, then we can begin to make some guesses about the final value of `x`. Specifically, we know that `x` depends on `i` from the statement `x += i`. If we think about it, `x` is really just the sum of the sequence of `i`. Therefore, any of the following answers could be possible values of `x`: 1, 3 (i.e., 1 + 2), 6 (i.e. 3 + 3), 10 (i.e., 6 + 4), or 15 (i.e., 10 + 5). Because 16 is not in this list, we can eliminate D (i.e., `x = 16`). The final step is to then figure out which subset of the sequence of `i` makes up the sum of `x`. This requires a bit more reasoning than the previous work, but it can be done. If we look at the initial values of `x` and `i`, they're 0 and 1, respectively. Because the summation line happens before `i` increments, we know that the first value of `i` we add is 1. Therefore, we just need to figure out the last term that is added. Again, because summation happens before the increment happens, we can conclude that the last value of `i` is never added. As a result, the final sequence is: 1, 2, 3, 4. When summed together, we get a value of 10. There are probably other ways to reason about this code without actually tracing it, but I find tracing to be easiest. For loops with hundreds of iterations, a process like this may be more reasonable. That said, it's still probably easier to trace a few terms and extrapolate the sequence than it is to try to reason about what the loop is doing. Regardless, I thought it would be fun to try approaching this problem from multiple perspectives. Happy Learning I figured I'd start this series off with a light looping problem. Perhaps as we go through the series, we'll dig through more complex problems. That said, let's call it a day. As mentioned once already, if you liked this article and would like to see more like it, consider showing your support. Alternatively, you can check out some of these related articles: How to Swap Java Reference Types in a MethodBeware of Division by Zero in JavaThe Remainder Operator Works on Doubles in Java Otherwise, take care! See you next time.