Lab PC-2: Programming Concepts Lab 2: Writing Algorithms

Date open: See Oncourse Assignments
Date due: See Oncourse Assignments
Number of points: 50

Learning Objectives

In this assignment, you will learn, by doing, how to design algorithms, using the fundamental structures of programming:

  1. Sequence: instructions are arranged in a sequence, and are executed one after another (INSTRUCTION, INSTRUCTION, …).
  2. Iteration (repetition):
  3. Selection or making decisions:

Instructions

Select one of the three problems below. Design an algorithm for a robotic agent to solve the problem.

Problems

Choose one of the following three problems. In each case, assume the agent is able to perform the same actions as in the Hour of Code (forward, left, right); we or you may specify additional actions and sensors, as needed.

Robotic Mail Delivery Truck

The truck has a collection (or bag) of letters to deliver. (We do not say whether the letters are sorted or not; you should give this some thought.) All the delivery addresses are on the same street, which is a straight line. Odd addresses are on one side of the street; even addresses are on the other. The truck begins at one end of the street. There is a place to turn around at the opposite end.

The objective is to get all of the mail delivered—ideally, in the shortest time and minimizing the distance traveled.

The sensors include the ability to read the address of a letter and to read the address of the adjacent house on the right. Actions include removing a letter from the bag and putting a letter into the mailbox of the adjacent house on the right.

Garbage Collection

There is a robotic garbage collection truck. The truck has to pick up the garbage on a single street, which is a straight line. The truck has limited capacity, and when it is full, must return to the base and dump the garbage it has collected.

The objective is to get all the garbage picked up and dumped at the base, ideally in the least amount of time and with minimum distance traveled.

The robot is able to sense the presence of a garbage can at its current location, and to tell whether the can is empty or not. Its actions, of course, include the ability to pick up a garbage can, take its contents, and put the can back down.

Vacuuming the Floor

The robot’s task is to vacuum the floor. The floor is a two-dimensional space enclosed by walls on all four sides. There are no internal obstacles to worry about.

The objective is to have a clean floor, ideally in the minimum amount of time and with minimal distance traveled.

The robot’s sensors include the ability to detect an adjacent wall on any of the four sides (ahead, left, right, behind), and to sense the presence or absence of dirt at its current location.

Its actions include moving forward or backward (one step), and turning left or right (90 degrees).

Questions

In your answer, tell us:

  1. Problem: Which problem did you choose (mail delivery, garbage pickup, or vacuum)?
  2. Procedure: What are the instructions, i.e., the algorithm itself, that the robot should use to solve the problem?
  3. Inputs: What sensors or input devices does the robot require? You should list all of the sensory capabilities of the agent, including those we told you about, and any more that you think are necessary.
  4. Outputs: Assume the robot is able to move forward (one step), turn right or left (90 degrees), as in the Hour of Code. Beyond these, what additional actions or output capabilities does the robot require, if any? Include those we told you about as well as those you thought up on your own.
  5. Functions: Assuming the robot is able to perform simple arithmetic (+, -, *, /) and comparison of numbers (<,  ≤ , =, >,  ≥ ) and text (alphabetical order), what additional functions, if any, does it need to have?
  6. Memories: What information, if any, does the agent need to remember?

You might find it easiest to start with the procedure. As you write the procedure, or after you have written it, take note of the inputs, outputs, functions, and memories you are assuming, and describe each of them.

Formatting the Algorithm

You need to indent the algorithm text to show its structure, so, first, let’s think about how to make our writing software indent text:

  1. We recommend using a text editor (such as Notepad++ or TextWrangler, as in the HTML lab, or even Notepad) to write your answer. Save the document as a plain text file with the .txt extension.

  2. If you use the Oncourse WYSIWYG editor, you should select Format: Formatted (see screenshot) for the algorithm text so that it will show indentation properly and not forcibly insert extra blank lines.
    Formatted text in the Oncourse WYSIWYG editor

  3. If you use a word processor, you should select a fixed-width font (such as Courier or Courier New) for the algorithm text so that it will show indentation properly. Also, we prefer you do not attach the word processor file in its native format (e.g., DOC or DOCX); instead, export the document to a PDF file and attach the PDF. (This will help us with grading: we can open the PDF files directly in our web browsers, but opening a word processor file requires running an external program and slows us down. There will be a bonus for not attaching a file that slows us down like this. You can earn this bonus by not using a word processor at all, e.g., using a text editor, or by converting the word processed document to PDF.)

Now let’s turn our attention to how the algorithm should be formatted.

  1. Format a sequence of instructions as one instruction per line, indented to the same level.

    forward
forward
left

  2. Format a repeat structure using the same words (or similar words) as in the Hour of Code; indent the instructions that are repeated four spaces more than the words repeat and do. If you like, you may finish the repeated instructions with the word end (unindented) for additional clarity.

    repeat until sunflower is here
do
    forward
    left
end
    repeat 3 times
do
    forward
    left
end

  3. Format an if or if/else structure using the same words (or similar words) as in the Hour of Code; indent the instructions that are to be done if the condition is true (or false) four spaces more than the words if, do, and else. If you like, you may finish the instructions with the word end (unindented) for additional clarity.

    if path ahead
do
   forward
end
    if path ahead
do
    forward
end
else
    left
end

Following these rules of indentation will make the structure of your algorithms clearer.

Turning in This Assignment

Online sections: Turn in through Oncourse Assignments. Either answer in the submission text box, or attach your plain text (.txt) or PDF (.pdf) file.

Other sections: Your instructor will tell you how to turn in the assignment.

Grading Rubric

50 points nominal total
55 points possible with bonus