Algorithmic Design hw

Homework 1

Algorithmic Design

Overview

In this homework you will describe an algorithm in pseudo-code to make a robot successfully navigate a maze. The purpose of this assignment is simply to get your algorithmic juices �owing and to prepare you for the kind of procedural thinking that will be necessary both to succeed in this course and in general as a programmer.

Submission Instructions

This and all other assignments will be submitted through BBLearn. Look for the submission link in the same place you found this assignment.

Technical Description and Instructions

Consider a maze like the one below. The `S' represents where you start and the `E' is the end goal. The dotted line represents the only path from start to �nish (with no backtracking):

##S############################

# ........ # #

##### # #.### ##### ## ##### #

# # # #.# ####...# ## #...# #

# # # # #.# .#.# #.#.# #

# # # # #.######.#.######.#.# #

# ### ###.# #.#.....##.#.# #

# #....# #.# ###....#.# #

# ##### ####.###.# ######.###

# # #.....# # # .. #

############################E##

Finding the dotted path through the maze would not be hard with a bird's eye view of the maze like we have in this document. This is a huge advantage. Imagine now that a person was tasked with �nding their way through a real maze with walls much taller than they could see over. How might they �nd the way out?

The answer is not terribly complicated, and you may know it already. If you don't know or would like a refresher, take a minute to search the internet for `how to get out of a maze'. I found a page with the answer in under a minute with that exact search query.

Once you've found out (or remembered) how to do this, write a simple description of how it can be done in plain, non-technical English. It does not have to be very long, but should be coherently written. I.E., complete sentence(s), reasonable spelling, etc..

Now consider a robot that can be programmed with the pseudo-code functions listed below:

is_facing_wall() This function simply returns true if the robot is currently facing a wall and false other- wise.

turn_clockwise() This function has no return value but causes the robot to change its facing by turning 90° clockwise.

1

move_forward() This function also has no return value and causes the robot to move in its current direction of facing by one square.

is_at_destination() This function returns true if the robot is in the square that represents the end of the maze and false otherwise.

In addition to the functions given above, the robot's pseudo-code programming language also recognizes the following constructs:

� Conditional statements such as:

if(<some condition>) {

<steps to execute>

} else if(<some other condition>) {

<other steps to execute>

} else {

<steps to execute when no conditions are true>

}

Note that the else if and else clauses are optional.

� A simple looping construct like:

while(<some condition>) {

<steps to execute>

}

� Your own custom functions that you can de�ne with the following syntax:

<return type> <function name>() {

<function body>

}

De�ne a function called turn_counterclockwise that turns the robot 90° counter-clockwise1.

Write a pseudo-code program that implements your maze solving algorithm for the robot2. You do not need to pay overmuch attention to `proper syntax'. This is pseudo-code, not C code, and as such I don't mind if you use Python style if statements or whatever. As long as the intention of the code is clear, it doesn't matter.

Enrichment

Image that the robot also had a function which could be called to see if it is at the beginning of the maze. Write down what you think it might signify if this function returned true at some point during the robot's attempt to solve the maze.

1Hint: �Two wrongs don't make a right, but three lefts do.� Try de�ning the function in terms of turn_clockwise. 2Hint: You may want to create some functions that allow the robot to check if there is a wall to its right or left and then

return the robot to its original facing.

2

Grading Speci�cation

For your submission to receive a grade of `pass', it must ful�ll the following criteria:

� It must be submitted as a PDF.

� It must be logically formatted with the answer to each question and the work for each prompt clearly designated under its own heading.

� All directions given with emphasis must be ful�lled. There should be three of these. For the pseudo- code implementation of the maze solving algorithm, you must make a strong attempt. But, if the algorithm is not 100% correct, that is okay.

� Your pseudo-code must be well organized and commented where appropriate. Comments should not give any information that I already gave you in this document or anything painfully obvious. For ex- ample, do not comment �This function turns the robot 90° clockwise� for the function turn_clockwise as this violates both the previous points. If your code is well organized, comments may not even be necessary.

3