Lesson 2: The Need for Algorithms
Overview
This is the 2nd day of a 3-lesson sequence in which we attempt to show the "art" of programming and introduce the connection between programming and algorithms. In the previous lesson we established the need for a common language with which express algorithms to avoid ambiguity in how instructions would be interpreted. In this lesson we continue to establish the connection between programming and algorithms, with more emphasis on the "art" of algorithms.
First students are presented with a new task for the “human machine” - to write a set of instructions to identify the smallest (lowest value) card in row of cards on the table. Once again we try to establish a set of fundamental commands for doing this, and develop a more formal set of “low-level” commands for manipulating playing cards. Students are presented with a "Human Machine Language" that includes 5-commands and then must figure out how to use these primitive commands to “program” the same algorithm.
At the conclusion several points about programming can be made, namely: 1. Different algorithms can be developed to solve the same problem 2. Different programs can be written to implement the same algorithm.
Purpose
The main point here is to connect the acts of writing "code" and designing algorithms, and to take some steps towards programming with code. To do this we imagine trying to write instructions for a "Human Machine" to complete a tightly defined task with playing cards.
We want to introduce the term algorithm and what designing an algorithm means in computer science (i.e. programming). We then want to take a few steps to build up to writing an algorithm with "code". Here are the basic steps of the lesson and their underlying purpose.
Step 1: Discover common instructions
When students write instructions to find the minimum card in a row of cards, we'll discover that even though the words used might be different between groups, there is probably a lot of commonality to underlying actions we need (shifting hands, picking up cards, comparing cards, jumping to a certain line in the instructions, etc.)
Step 2: Agree on a minimal instruction set
Recognizing these commonalities we can give names to a few commands and come to agreement about how they should be interpreted. This is the foundation for a "code". We then provide a 5-instruction "human machine language" that is sufficient for implementing an algorithm to find the minimum card.
Step 3: Use the provided Human Machine Language "code" to implement an algorithm
The art of programming is to solve computational problems using a provided language that controls the machine. In the activity we provide a simple, low-level, language for acting on playing cards. The point is to show that even when you know what the commands are, you still need to be creative to use them to solve a problem.
Why the Human Machine Language? This language bears a strong resemblance to so-called "low level" programming languages - a sparse, primitive set of commands to directly control the physical/electronic operations of a computing machine. Other programming languages are built on top of the low level languages to provide more abstraction and functionality that combines low level operations into commonly used procedures. The most commonly known low level language is called Assembly Language For a good example see the wrap up of the next lesson where we introduce students to low level languages.
Agenda
Getting Started (5 mins)
Activity 1 (30 mins)
Activity 2 (30 mins)
Wrap Up (10 mins)
View on Code Studio
Objectives
Students will be able to:
- Trace programs written in the "Human Machine Language"
- Develop an algorithm to find the smallest playing card in a row of cards
- Express an algorithm in the "Human Machine Language"
- Identify the properties of sequencing, selection and iteration the "Human Machine Language"
- Evaluate the correctness of algorithms expressed in the "Human Machine Language"
Links
Heads Up! Please make a copy of any documents you plan to share with students.
For the Teachers
- KEY - Human Machine Language - Answer Key
- KEY - Minimum Card Algorithm - Answer Key
For the Students
- Human Machine Language - Activity Guide
- Minimum Card Algorithm - Activity Guide
Vocabulary
- Algorithm - A list of steps to finish a task.
- High Level Programming Language - A programming language with many commands and features designed to make common tasks easier to program. Any high level functionality is encapsulated as combinations of low level commands.
- Low Level Programming Language - A programming language that captures only the most primitive operations available to a machine. Anything that a computer can do can be represented with combinations of low level commands.
Teaching Guide
Getting Started (5 mins)
Recall the lessons learned about language
Yesterday's activity focused on the inherent difficulties of trying to express precise processes with written language. We arrived at a few conclusions...
- We need to agree on a set of commands and exactly what terms mean
- The fewer commandes we have, the easier it is to agree
- We want to know what are the "primitive" operations - the most basic set of operations that will allow us to do most of the tasks that the situation requires.
Define: Algorithm
Remarks
- Language is important, but there is another part to programming. Once you have a well defined language you need to apply it to problems.
- The art (and science) of using a well-defined language of primitive operations to solve problems is the art and science of algorithms.
- The CS Principles definition of algorithm is: Algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages.
- One way to think of the study of algorithms is that it is the study of processes -- how can you use a small set of instructions to clearly and correctly define process that will solve some problem?
- Yesterday, with the LEGO blocks, you also attempted to design an algorithm. Any time you are trying to write a precise set of instructions for a process to solve a problem you are designing an algorithm.
- Today we're going to get into algorithms a little more deeply.
Activity 1 (30 mins)
Find Min Card Algorithm
Remarks
Perhaps it goes without saying that in a Computer Science class we are concerned with not just any processes, but computational processes - ones that can be executed by a computer - which have specific sets of constraints.
We often get started thinking about algorithms and computational processes by trying to rigorously act them out ourselves as a sort of “Human Machine”. When acting as a machine, we can keep the limitations of a computer in mind.
In this activity you're going to pretend that you are a "Human Machine" that operates on playing cards on the table.
Distribute Minimum Card Algorithm - Activity Guide
Put students into pairs
Teaching Tip
Circulate the room asking pairs to demonstrate what they are coming up with.
Use the suggested solution in the answer key, as well as the notes on the discussion that follows this activity, to help guide your questioning.
You're looking for students to:
- Develop deeper understanding of the problem - trying to write an algorithm should evoke lots of questions about details like: "where do hands start?" "can we number things?"
- Develop clear, precise processes - ask questions to address gaps in clarity. Students might have to define or make up their own terms for things.
After distributing the guide and playing cards:
-
Get clear on the task, rules, instructions
-
With a partner act out an algorithm
-
Write down the steps
-
Give students time to work
As students are working you might ask probing questions like:
- "How do you know when to stop?"
- "Do your instructions state where and how to start?"
- "Is it clear where to put cards back down after you've picked them up?"
Discussion Goal
The goal here is to define and agree upon a language for moving cards around.
You'll probably need to steer the conversation a little bit so that you land on the commands we need for the upcoming activity. You can probably coerce the conversation based on your observations circulating the room.
A secondary, longer range, goal here is to see where programming languages come from - it's often from a process just like this. What can end up looking cryptic is often actually simple, or at least stems from trying to keep things as simple as possible.
Discuss - Define a language
-
Invite a pair to share their solution by reading it out loud or displaying.
-
Ask if any other groups did something similar.
Prompt:
-
"As we look at these algorithms you came up with, we can see they are not all the same. However, there are common things that you are all making the human machine do and commonalities in some of your instructions. Can we define a language of common Human Machine commands for moving cards around? What are the commands or actions most of these instructions have in common?"
-
Ask students to suggest commands
- Write them down or group them based on type.
-
Hopefully, you can derive a set similar to what we'll use in the next activity:
-
SHIFT (hand) - some form of shifting hands one position down the row left or right
-
MOVE (hand) - some form of moving a hand directly to a particular card based on its position in the list or to the position of one of the other hands.
-
COMPARE - some way to compare cards and do something based on the result like: "if card in right hand is less than card in left hand then..."
-
GO TO LINE - some way to jump to an earlier or later line in the program
-
PICK CARD UP/PUT CARD DOWN - some way to do this that also makes clear where to put a card back down. Typically something like: "Put right hand card down into the right-most open space in the row of cards" NOTE: we don't need this command for the next activity so just acknowledging the need is fine.
-
Transition to next activity...
Activity 2 (30 mins)
The "Human Machine" Language
We have just identified a set of primitive commands that we can use to operate on a set of cards.
To be very concrete let's formalize this into a language...
Distribute Activity Guide - Human Machine Language - Activity Guide
Introduce Human Machine Language
-
Have students read the first page.
-
Clarify the instructions and setup.
-
Put students into partners (same partner they developed the Find Min algorithm with)
Students Execute the Example Programs
-
Students should try to figure out the example programs with a partner, making use of the code reference guide.
-
One partner reads, the other acts as the human machine.
-
They should jot notes about what the program does.
Review the example programs and answer questions (See: KEY - Human Machine Language - Answer Key)
-
Verify that students get the gist of how the language works.
-
For each example you can ask students to describe what it did.
-
Review the last example which had a problem.
- Make sure everyone understands the problem
- Have students suggest a solution (or show a solution along with the following transitional comments)
Transition to the challenge
This problem we identified with the last example speaks to the art and science of algorithm design and what can make it so interesting.
The question is: can we fix the problem without adding more commands to the language? Yes. (see examples of fixes)
If we can fix a problem without extending the language, that's a good thing. We can focus our attention on designing algorithms given these constraints.
Let's try to write FindMin using the Human Machine Language...
Teaching Tip
Reviewing Differences
- This might be very challenging at first since the problem setup is slightly different, which is why it's worth reviewing these differences before students set out on the challenge.
- The problem now has different initial assumptions.
- It's likely that student's hand-written instructions will differ because:
- They weren't restricted to one command per line as they must be for the Human Machine Language
- It involved actions like picking up cards, changing hands, or moving cards to other locations, which is also not possible with the Human Machine Language.
Don't need to finish today
- It's okay if you can't quite finish before the period is over. This activity continues in the next lesson anyway. You can allow this to overflow, and make the wrap up points later.
Challenge: Find Min with the Human Machine Language
First identify what's different about the problem setup for the Human Machine Language:
- All cards are face up
- Card positions have numbers
- Don't need to pick up cards or put them down
- There is actually no way to move cards at all - only hands
- The ending state is well defined - left hand touching the min card.
Now use the Human Machine Language to write the algorithm for finding the min card.
-
NOTE: Students can just write the code, or you can use the cutout strips of the commands and write values into the boxes.
-
Give students time to work things out with their partners.
-
It may take some time to get oriented and understand the task.
- This is a first experience in evaluating some code.
- It's important to actually try out a solution to identify any potential errors.
- It's also important to see that people's programs are different
- See the wrap-up notes for other things to identify as students share
Share solutions to Find Min with the Human Machine Language
- Put pairs together to compare solutions.
- Each group should test out the other group's code by acting as the human machine.
- During the comparision note any differences in people's approach.
- There are several ways to go about it but the canonical solution is given in the answer key.
Wrap Up (10 mins)
Discuss - The "Art" of Programming
Connect algorithms to programming.
- Yesterday we discussed the need for a programming language
- Today we came up with our own programming language and used it to implement an algorithm.
- The CSP definition of algorithm is: “a precise sequence of instructions for processes that can be executed by a computer and are implemented using programming languages."
Notice two things about algorithms and programming...
Content Corner
Point 1 is verbatim from the CSP Framework -- Essential Knowledge statement 4.1.1H
Point 2 is not in the framework, but is equally true.
-
Different algorithms can be developed to solve the same problem
Even though you were all trying to solve the same problem (find min) as a class we came up with different methods for doing it. We would say we came up with different algorithms.
-
Different code can be written to implement the same algorithm
This is sometimes surprising to newcomers. When writing "code" (even with with the human machine language) two people trying to write code to implement the same algorithm may very easily code it differently.
Remarks
These two facts - Different algorithms can be developed to solve the same problem and different code can be written to implement the same algorithm - embody art of programming and what makes programming so fun, engaging and creative.
In programming, just like art, we strive to make beautiful things:
- A beautiful algorithm is an elegant and clever idea for how to solve a problem.
- A beautiful program is an elegant use of whatever language structures are provided to make the algorithm actually work on a computer.
Foreshadow: tomorrow we'll try some other algorithms in the human machine language.
- Lesson Vocabulary & Resources
- 1
Teaching Tip
KEY: Minimum Card Algorithm - Example of a student response
KEY: Human Machine Language - Answers to example programs and Find Min with Human Machine Language.
Student Instructions
Unit 3: Lesson 02 - The Need for Algorithms
Vocabulary
- Algorithm: A precise sequence of instructions for processes that can be executed by a computer and are implemented using programming languages. (NOTE: this is the definition from the AP CS Principles framework).
- Low level programming language: A programming language that captures only the most primitive operations available to a machine. Anything that a computer can do can be represented with combinations of low level commands.
- High level programming language: A programming language with many commands and features designed to make common tasks easier to program. Any high level functionality is encapsulated as combinations of low level commands.
Lesson
- Write instructions to find the smallest card in a row of playing cards
- Compare solutions with classmates and come up with the mimimal set of instructions needed to do this
- Define a "human machine language" for this task and implement your algorithm with it.
- Test out and refine your algorithm
Resources
Standards Alignment
View full course alignment
Computer Science Principles
4.1 - Algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages.
4.1.1 - Develop an algorithm for implementation in a program. [P2]
- 4.1.1A - Sequencing, selection, and iteration are building blocks of algorithms.
- 4.1.1B - Sequencing is the application of each step of an algorithm in the order in which the statements are given.
- 4.1.1C - Selection uses a Boolean condition to determine which of two parts of an algorithm is used.
- 4.1.1D - Iteration is the repetition of part of an algorithm until a condition is met or for a specified number of times.
- 4.1.1H - Different algorithms can be developed to solve the same problem.
- 4.1.1I - Developing a new algorithm to solve a problem can yield insight into the problem.
4.1.2 - Express an algorithm in a language. [P5]
- 4.1.2A - Languages for algorithms include natural language, pseudocode, and visual and textual programming languages.
- 4.1.2B - Natural language and pseudocode describe algorithms so that humans can understand them.
- 4.1.2G - Every algorithm can be constructed using only sequencing, selection, and iteration.
4.2 - Algorithms can solve many but not all computational problems.
4.2.4 - Evaluate algorithms analytically and empirically for efficiency, correctness, and clarity. [P4]
- 4.2.4F - Finding an efficient algorithm for a problem can help solve larger instances of the problem.
5.4 - Programs are developed, maintained, and used by people for different purposes.
5.4.1 - Evaluate the correctness of a program. [P4]
- 5.4.1F - Knowledge of what a program is supposed to do is required in order to find most program errors.
- 5.4.1I - Programmers justify and explain a program’s correctness.