Lesson 2: The Need for Algorithms
Overview
This is the 2nd day of a 3lesson 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 “lowlevel” commands for manipulating playing cards. Students are presented with a "Human Machine Language" that includes 5commands 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 5instruction "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, lowlevel, 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 socalled "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
For the Teacher
 KEY  Human Machine Language  2018  Answer Key
 KEY  Minimum Card Algorithm  2018  Answer Key
For the Students
 Human Machine Language  Activity Guide
 Minimum Card Algorithm  Activity Guide
Vocabulary
 Algorithm  A precise sequence of instructions for processes that can be executed by a computer
 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 commands 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 welldefined 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 rightmost 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 handwritten 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 wrapup 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 Overview
 Teacher Overview
 Student Overview
KEY: Minimum Card Algorithm  Example of a student response
KEY: Human Machine Language  Answers to example programs and Find Min with Human Machine Language.
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.
CSTA K12 Computer Science Standards (2017)
AP  Algorithms & Programming
 2AP17  Systematically test and refine programs using a range of test cases.
 3AAP13  Create prototypes that use algorithms to solve computational problems by leveraging prior student knowledge and personal interests.