CS 1044
Spring 1999

Assignment 1: Problems and Programming
Due Date: Monday, February 8


Problems: (pages refer to the textbook by Dale, Weems & Headington)

#1 page 54 no. 2 - see page 24 for description of Syntax Templates

#2 page 54 no. 4

#3 page 55 no. 5

#4 Robbie the Robot:

Robbie the Robot is touring New Orleans and has discovered that an excellent oyster po-boy can be found at the Acme Oyster House in the French Quarter as shown below on 2nd Avenue at point Y. Currently he is standing a point X on A Street. Some of the street segments are one-way as indicated, but the two segments with ?-marks are both either 1-way east or 1-way west, depending upon traffic conditions and do not change during the course of a single trip from X to Y or from Y to X.

Robbie also has 9 friends with him at point X, and his job is to get a po-boy for each of his friends and return to point X to dine with them. He can only carry one meal at a time, which is of no consequence, since Robbie is, of course, only a robot. However, Robbie is to travel the shortest distance possible, considering the state of the one-way streets as he travels. On one trip he may be able to move east on 2nd Avenue, while on another he may have to take another route.

Your job is to present Robbie's task as a formal algorithm.

Robotspeak

Robbie will move one block at a time when given one of the commands, NORTH;, EAST;, SOUTH;, or WEST;. For example, to get from point X to point Z simply requires the commands, NORTH;, and then WEST;. We can make more complicated commands by enclosing component commands in braces, as in {NORTH; WEST;}. Robbie can make decisions, too, using a function called LEGAL. For example, at some point he wants to know if it is legal to go west a block from where he is, so he can look at the value of LEGAL (WEST), which is YES if it is legal to go west and NO if it is not. In an algorithm one would write IF LEGAL (WEST) {Commands} to perform {Commands} only if it was legal to move west. One could also write IF LEGAL (WEST) {Commands 1} ELSE {Commands 2} if one wanted to perform different commands, depending on whether a move west was legal. Finally, there is a REPEAT command, in case one wanted to repeat a group of commands several times. For example, REPEAT (5) {commands} would repeat {commands} five times.

A formal algorithm is written ALGORITHM (Name) {commands}, and in an algorithm we write lots of comments (lines beginning with an !) so that humans can figure out what is going on at any point in the algorighm. For example, if Robbie wants to take a walk around Acme from point X one could write,

   ALGORITHM (Circle Walk)

   ! This algorithm describes what Robbie does to take a walk around his favorite
   ! restaurant at point Y, starting with a southward move from point X.

   ! Move down to 1st Avenue.

     {SOUTH;
   
   ! Can't go up C Street since it's one-way in the wrong direction.

      REPEAT (3)
        {EAST;
        };

   ! Now continue north, then west, and then south back to the starting
   ! point.

     REPEAT (2)
       {NORTH;
       };
     REPEAT (3)
       {WEST;
       };
     REPEAT (2)
       {SOUTH;
       };
     }
Notice the consistent use of indentation, punctuation, blank lines, comments, and other documentation to make the formal algorithm into an unambiguous statement of what Robbie does to accomplish the assigned task.

U-Turn Example

Program:

In order for you to gain experience using your editor, compiler and operating system, type in the following program:
//******************************************************************
// Mileage program
// This program computes miles per gallon given four amounts
// for gallons used, and starting and ending mileage
//
// <TYPE YOUR NAME HERE>
//******************************************************************
#include <fstream.h>

const float AMT1 = 11.7;           // Number of gallons for fillup 1
const float AMT2 = 14.3;           // Number of gallons for fillup 2
const float AMT3 = 12.2;           // Number of gallons for fillup 3
const float AMT4 = 8.5;            // Number of gallons for fillup 4
const float START_MILES = 67308.0; // Starting mileage
const float END_MILES = 68750.5;   // Ending mileage

int main()
{
    float mpg;           // Computed miles per gallon
    ofstream outputFile; // File containing output data

    outputFile.open("hw1.out");
    mpg = (END_MILES - START_MILES) / (AMT1 + AMT2 + AMT3 + AMT4);

    outputFile << "For the gallon amounts " << endl;
    outputFile << AMT1 << ' ' << AMT2 << ' '
               << AMT3 << ' ' << AMT4 << endl;
    outputFile << "and a starting mileage of " << START_MILES << endl;
    outputFile << "and an ending mileage of " << END_MILES << endl;
    outputFile << "the mileage per gallon is " << mpg << endl;

    outputFile.close();
    return 0;
}
The output from this program is:
For the gallon amounts 
11.7 14.3 12.2 8.5
and a starting mileage of 67308
and an ending mileage of 68750.5
the mileage per gallon is 30.8887

Correct any syntax errors or typing errors you make. Compile and execute the program until it executes correctly. All documentation (the lines beginning with //) must be typed as well. Refer to slide 2.5 for Microsoft Visual C++ help instructions.

Grading:

Turn in hard copies of the problem solutions (typed or neatly handwritten) along with the source code and the output results for the program. The program creates the output results in a file named hw1.out, which you need to print out. All pages must be stapled together and neatly labeled with the last 4 digits of your SSN in the top right corner of the top sheet. Please include your name in the documentation at the heading of the program.