Algorithm Basics¶
Time Estimate: 45 minutes
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.
- express an algorithm that uses sequencing, selection and iteration without using a programming language
- create algorithms, write conditional statements, and write iteration statements
- 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
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 here
is a summary of some basic points about algorithms.
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 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.
- 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.
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
- Which part(s) of the algorithm above are selection control structures?
- Which part of the algorithm above is a repetition control structure? Remember a control structure can consist of multiple statements.
- 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?
- (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.
- (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.
Summary¶
In this lesson, you learned how to:
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.
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.
- An algorithm is a sequence of precise instructions.
- This is challenging, but rewarding! An algorithm is indeed a sequence of precise instructions. So this is not the correct answer.
- Algorithms can be written to solve every problem.
- Yes, by process of elimation, this is the correct answer. As we will learn more fully later in the course, it has been proved that there are problems for which it is impossible to write a correct algorithm. Such problems are called undecidable problems. A surpisingly simple example is the halting problem, which can be stated as: Given a description of an arbitrary computer program and a finite set of inputs to the program, determine whether the program will eventually stop or run forever.
- Algorithms are step-by-step procedures.
- This is challenging, but rewarding! Algorithms do proceed step-by-step. So this is not the correct answer.
- Algorithms consist of a combination of sequences, selections, and/or repetitions.
- This is challenging, but rewarding! Algorithms are indeed constructed by combinations of three control structures, sequence, selection, and repetition. So this is not the correct answer.
Q-2: Which of the following is not true about algorithms:
- True
- OK, so you didn’t get it right this time. Let’s look at this as an opportunity to learn. Try reviewing this...The Blockly Maze language is an example of a programming language. It is more formal than pseudocode and its instructions can be executed (run) on a computer.
- False
- Right. The Blockly Maze language is an example of a programming language. It is more formal than pseudocode and its instructions can be executed (run) on a computer.
Q-3: True or False: The Blockly Maze language is an example of pseudocode.
- easy to read
- Because it is concise, pseudocode is easy to read--easier than a natural language.
- not a programming language
- Pseudocode may use elements from a programming language but it is not as formal as a programming language.
- a mixture between a natural language and a programming language
- Yes, pseudocode is more precise than, say, English, but not as formal as a programming language.
- an executable program
- We’re in the learning zone today. Mistakes are our friends!
Q-4: Pseudocode is ___________________.
- in any order the programmer chooses
- If it were easy, you wouldn’t be learning anything!
- all at once
- If it were easy, you wouldn’t be learning anything!
- two steps at a time
- If it were easy, you wouldn’t be learning anything!
- in the order they are given
- That's right. A sequence of instructions is executed from top to bottom in the order that they are given.
Q-5: Complete the following sentence: Sequencing in algorithms means that each step of the algorithm is executed ____________.
REPEAT UNTIL GoalReached
IF CAN_MOVE forward
MOVE_FORWARD REPEAT UNTIL GoalReached
IF CAN_MOVE forward
MOVE_FORWARD
ELSE
ROTATE_RIGHT REPEAT UNTIL GoalReached
IF CAN_MOVE left
ROTATE_RIGHT
ELSE
MOVE_FORWARD REPEAT UNTIL GoalReached
IF CAN_MOVE forward
MOVE_FORWARD
ELSE
ROTATE_LEFT
Q-6: Which of the following algorithms would navigate the robot below to reach its goal, the gray square?
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.