Answer these questions:
Algorithms: Solving a Maze POGIL Worksheet
Break into POGIL teams of 4 and assign each team member one of the following roles.
Student Name
Role
Responsibility
Jasmine
Facilitator
Reads the questions aloud, keeps track of time and makes sure everyone contributes appropriately and is heard.
Justin
Spokesperson
Talks to the instructor and other teams when the team has questions and reports team answers back to the class.
Justin
Quality Control
Records all answers and makes sure everyone agrees on the answers.
Jaden
Process Analyst
Considers how the team could work and learn more effectively with respect to use of time, effectiveness, contributions. Reports this back to team and class.
Algorithms: Solving a Maze
The problem below is similar to a type of AP CSP exam question. Consider a robot that can follow the simple sequence commands below:
Let's put our robot in the maze below. The robot is represented as a black triangle and is initially facing up. It can only move forward to a white square. It cannot move onto the black squares or move beyond the edge of the grid.
Answer the following questions with your POGIL team:
CAN_MOVE(forward) is true, but CAN_MOVE(right) is not.
For (i=1, i < 3, i++) {
Move_forward;
}
Rotate_Right;
For (i=1, i<5, i++) }{
Move_forward;
}
Rotate_Left
For (i=1, i < 3, i++) {
Move_forward;
}
REPEAT n times
Commands
Rewrite your algorithm above using Repeat n times control structures (substituting in a
number for n) instead of repeating the MOVE_FORWARD command many times.
For (i=1, i < 3, i++) {
Move_forward;
}
Rotate_Right;
For (i=1, i<5, i++) }{
Move_forward;
}
Rotate_Left
For (i=1, i < 3, i++) {
Move_forward;
}
4.) Can you come up with a more general algorithm to navigate a maze using IF commands and a REPEAT UNTIL GoalReached command, which tests if the robot has reached the gray square goal? Try to come up with an algorithm before looking at the algorithm on the next page.
While (can_move(forward) == true) {
Move_forward
}
While (can_move(right) == true) {
Rotate_right
}
While (can_move(left) == true) {
Rotate_left
}
Here’s a more general way to navigate a maze with the following algorithm which uses GoalReached to test if the robot has reached the gray square.
REPEAT UNTIL GoalReached
{
IF (CAN_MOVE forward)
MOVE_FORWARD
IF (CAN_MOVE left)
ROTATE_LEFT
IF (CAN_MOVE right)
ROTATE_RIGHT
}
5.) (Portfolio) Write an algorithm for washing a stack of 10 items that are cups and saucers mixed together, where the rule is that the cups are washed in hot water and the saucers in cold water. Use simple commands like hot_wash and cold_wash. You may also use the control structures IF and REPEAT n times. Identify the parts of your algorithm that are examples of Sequence, Selection, and Repetition.
REPEAT 10 TIMES
{
IF (CUP)
HOT_WASH
IF (SAUCER)
COLD_WASH