Stuart Reges explains The Mystery of “b := (b = false)” — and a few other “powerhouse questions” on the computer science advanced placement exam:
Most multiple-choice questions on the exam had few significant correlations with other parts of the exam. But a small set of five questions had a nontrivial correlation with many parts of the test. One question in particular demonstrated such correlations. It asked about the effect of the assignment statement “b := (b = false)” for a boolean variable b. One interpretation of this data is that these questions are testing general programming aptitude.
[...]
Computer Science educators have for years complained that introductory courses seem to be divided between a group of students who “get it” and a group of students who do not. Donald Knuth has written about this phenomenon:
“Educators of computer science have repeatedly observed that only about 2 out of every 100 students enrolling in introductory programming classes really resonate with the subject and seem to be natural-born computer scientists…I conclude that roughly 2% of all people ‘think algorithmically,’ in the sense that they can reason rapidly about algorithmic processes.”[...]
It was an unpublished study conducted by Gerrit DeYoung in which he found that a measure of quantitative reasoning was not a predictor of success in a course for CS majors but was a reasonable predictor of success in a course for nonmajors. Knuth’s tentative conclusion was that there is some kind of CS aptitude that is not measured by standard tests of quantitative reasoning and that students who lacked that ability were instead relying on general quantitative aptitude.
[...]
What exactly do the powerhouse questions look like? Let’s explore question 23 in depth because it had the most nontrivial correlations. The exact text of the question is reproduced below:
23. If b is a Boolean variable, then the statement b := (b = false) has what effect?
(A) It causes a compile-time error message.
(B) It causes a run-time error message.
(C) It causes b to have value false regardless of its value just before the statement was executed.
(D) It always changes the value of b.
(E) It changes the value of b if and only if b had value true just before the statement was executed.Only 5.4% of the students skipped the question. Of those who answered, 60% got it right. And getting this question right turned out to be a predictor of success on most of the rest of the exam, including solving complex problems like reversing a linked list.
To answer this question correctly, a student has to be able to read the code and simulate its execution. They also have to be able to identify the correct answer among the given choices.
[...]
So what do the powerhouse questions have in common? They all involve reading and understanding code. They all test whether students have a proper mental model of program execution. And they involve some of the most central concepts from the first year programming course: logic, recursion and two-dimensional arrays.The author had the opportunity to present these results to a group of Stanford faculty, including the late Bob Floyd. Floyd, who had taught introductory programming many times, commented that the greatest single predictor he had noticed for success was whether students had a mental model of program execution, whether they could “play computer” in their head. He commented that these questions seemed to be very good at measuring that ability.
[...]
Knuth provides an intriguing intuition about this in talking about the difference between mathematical reasoning and algorithmic thinking:
“The other missing concept that seems to separate mathematicians from computer scientists is related to the ‘assignment operation’ :=, which changes values of quantities. More precisely, I would say that the missing concept is the dynamic notion of the state of a process. ‘How did I get here? What is true now? What should happen next if I’m going to get to the end?’ Changing states of affairs, or snapshots of a computation, seem to be intimately related to algorithms and algorithmic thinking.”Question 23 is about assignment for a boolean variable that requires thinking about its value before the assignment statement and what value it will have afterwards.