This is the 2nd day of a 3-lesson sequence in which the students will attempt to show the "art" of programming and introduce the connection between programming and algorithms. In the previous lesson the students established the need for a common language with which they can express algorithms to avoid ambiguity in how instructions would be interpreted. In this lesson the students will continue to establish the connection between programming and algorithms, with more emphasis on the "art" of algorithms.
First, the 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 a row of cards on the table. Once again the students will 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:
- Different algorithms can be developed to solve the same problem.
- Different programs can be written to implement the same algorithm.
- 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.
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"
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 the students will imagine trying to write instructions for a "Human Machine" to complete a tightly defined task with playing cards.
The teacher will introduce the term "algorithm" and what designing an algorithm means in computer science (i.e. programming). Then, the students will 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". Then, the teacher will 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. The point is to show the students that even when they know what the commands are, they still need to be creative to use these commands 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. Please see the wrap up of the next lesson where we introduce students to low level languages.
There are several ways to solve the problems in the activity guides. Allow the students to discuss with their classmate or with the teacher about what is the most efficient way to set up this algorithm.
We have prepared the same documents in different file formats for the lesson. The first file is in .docx format and has many graphic components. Another file is in .doc format and is a text only document. All the graphics in the first .docx file are described in narrative manner. There is also a .brf file, which can work with a refreshable braille display or a braille embosser. The PDF files are also included for convenience.
Yesterday's activity focused on the inherent difficulties of trying to express precise processes with written language. Remind the students that conclusions the class has arrived at include:
- We need to agree on a set of commands and exactly what they 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.
What is Algorithm Discussion
Some remarks for the discussion include:
- Language is important, but there is another part to programming. Once we have a well defined language, we 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 we use a small set of instructions to clearly and correctly define a process that will solve some problem?
- Yesterday, with the LEGO blocks, the students also attempted to design an algorithm. Remind students that any time they are trying to write a precise set of instructions for a process to solve a problem they are designing an algorithm.
- Today the class is going to get into algorithms a little more deeply.
Activity 1: Find Minimum Card Algorithm
Perhaps it goes without saying that in a Computer Science class the students are concerned with not just any processes, but computational processes - ones that can be executed by a computer - which have specific sets of constraints.
The students often get started thinking about algorithms and computational processes by trying to rigorously act them out themselves as a sort of "Human Machine." When acting as a machine, the students can keep the limitations of a computer in mind. In this activity the students are going to pretend that they are a "Human Machine" that operates on playing cards on the table.
Download the "Minimum Card Algorithm - Activity Guide" and then follow the guide to allow the students to develop their own instructions to find the card with the smallest number value. If students prefer, allow them to do this activity independently. While working, consider the following questions for the students:
- "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?"
- Develop a deeper understanding of the problem - trying to write an algorithm should evoke lots of questions about details like: "where do hands start?" or "can we number things?"
- Develop clear, precise processes - ask questions to address gaps in clarity. The students might have to define or make up their own terms for things.
As a class, look at the algorithms that students came up with. Most likely, these algorithms are not all the same. If a student is taking this class by himself or herself, help the student find out that there are many algorithms that would produce the same outcome. However, also point out to students that there are common tasks that they are making the "human machine" do. Ask them what are the commands or actions most of these instructions have in common. Ask them if they can define a language of common Human Machine commands for moving cards around.
- The goal here is to define and agree upon a language for moving cards around.
- 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.
Sample Set of Human Machine Commands:
- 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 the card in the right hand is less than the card in the 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 command is fine for now.
Activity 2: The Human Machine Language
As a class, we have just identified a set of primitive commands that the students can use to operate on a set of cards.
To be very concrete let's formalize this into a language as a class through the following activity.
Instructions for the Activity Guide
- If possible, pair students with a classmate for this activity. If not, the activity can be completed independently.
- Try to figure out how the sample program works first.
- If you have a partner, one person should read the "Human Machine Language," and the other person should perform the task.
- Refer to the reference page to completely understand how each "part" works in the language.
- Try the example which contains the problem. Then come up with a solution without changing the underlining basic language structure and function.
The 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? The answer is "Yes." 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.
Challenge Activity: Find Minimum with the Human Machine Language
First identify what's different about this problem setup for the Human Machine Language:
- All cards are face up
- Card positions have numbers
- We don't need to pick up cards or put them down
- There is actually no way to move cards at all - only move your hands
- The ending state is well defined - left hand touching the minimum card.
Now use the Human Machine Language to write the algorithm for finding the minimum card. NOTE: The students can just write the code, or the students can use the cutout strips of the commands and write values into the boxes.
- This might be very challenging at first since the problem setup is slightly different, which is why it's worth reviewing these differences before you set out on the challenge.
- The problem now has different initial assumptions.
- It's likely that a set of 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.
- It's okay if the student can't quite finish before the period is over, as this activity continues in the next lesson. The teacher can allow this to overflow into the next period, and make the wrap up points later.
Yesterday the class discussed the need for a programming language. Today class 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." There are two facts about the algorithm and programming:
- Different algorithms can be developed to solve the same problem: Even though you were all trying to solve the same problem (find minimum), the class probably 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), it is common that two people trying implement the same algorithm end up coding it differently.
Remarks for the Students
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 the 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.
- Computer Science Principles: 4.1.1 (A, B, C, D, H, I)
- Computer Science Principles: 4.1.2 (A, B, G)
- Computer Science Principles: 4.2.4 (F)
- Computer Science Principles: 5.4.1 (F, I)