11/22/2006

I do not want you to interrupt your Thanksgiving holiday, but when you
get back to work, I thought I would share this question and my response
to Problem 5 on the exam.

A student writes:

Dr. Patt,

I've been reviewing the past exam, trying to figure out why I didn't
perform better, so I can fill the holes in my understanding.

On most of the problems I missed, I am not too worried.  I usually ran
into trouble trying to execute code without the LC-3 Simulator.  The
system I was using forced me to track too much in my head and not enough
on the page.  While it worked on the problem sets, under the pressure of
an examination I became quite accident prone.  I've worked out a better
system for working on those kinds of exam questions.  So problem 
solved on one front.

What really concerns me is a question like Problem 5.  I simply couldn't
figure out what the second two instructions were.  I talked to a 
friend in class about the problem, and I now know the solution.  
I've worked through
the program and the solution makes sense.  However, I still have no idea
how I would solve a similar problem in the future.  It seems like such
problems can easilly depend on a fair amount of cleverness.  Often, I'm
having a clever day and will find a solution, but some days (sometimes
exam day) I don't feel terribly clever at all.  I don't know how 
to study for such a problem.  Are there some basic strategies I 
could use to approach similar questions in the future?  Or is there 
at least a good approach to laying out such problems so they can be 
viewed from more than one angle if it is not readilly apparent what 
the solution is?

Any advice you could give me would be deeply appreciated.

Yours,
<<name withheld to protect the student looking for insights into #5>>

Your question about problem 5 is an excellent one.  In fact, I felt that
it was by far the hardest problem on the test.  I was surprised that more
people missed the last problem than missed problem 5.

On all the other problems, if you had a strong foundation in the material
of the course, you should do fine.  Each can be solved in a very straightforward
way.  In fact, I was disappointed that so many students did not get a large 
fraction of those 80 points.

Problem 5 was another matter.  But it is important to have one on the exam
since we need to test whether you understand the transformation from problem
statement to actual program.  

The best way to handle such a problem, in my view, is to first understand 
the application the exam is asking about, perhaps write a flow chart for 
its solution.  Then move to the existing code, and try to see whether it 
fits the flowchart.  If yes, then it is a short step to fill in what must 
be the missing instructions.

But since there are many solutions to a programming problem, your flowchart
might not initially correspond to the existing code.  At that point, it is
a good idea to look at the code and try to figure out what must be going on.

In problem 5 on the test, there were three blanks to fill in.

The first one, we all agree was obvious.  In order to have R2=x0001 after
adding 1 to R2, what must R2 contain, and how do we ensure that?

The second and third were less easy.

You note that the third instruction is making a test, and based on that
test, either you are adding R3 to R0 or you are not adding R3 to R0 before
terminating.  Since R0 (at the end) must contain the sign-extended value
in R0, you ask yourself what must R3 contain.  It may not be obvious, but
after a little thought, one might think, "Aha!  R0 starts with the zero
extended value, and at the end contains the sign-extended value."  Perhaps
R3 contains leading 1s to add to R0 in case we need sign-extended.  What
determines whether to zero-extend or one-extend?  Answer: whether the first
1/0 entered was a 0 or a 1. 

You note that the loop starts with R1 = the number of 0s/1s entered from
the keyboard, and systematically subtracts 1 and left shifts the non-zero
bit in R2 until R1=0.  You should guess at that point that the 1 in R2 is
lined up with the first 1/0 entered.

So, what instruction will determine whether to add leading 1s or not?
Looks like you want to AND R2 with R0.

You still need to generate the leading 1s in R3. You note that before 
entering the loop, R2 has a 1 in bit[0] and 0s everywhere else, and R3 has a 0 in
bit[0] and 1s in all bit positions to the left of that 0.  When you exit the loop,
you need R3 to have leading 1s in all bit positions
to the left of the bit position that R2 has a 1 in.  How to do that in the
one (second) missing instruction.  "Aha!  Shift R3 one bit position to the 
left each time I shift R2 one bit position to the left.  The result: 
ADD R3,R3,R3.

Was the above trivial?  Of course not.  How did I figure it out?  I looked
at the existing code, and figured out what was going on based on what I knew.
Given that, and knowing what the program must do, I systematically pieced
together what must going on in each of the three instructions to make that
happen.

I hope the above helps.  You will probably have another one of these on the
final exam.  ...and solving it will probably take a substantial piece of
time.  But I believe it is not beyond you, if you approach it in the
above systematic way:

1. What do I know about the problem.
2. How would I write a program to solve it.
3. Does my flow chart match the code?  If yes, fill in the missing pieces.
4. If not, study the code as best you can.
5. Match stuff in the code to what must be going on.
6. Systematically deduce what must the missing instructions be in order 
   to have it work.

Hope the above helps.
Yale Patt