CSI $131$ Computational Thinking

LAB $1-$ Problem solving, introducing repetition and decisions: Intuitive

Objectives:

a$)$ Describe the difference between heuristic and algorithmic solutions to problems.

b$)$ List $/$ describe the five steps to solving a problem that has an algorithmic solution.

$1.$ Problem Types: From the definition of algorithm we see that it involves a set of steps to get to the solution. This is possible with numeric problems like performing long division, calculating the trajectory of a baseball, or adding a column of numbers. These problems are said to have an algorithmic solution. Some problems cannot be solved through a sequence of steps. For example, determining whether an egg is $$over cooked,$$ deciding if a person is $$nice$,$ or whether to buy a certain stock. These problems have heuristic solutions. The solution is determined through $$trial and error$$ techniques, experience or intuition.

$2.$ Five Steps in Problem Solving:

i$)$ Understand the Problem: Once the problem is identified take time to understand every aspect of the problem. It is very important to do this because only after one understands the problem can one begin to solve the problem.

ii$)$ Design a Solution: Identify alternative solutions to the problem. The list should be as complete as possible. Look in books, discuss with friends, and consider all approaches you can think up $($consider the ridiculous, think outside the box$).$ Identify and evaluate the pros and cons of each possible solution prior to choosing the $$best$$ one. Then design a solution using a flowchart $($in this class$)$

iii$)$ Validate the solution: trace the logic to make sure that it produces correct answers. This requires testing every branch of the logic.

iv$)$ Implement the Best solution: In this class we will be using C$++$ to implement or solutions on a computer.

v$)$ Test the Solution: Check if the result is correct, and if it satisfies the needs of the person with the problem. If the result is either incorrect or unsatisfactory the process must be started over. If the solution contains semantic errors then use code tracing to debug the code.

$3.$ Assignment $($Bob the Robot$)$ Bob has $15$ instructions in his knowledge base. He can follow a set of instructions and do what he is told, as long as they are part of his knowledge base. He executes instructions in sequential order $($when he is finished with one instruction he executes the next in order$).$ He does only what he is told.

Maneuvering Instructions:

$1.$ Sit Down

$2.$ Stand Up

$3.$ Take Step $($will take a single step forward in the direction he is currently facing$)$

$4.$ Turn $($rotate left $90$ degrees$)$

$5.$ Open Door $($opens a door that is immediately in front of Bob$)$

Conditional Instructions:

$6.$ Wall in Front $($tests if there is a wall impeding next move$)$

$7.$ Door Closed $($ tests if a door is closed$)$

$8.$ Chair in Front $($tests if chair is in front$)$

$9.$ Chair in Room $($tests if a chair is in the same room as Bob$)$

$10.$ Is Door $($test if door is in front$).$

Repeat Instructions :

$11.$ Repeat x Times $[$instruction$]($executes $[$instruction$]$ x times$)$

$12.$ Repeat$\_$Until $[$statement$]($repeats until statement is false$)$

Other Instructions :

$13.$ Add $($ Bob can remember a single number $($called Memory$)$and this will add one to it$.$ The number is zero when execution begins$)$

$14.$ Subtract $($this will subtract one from the number in Bob$$s memory$)$

$15.$ Halt $($stops execution of instructions$)$

Example: Direct Bob to walk down a hall where a chair is$,$ sit down, get up and go back to where Bob started. Bob is currently facing the correct direction but we do not know how many steps to the chair.

Repeat$\_$Until$[$Chair in Front$]$ Bob keeps walking and counting the

Take Step number of steps until the chair is encountered.

Add

Turn Turn Bob around so the chair is behind him.

Turn

Sit Down Bob sits

Stand Up Bob stands

Repeat Memory Times $[$Take Step$]$ Bob goes back the number of steps he took

Halt Stop.

Use the five steps to solve the following:

a$)$ Direct Bob to walk in a square that is $3$ steps on each side. All turns are to be left$-$hand turns. How many solutions can you find?

b$)$ Direct Bob to walk in a square that is $3$ steps on each side. All turns are to be right$-$hand turns. How many solutions can you find?

c$)$ Direct Bob to walk to a wall that is any distance forward and then walk back to three steps to the left of the starting location.