Overview

This is the third of the first three lessons that make the connection between programming and algorithms. In this lesson, the students will continue to work with the "Human Machine Language" to get creative designing more algorithms for playing cards. One command is added to the language from the previous lesson (SWAP) that allows positions of cards to change. With the addition of this swap command, the challenge is to design an algorithm that will move the minimum card to the front of the list while keeping the relative order of all the other cards the same. If that is achieved, some other Human Machine Language challenges are available.

Vocabulary

Goals

Students will be able to:

Purpose

The purpose of this lesson is to see what "creativity in algorithms" means. Creativity has to do with both the process of inventing an algorithm to solve a new problem in a given context and the implementation of that algorithm in a given language. Creativity often means combining or using algorithms someone knows as part of a solution to a new problem. Thus, the "Min To Front" problem is interesting because students already solved part of it (the find min part) in the previous lesson.

In the CSP Framework, almost every "Essential Knowledge" statement from "Learning Objective 4.1.1 Develop an algorithm for implementation in a program" applies here. The two points from the previous lesson carry over here and are also in the CSP Framework:

Furthermore, the CSP Framework states: "4.1.1A Sequencing, Selection, and Iteration are building blocks of algorithms" and "4.1.2G Every algorithm can be constructed using only sequencing, selection, and iteration." The findMin problem and the other problems the students solved with the Human Machine Language also have sequencing, selection, and iteration. Here's what they mean:

Looking ahead, while sequencing seems obvious at first, it can trip up the novice programmer, because you must pay attention to how the state of the world changes with each line executed. In particular, this can cause some confusion when programming simple mathematics. For example, here is a series of instructions in some programming language:

Example:

x = 2
x = 5
x = x + 1

In mathematics this is an impossible (and meaningless) system of equations. But in programming, because it's sequenced, it simply means do one thing after the other; first, x gets the value 2. Then, x gets the value 5. Then x gets the current value of x plus 1. When these 3 lines have completed executing x has the value 6.

Resources

Activity Guides

Solutions

Teacher's Tip

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.

Getting Started

One thing about algorithms is that once someone knows a few, and knows how they work, that person can combine them (or slightly modify them) to solve new problems. Creativity in algorithms comes from figuring out clever ways to solve problems by developing a process that could be executed by a machine. As a class, we study algorithms and care about them because in programming the techniques and mechanics of certain processes come up over and over and over again. So it's worth knowing a few so programmers don't have to reinvent the wheel. For example, suppose someone just wrote an algorithm to find the smallest card in a row of cards. Is it hard to modify that exact same strategy to find the max card? (The answer is no.) There will be challenges in today's class where students will be solving a few more problems that will require the students to get creative!

Activity: Adding SWAP to Human Machine Language

Download and follow the activity guide with the students.

Teaching Tips

Here's what the example program does:

Challenge Activity: Min-to-Front

Wrap Up

Identify Sequencing, Selection, and Iteration in Human Machine Programs

The CSP Framework states:

If these statements are true then we should be able to identify these elements of sequencing, selection and iteration in our Find-Min and Min-to-Front algorithms. Give the students a quick definition of each and ask them if or where we saw it in our Human Machine Language programs...



Discussion

After reviewing solutions, there are a few points to make to wrap up this foray into algorithms:

Algorithms can be combined to make new algorithms

Low-Level languages exist

Teaching Tips

The students don't really need to know many specifics about low level languages. The point should be made here in order to refer back to it later when the students are programming in a high level language (like JavaScript, Quorum, etc.). A high level language is more abstract, provides more functionality to make it faster to write and reason about programs, but ultimately that code is translated down into low-level, primitive machine instructions for the computer to execute.

Video: You Should Learn to Program: Christian Genco at TEDxSMU

Remarks

Learning to program is really learning how to think in terms of algorithms and processes. And it can be really fun and addicting. In the next lesson the students will start writing programs that a real machine (not a human machine) will execute. But since programming is really about thinking and problem solving, their "human machine" skills will come in handy - reasoning about programming is a way of reasoning about what a computer can and cannot do, and what the given language you're using lets you and doesn't let you do.

Assessment

Write a human machine language program that: Repeatedly shifts the left hand to the right until it finds a 5 or 6. The program should stop when the left hand is at (or past) the end of the list, or it finds a 5, or it finds a 6.

Standards Alignment