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