2.3. Algorithm Basics

Time Estimate: 45 minutes

2.3.1. Introduction and Goals

In Lesson 1.2 we introduced the term algorithm and defined it as a step-by-step procedure of precise instructions that performs some calculation or computation. Algorithms are at the heart of computer science. Algorithms, expressed in computer code and interpreted by the computer, are what make our computers such powerful and adaptable machines. An amazing fact that has been proved by computer scientists is that all algorithms can be constructed by using just these three control structures. In other words, any algorithm that you would like to write to solve a problem can be built by a combination of sequence, selection, and repetition.

Learning Objectives: I will learn to
  • express an algorithm that uses sequencing, selection and iteration without using a programming language
  • create algorithms, write conditional statements, and write iteration statements
Language Objectives: I will be able to
  • use target vocabulary, such as algorithm, sequence, selection, repetition, and pseudocode, while describing a problem solving process, out loud and in writing, with the support of vocabulary notes from this lesson
  • describe the relationship between the target vocabulary words for the POGIL activity and portfolio reflection questions with the support of concept definitions and vocabulary notes from this lesson

2.3.2. Learning Activities

Blockly Maze Problems

Beyond visual and textual programming languages, algorithms can be expressed in a variety of ways such as natural language, diagrams, and pseudocode which is a way to describe the each step of the code in English to plan it out. Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing algorithms. Knowledge of existing algorithms can help in constructing new ones. Using existing correct algorithms as building blocks for constructing another algorithm has benefits such as reducing development time, reducing testing, and simplifying the identification of errors.

As we saw in the maze problems in Lesson 1.2, algorithms are constructed out of basic building blocks called control structures. There are three basic control structures:

  • Sequence– a sequence of instructions or statements.
  • Selection– a conditional instruction that lets the program branch between two or more alternatives.
  • Repetition (or Iteration)– a structure that repeats one or more instructions.

If you didn't get a chance to work through the Maze problems in Unit 1 or if you want to solve a few more maze problems that use sequence, selection, and iteration, here's a link to some additional problems that use the Blockly language (instructions).

Algorithm Basics

Now that you've created algorithms to solve Maze puzzles using sequence, selection, and iteration, watch this video about algorithms by Dr. Ralph Morelli, one of the founders of Mobile CSP.



POGIL Activity for the Classroom

This course emphasizes communication and collaboration. You will do many group activities called POGIL Activities in this course, starting with the one below. POGIL stands for Process Oriented Guided Inquiry Learning. In POGIL activities, you will work in self-managed teams of 3 or 4 students where everyone has a role. You will explore an activity or solve a problem together, making sure that everyone in the team participates and learns. In order for these POGIL activities to be effective, each member must be willing to practice good interpersonal skills including communication, consensus building, conflict resolution, and negotiation.


Break into POGIL teams of 4 and assign each team member one of the following roles. Record your answers using this worksheet.
Here's more information about POGIL roles.
RoleResponsibility
Facilitator Reads the questions aloud, keeps track of time and makes sure everyone contributes appropriately and is heard.
Spokesperson Talks to the instructor and other teams when the team has questions and reports team answers back to the class.
Quality Control Records all answers & questions, and makes sure everyone agrees on the answers.
Process Analyst Considers how the team could work and learn more effectively with respect to use of time, effectiveness, contributions. Reports 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:

  • MOVE_FORWARD: The robot moves 1 square forward in the direction it is facing.
  • ROTATE_RIGHT : The robot turns right 90 degrees, staying in the same square.
  • ROTATE_LEFT: The robot turns left 90 degrees, staying in the same square.
  • CAN_MOVE(direction): This command can be used with 4 possible directions: left, right, forward, and backward. It returns true if there is an open square in the specified direction from the square that the robot is in.

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 group using this worksheet.
  1. For the robot in the maze above, is CAN_MOVE(forward) true? Is CAN_MOVE(right) true?
  2. (Portfolio) Write an algorithm using the 4 commands above to navigate the robot through the maze to reach the gray square. You can pretend that one of you is the robot and walk through your algorithm with your fingers on the maze. Are there commands that are repeated in your algorithm? Circle them.
  3. (Portfolio) Let's replace the repeated commands with a repetition control structure. The following command can be used to repeat a block of commands:
    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.
  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 and then click on and compare to the Maze Navigation Algorithm below.

    Maze Navigation Algorithm (click here after trying your own algorithm)

    REPEAT UNTIL GoalReached
      IF CAN_MOVE forward
        MOVE_FORWARD
      IF CAN_MOVE left
         ROTATE_LEFT
      IF CAN_MOVE right
         ROTATE_RIGHT
    1. Which part(s) of the algorithm above are selection control structures?
    2. Which part of the algorithm above is a repetition control structure? Remember a control structure can consist of multiple statements.
    3. Does the algorithm solve the maze above and navigate the robot to the goal, the gray square? How many times does it need to run through the loop?
    4. (Portfolio) Can you come up with a maze that this algorithm will not be able to solve? Include a description or a photo of your drawing of such a maze in your portfolio.
  5. (Portfolio) Write an algorithm for washing a stack of 10 items that are cups and dishes mixed together, where the rule is that the cups are washed in hot water and the dishes 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.

2.3.3. Summary

In this lesson, you learned how to:

2.3.4. Still Curious?

It may seem a bit amazing to you that the three simple control structures we used in the Maze problems are powerful enough, in combination, to build any algorithm that can be thought of. But this fact, known as the structured program theorem, was proved in a 1966 research paper by Corrado Boehm and Guiseppe Jacopini. You can read more about it in this Wikipedia article.

2.3.5. Self-Check

Vocabulary

Here is a table of the technical terms we've introduced in this lesson. Hover over the terms to review the definitions.

algorithm
control structure
sequence
selection
repetition 		iteration
boolean
pseudocode
flowchart

Check Your Understanding

Complete the following self-check exercises.

2.3.6. Reflection: For Your Portfolio

Answer the following portfolio reflection questions as directed by your instructor. Questions are also available in this Google Doc where you may use File/Make a Copy to make your own editable copy.

You have attempted of activities on this page