Problem Set 5B Frequently Asked Questions

Q: The problem states that expressions must be generated in prefix order, but the examples appear to contradict this. What is going on?

A: Several questions have been raised about the ordering of expressions in the CSE problem. The text states that the expressions should be generated in prefix order, but the examples seem to violate this requirement.
The expressions are indeed generated in prefix order, and they are collected into a list. Since it is easier to prepend expressions to a list than to append them we chose the former method to collect expressions into a list; we end up with the expressions in a kind of "reverse prefix order." A note explaining this quirk was present in one of the earlier drafts of the text but it was left out of a final edit.
Of course, we could have reversed the list of expressions at the end. The method we chose, however, places more complex expressions (those encountered higher up in the tree) toward the right end of the list of expressions; this structure improves performance in the later parts of the problem.