12/2/04

A student seems to be having trouble getting started. He writes:

     Dr. Patt,
     I'm working on my programming assignment
     and i can not figure out how to
     write the subroutine IS_OCCUPIED.  i am not
     sure how to check the exact
     spot on the game board to see if there is
     something in that spot.  Also, i
     couldn't figure out how to write the
     GET_ADDRESS subroutine.  How do i know
     which memory locations correspond to the places
     on the game board, or is it
     something i have to figure out on my own.  
     I tried to see if the questions
     i have were answered somewhere in part of the
     program that you wrote for us
     but i couldn't find it.  Also what is the game
     board data structure?  is
     that supposed to be a stack or something...
     thanks alot for any of your help.
     << name withheld >>

My first question to this student is the usual one: Have you visited a TA during office hours. Any of the ten TAs would be happy to get you started.

Since Friday is very close, I will be your TA tonight.

Let's start with the game board data structure: No, it is not a stack.

Why would you think "stack"? Is there ANYTHING about this problem that suggests a "stack" is appropriate? OR, is the REASON you say "stack" because the last DATA STRUCTURE we discussed in class was a STACK and since this is the last PROGRAM, it MUST be the case that the data structure is a STACK. Wrong! How do I get this kind of thing to stop, and thinking substituted?

Ok, end of rant, and moving on. The data structure is a collection of locations where what is relevant is which row and column we are talking about. We call this data structure an array.

How about getting out a sheet of paper and making a drawing of the game board. How many rows? How many locations in each row? How many total locations.

But memory does not have two dimensions. So the two-dimensional array occupies consecutive sequentially addressed locations. Look at the LC-3 starter code, in particular the "board game." Supposing the first location: Row 0, Column 0 was stored in memory location x5050. Label each Row i, Column j location with the memory address of that location. How many are there for this array?

Where would Row 0, Column 1 be stored? How about the last column of Row 2? If you know the address of the location that stores what Row 0, Column 0 corresponds to, can you figure out the address of every location corresponding to its Row i, Column j.

So, a two-dimensional array can be stored into memory locations with consecutive sequential addresses. Part of our job in this programming assignment is to figure out the ADDRESS of the memory location representing Row i, Column j, given that we know i and j.

Next question: What can we store in each location. Answer a symbol representing the value of that cell in the array. In other words, what can we store in Row i, Column j? Answer: depends on i and j.

So, let's be specific. What two things can we store in Row 0, Column 1. Hint: what are the two different things that can be in Row 0, Column 1? on our game board? What is in Row 0, Column 1 when we begin the game?

What is the only thing we store in Row 0, Column 0? What about Row 1, Column 4?

What about Row 1, Column 5? What are the three different things that can be stored there. So, if we load from the location representing Row i, Column j, what can we find out?

Summarizing: I think the first step in conquering this programming assignment is mastering this concept of how a 2-dimensional area is actually stored in memory, and how to go back and forth between the Row i, Column j, and the address of the memory location that stores its contents so one can examine those contents and take action accordingly.

Hope this helps.

Yale Patt