After going through the multimedia for Problem Solving Before Programming, you will start solving problems in Knobby's World. In lab, do the following non-written exercises from the book, given again below (you can bring them up in Netscape while you're in lab). Show a Teaching Apprentice that you've got at least as far as the last two exercises. Then go on to the homework exercises below.

Note: Knobby's World has been installed on the LAN. You may also download the most recent version of Knobby's World using a web browser, from the Knobby's World page under my web page. Download it to drive C:\, the root or top directory. After you've got it in C:, use winzip or (pkunzip -d knobby) to unarchive it into directory C:\umach. (You shouldn't need to do this if you are working in the lab or elsewhere on campus.)

Knobby's World laboratory exercises:

Exercise 2.53: Start up Knobby's World. By default, it should load the situation file mountain.sit. By using move and left, navigate Knobby to the other side of the mountain.

Exercise 2.54: How can you instruct Knobby to take three steps backward? When or why might you want Knobby to do this?

Exercise 2.55: How can you instruct Knobby to take three steps forward, pick up a character, and return to his original position?

Exercise 2.56: What happens if Knobby attempts to perform a write at the beginning of a task? Why? How can a Knobby program avoid this behavior?

Exercise 2.57: What happens when Knobby performs a read from a corner that appears not to have a character on it? How can you use this behavior to erase other characters?

Exercise 2.58: Now for some action! Press the reset button, so that Knobby is back where he started, ready to start a task. Knobby's goal is to pick up a copy of the flag, F', climb up to the top of the mountain (where it should find ^'), plant the new flag there, then climb down to the other side of the mountain. What problem solving strategy might you well use to solve this problem?

Exercise 2.59: There is no single command to copy a character from a corner one at 1st Street and 2nd Avenue, the other at 1st Street and 3rd Avenue.) How can he do that?

Exercise 2.60: Without actually doing it, what do you suppose would happen if you sent Knobby to the flag, had him read it, and then copied b2 into b1? Why? Now perform the experiment to see if your analysis was correct. (Don't forget to reset the world first.)

Exercise 2.61: Reset again. This time plant a copy of the flag on top of the mountain, then come back down and erase the (original) flag you've left at the bottom. How can Knobby "empty" board b1 in order to erase the flag? Hint: see exercise 2.59.

Exercise 2.64: Define instructions right and reverse. Then send Knobby through the task of planting a flag on a mountain, using your new instructions. (Remember, you perform a left or a move as before; you perform a right or a reverse by pressing E, then telling Knobby which new instruction to execute.)

Exercise 2.65: Now that you have used the defined instructions right and reverse, define a single new instruction for the complete flag-moving task. (Test it to make sure that it works correctly.) In what sort of circumstances might this new instruction be part of a solution to a still larger problem?

(Show an apprentice teacher that you have done and understand the above laboratory exercises, before going on to do the homework.)

Homework exercises,, in the textbook, The Universal Machine:

a) Do the following written exercises: 2.1, 2.5, 2.34 (but do the second chapter), 2.37, 2.47, 2.69 and 2.73. Use Notepad or another text editor to enter your answers into a file.

Write Knobby's World programs for exercises 2.76, 2.81 (do not use a while loop for this version), and 2.97. Instructions for handing in these programs are below.

Extra credit: 2.87 (here you get to try writing a while loop), 2.88, 2.91 (Knobby's World will let you let create and edit your own situation files--see the World menu) and 2.98 (take your pick!).

Due: Friday, 9/15, anytime before midnight.

Hand in: When you're ready to submit your assignment, using a web browser, go to The Student Drop Box for Introduction to Computing. (It's under Student Tools.) Click on the Browse button, then find your files in their folder (if you put it on a floppy disk, it's in A:). When you've selected your file, you should see a directory path to this file next to the Browse button. If it looks right to you, click on the Send File to Instructor button. Then you should see this file listed under Current Files in your DropBox. The Teaching Assistant, Jeff Eynon, will get this file and grade it.

If you have any questions about submitting assignments or grading, please send email with attachments to Jeff Eynon (jne3). (If you can't figure out how to use the Student Drop Box, you may just email the assignment to him.)

Hints:

Exercise 2.37 asks you to flesh out the algorithm--i.e., the algorithm on the bottom of the preceding page, p. 46, by providing the pseudocode where you see the ellipses (. . .).

Exercise 2.47 is similar to exercise 2.45, which defines a class for Squares:
A Square's properties (attributes it possesses) include the length of one side, a real number.
A Square's behaviors (things it does) include computing its area, perimeter, diagonal, drawing and moving itself, etc.
A Square class could either be a subclass of Rectangle or Polygon, depending on whether you want to take a pure mathematical view. (The multimedia, which discusses and object-orientation and the Square example at the end of the problem solving unit.)

Exercise 2.69 and 2.73 involves interpreting syntax diagrams. A syntax diagram is hard to explain in words; if you get into the "UM" multimedia, then use the "find" button and enter "syntax diagram", you'll find a dynamic explanation which should be helpful. But in words, you trace a diagram by following the arrows through the boxes. If the box is an oval, then it's a token, which must correspond to a token in the program. If it's a square, then it's a non-terminal symbol, which must be expanded by another syntax diagram (rule). For example, the syntax diagram for define-instruction (on p. 60) starts with the name of the diagram (define-instruction), followed by an arrow pointing to the token "define", followed by an arrow pointing to the non-terminal symbol "instruction-name", which is defined by another syntax diagram on p. 61. In this diagram, the first non-terminal is a "letter" (see the syntax diagram below on this page), which may be followed by zero or more letters or digits. Zero is possible since the arrow out of "letter" can exit the diagram. Alternatively, another arrow branches down to either another "letter" or a "digit", both of which have arrows that lead back up to the main arrow, before the arrow branching back down to "letter" or "arrow" (hence zero or more letters or digits). Once you are done with the instruction-name, you return back to the "define-instruction" diagram, where the NEXT token is "as", followed by another non-terminal "compound-instruction", which is expanded by another syntax diagram on p. 60.

Exercise 2.73 only considers instruction-names, so all you need to do is figure out what is allowed starting with this diagram. A string is NOT a valid instruction-name if it cannot be recognized by the diagrams that define a well-formed instruction-name. For example, my email address, gdb0@lehigh.edu, is not a well-formed instruction-name. It starts out OK, with a letter, followed by two more letters, followed by a digit (0), but then there's an '@' character, which is not allowed by the rules for instruction-name.

Exercise 2.76 assumes that you use the initial world situation in file morning.sit. (Under the World menu option, select Load, then double click on file morning.sit.) On the CD-ROM, the "paper" is a "P" rather than an "N" as described in the book. No big deal, but it's now an "N" on the LAN. To create your program, you could copy one of the other Knobby's World programs (ending with extension .kno) to another name, e.g.

      C:\umach>copy square.kno morning.kno

Then load it into Knobby's World (under the Program menu, select Load, then double click on morning.kno), then edit it (under the Program menu, select Edit, then mouse click on the editor window on the right). Use decomposition to break this problem down into smaller pieces that can be defined as instructions, which get called by the top level main instruction or other instructions. Try creating a few utility instructions, such as turning right, or moving a particular number of squares. Comment your code!

Exercise 2.81 only requires that you get Knobby to jump the hurdles set up in hurdle.sit. Any generalizations are best saved for exercise the extra credit exercises 2.87 and 2.88, which require that you use while loops to generalize your solution for this problem using loops. If your program allows Knobby to jump any SIZE hurdle, you might want to demonstrate this by setting up another situation file. Extra credit for this--but make sure this is documented!

Exercise 2.97 only requires that you write a program that adds 3+4, not any two numbers. (Any two numbers is covered in exercise 2.98, which is extra credit.) I provide adder23.sit, which sets up the 2+3 problem (two X's, space, then four X's) for 2.96 adder34.sit, which sets up the 3+4 problem (three X's, space, then four X's) for 2.97, on my web page.

Regarding Knobby's World programming, a student asks: > How can you break an infinite loop? My program was stuck in > an infinite loop and the only way I could stop it was to quit > the program. Thanks.
Apparently Knobby's World doesn't respond to ctrl-c or ctrl-break, as I had suggested in class. Here's what works: press ctrl-alt-del (hold down the Ctrl key, then hold down the Alt key, then press the Del key). Windows will bring up a list of tasks. Click on Knobby's World, then click on end task. This may not work right away if you're in a "tight" (fast) loop, so you may have to wait or do this more than once. BTW, this is how you can kill any task that's not behaving well, under Windows 95.

Prof. Blank