Chapter 2.3 - Algorithm Basics
Time Estimate: 45 minutes
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
slides | YouTube video | TeacherTube video | POGIL worksheet
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 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.
Role
Responsibility
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 the team's 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 the use of time, effectiveness, and contributions. Reports back to the 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 of 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.
For the robot in the maze above, is CAN_MOVE(forward) true? Is CAN_MOVE(right) true?
(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.
(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.
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.
A. Which part(s) of the algorithm above are selection control structures?
B. Which part of the algorithm above is a repetition control structure? Remember a control structure can consist of multiple statements.
C. 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?
D. (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.
E. (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
2.3.3 Learning Activities
Learning Objective AAP-2.A: Express an algorithm that uses sequencing without using a programming language.
Algorithms executed by programs are implemented using programming languages.
Learning Objective AAP-2.B: Represent a step-by-step algorithmic process using sequential code statements.
Sequencing is the application of each step of an algorithm in the order in which the code statements are given.
Sequential statements execute in the order they appear in the code segment.
Learning Objective AAP-2.C.a: For relationships between two variables, expressions, or values: a. Write expressions using relational operators.
Learning Objective AAP-2.C.b: For relationships between two variables, expressions, or values: b. Evaluate expressions that use relational operators.
A Boolean value is either true or false.
Learning Objective AAP-2.D: Express an algorithm that uses selection without using a programming language.
Selection determines which parts of an algorithm are executed based on a condition being true or false.
Learning Objective AAP-2.E.a: For selection: a. Write conditional statements.
Learning Objective AAP-2.E.b: For selection: b. Determine the result of conditional statements.
Conditional statements or if-statements affect the sequential flow of control by executing different statements based on the value of a Boolean expression.
Learning Objective AAP-2.F: Express an algorithm that uses iteration without using a programming language.
Iteration is a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.
Learning Objective AAP-2.G.a: For iteration: a. Write iteration statements.
Learning Objective AAP-2.G.b: For iteration: b. Determine the result or side-effect of iteration statements.
Iteration statements change the sequential flow of control by repeating a set of statements zero or more times, until a stopping condition is met.
Learning Objective AAP-2.H.a: For algorithms: a. Create algorithms.
Learning Objective AAP-2.H.b: For algorithms: b. Combine and modify existing algorithms.
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. Some existing algorithms include: -determining the maximum or minimum value of 2 or more numbers - computing the sum or average of 2 or more numbers - identifying if an integer is or is not evenly divisible by another integer - determining a robot’s path through a maze
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.
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.
Q-1: Which of the following is not true about algorithms:
A. Algorithms are step-by-step procedures.
B. Algorithms can be written to solve every problem.
C. Algorithms consist of a combination of sequences, selections, and/or repetitions.
D. An algorithm is a sequence of precise instructions.
Activity: 2.3.5.1 Multiple Choice (mcsp-2-3-1)
Q-2: True or False: The Blockly Maze language is an example of pseudocode.
A. True
B. False
Choose one
Activity: 2.3.5.2 Multiple Choice (mcsp-2-3-2)
Q-3: Pseudocode is ___________________? (Choose all that apply)
A. not a programming language
B. an executable program
C. a mixture between a natural language and a programming language
D. easy to read
Activity: 2.3.5.3 Multiple Choice (mcsp-2-3-3)
Q-4: Complete the following sentence: Sequencing in algorithms means that each step of the algorithm is executed ____________.
A. all at once
B. two steps at a time
C. in any order the programmer chooses
D. in the order they are given
Activity: 2.3.5.4 Multiple Choice (mcsp-2-3-4)
Q-5: Which of the following algorithms would navigate the robot below to reach its goal, the gray square?
A.
REPEAT UNTIL GoalReached
IF CAN_MOVE forward
MOVE_FORWARD
B.
REPEAT UNTIL GoalReached
IF CAN_MOVE forward
MOVE_FORWARD
ELSE
ROTATE_LEFT
C.
REPEAT UNTIL GoalReached
IF CAN_MOVE left
ROTATE_RIGHT
ELSE
MOVE_FORWARD
D.
REPEAT UNTIL GoalReached
IF CAN_MOVE forward
MOVE_FORWARD
ELSE
ROTATE_RIGHT
Activity: 2.3.5.5 Multiple Choice (mcsp-2-3-5)
2.3.6. Reflection: For Your Portfolio
(POGIL) Write an algorithm using the 4 simple commands to navigate the robot through the maze in the POGIL question listed in your online textbook.
(POGIL) Write an algorithm using repetition control structures to navigate the robot through the maze referenced above.
(POGIL) Include a description or a photo of your drawing of a maze that the general algorithm in the POGIL exercise CANNOT solve.
(POGIL) Write an algorithm for washing a stack of 10 items that are cups and dishes mixed together, where the rule is that cups are washed in hot water and 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.
Portfolio Reflection Questions
Make a copy of this document in your Portfolio Assignments folder and answer these questions in the spaces below. Once complete, turn in this assignment according to the steps given by your teacher.
Answer the following questions: 1. (POGIL) Write an algorithm using the 4 simple commands to navigate the robot through the maze in the POGIL question listed in your online textbook.
Answer
2. (POGIL) Write an algorithm using repetition control structures to navigate the robot through the maze referenced above.
Answer
3. (POGIL) Include a description or a photo of your drawing of a maze that the general algorithm in the POGIL exercise CANNOT solve.
Answer
4. (POGIL) Write an algorithm for washing a stack of 10 items that are cups and dishes mixed together, where the rule is that cups are washed in hot water and 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.
Answer
Last updated