Mon, 10 Oct 2011, 06:08
I have received several emails from students who are still struggling with
Lab 1. In the interest of getting them started right away, I decided to send
this email. If you have completed lab 1, or are completely comfortable with it
and it is just a matter of a few tweaks to finish it, then feel free to stop
reading this email and move on.
If you are still having trouble getting started, then I hope the following
helps. I will also work another problem in class tomorrow, which I hope
will also help.
To construct a computer program to solve a problem, the first step is to
understand the problem you are being asked to solve! That may sound obvious,
but based on the way some students start by writing instructions before
understanding fully what is asked for suggests that it is not as obvious as
one would think.
Read the problem statement carefully, and restate it in your own words.
You can develop the algorithm for solving the problem by systematically
decomposing the problem statement into smaller statements as we discussed
in class last week and as is described in Chapter 6 of the textbook. Don't
concern yourself yet with writing instructions. That will come naturally
AFTER you have sufficiently decomposed the problem statement.
Step one looks like this:
Start
|
|
v
--------------------------
| Statement of the problem |
| in your own words. |
--------------------------
|
|
v
Stop
Recall from Wednesday's lecture (and Chapter 6) that we have three constructs
to replace the single block shown above with: sequential, conditional, and
iteration. For the Lab1 problem statement, we replace the block above with
three sequential blocks:
Start
|
|
v
----------
| | Initialize
| 1 |
| |
----------
|
|
v
----------
| | Which of the three makes sense?
| 2 |
| |
----------
|
|
v
----------
| | Store the result in x3101
| 3 |
| |
----------
|
|
v
Stop
Recall that "Initialize" consists of all that has to be done first, before
we begin the major work, which is the block labeled 2.
The next step is to decide which of the three to replace block 2 with. Ask
yourself: To solve this problem, which of the three makes the most sense.
If you think block 2 describes a conditional, replace block 2 with:
==========================================
|
|
V
/\
_______ / \_______
| \ ?/ |
--------- \/ ---------
| | | |
| a | | b |
| | | |
--------- ---------
| |
| |
|___________________|
|
|
|
|
For this to make sense, you need to identify a test that can have
exactly two answers. For one answer, you wish the computer to do what
is specified in block a. For the other answer, you wish the computer
to do what is specified in block b.
Example: Suppose you want to replace a 2's complement integer with its
absolute value. If the value is positive, you want to do nothing. If the
value is negative, you want to replace the value with the negative of the
value.
How would do that? The test is the most significant bit of the value.
So, before you test, you need to load the value into a register, thereby
setting the condition codes. Then, the test is simply examining the N
condition code. If N=0, block a: Do nothing. If N=1, block b: Replace
the value with the negative of that value.
...and you are done with the conditional.
If you think block 2 describes "iteration," replace block 2 with:
===========================================
|
|
--------->|
| |
| v
| / \
| / ? \_______
| \ / |
| \ / |
| | |
| | |
| v |
| --------- |
| | | |
| | a | |
| | | |
| --------- |
| | |
| | |
---------- |
|
_________|
|
|
v
For this to make sense, you need to identify an operation that needs to
be repeated a number of times. To do this, you must be able to do three
things:
Thing 1. Identify the operation that must be repeated. This is the first part
of block a.
Thing 2. Identify what bookkeeping is required in order to enable the program
to do Thing 1 again. This is the second part of block a.
Thing 3. Keep track of when you wish to stop doing Thing 1. This can be based
on keeping a counter if you know you want to do Thing 1 a fixed number of times.
Or, it can be based on a test that has nothing to do with a fixed number of
iterations.
Your job: Replace block 2 with either "conditional" or "iteration,"
depending on which makes sense.
Next step is to look at each of the blocks after replacing block 2, and
replace each block with either sequential, conditional, or iteration.
Keep doing this until the statement inside each block is easily identified
as an LC-3 instruction.
In class on Monday, we will work through another example doing exactly the
above.
I hope the above is helpful. If not yet, let's see what happens in class.
You still have until Tuesday night to finish Lab1.
Yale Patt