Intro to Programming - Lesson 3: Creativity in Algorithms
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.
Algorithm: A precise sequence of instructions for processes that can be executed by a computer
Iterate: To repeat in order to achieve, or get closer to, a desired goal
Selection: A generic term for a type of programming statement (usually an if-statement) that uses a Boolean condition to determine, or select, whether or not to run a certain block of statements
Sequencing: Putting commands in correct order so computers can read the commands
Students will be able to:
Develop an algorithm to solve a new problem with playing cards
Express an algorithm in the Human Machine Language
Identify Sequencing, Selection, and Iteration in a program written in the Human Machine Language
Describe the properties of the Human Machine Language that make it a "low level" language.
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:
Different algorithms can be developed to solve the same problem
Different programs (or code) can be written to implement the same algorithm
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:
Selection: also known as "branching" and is most commonly seen in if-statements -- The "JUMP...IF" command in the Human Machine Language is a form of selection. It gives us a way to compare two things (numbers) and take action "if" one thing was true.
Iteration: also known as "looping" -- The JUMP command in the Human Machine Language allows us to move to a different point in the program and start executing from there. This allows us to re-use lines of code, and this is a form of iteration or looping.
Sequencing: From the framework: "4.1.1B - Sequencing is the application of each step of an algorithm in the order in which the statements are given." Sequencing is so fundamental to programming. In our lesson, the sequencing is simply implied by the fact that we number the instructions with the intent to execute them in order.
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:
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.
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.
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.
If possible, it is easier for students to do this activity with a partner or their teacher. However, the students can still do this activity independently.
Review the first page of the activity guide and the addition of the "swap" command.
Do the example code first: if students have a partner, have one student read the code and ask their partner to perform the task, then have them switch roles and go through the code again.
Here's what the example program does:
END STATE: the order of the cards has been reversed
It does this by first moving the right hand to the end of the list, then shifting each hand progressively toward the middle of the row, swapping cards each time.
The program stops once the hands have crossed over each other (by checking if RHPos < LHPos)
Challenge Activity: Min-to-Front
The challenge is to find the min card and swap it to the front of the list, keeping the order of the rest of the cards the same.
IDEA: Solve the problem of "move-to-front" first. Remember: "Algorithms can be combined to make new algorithms." The students should know a solution to find min from the previous lesson, so they can put that out of mind for a minute. Instead, ask the students to start by assuming that they have found the min card, and then have them write a procedure to move some card to the front of the list by swapping. Once they have finished that, they can simply add their algorithms for finding min to the algorithms they just wrote.
Remind the students to not be afraid to invent a completely new algorithm.
Identify Sequencing, Selection, and Iteration in Human Machine Programs
The CSP Framework states:
Sequencing, selection, and iteration are building blocks of algorithms.
Every algorithm can be constructed using only sequencing, selection, and iteration.
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...
"Sequencing is the application of each step of an algorithm in the order in which the statements are given." -- Does our human machine language have sequencing?
Sequencing is so fundamental to programming it sometimes goes without saying. In our lesson, the sequencing is simply implied by the fact that we number the instructions with the intent to execute them in order.
"Selection uses a [true-false] condition to determine which of two parts of an algorithm is used." -- Where did we see "selection" in our human machine language programs?
The JUMP...IF command in the Human Machine Language is a form of selection. It gives us a way to compare two things (numbers) and take action if the comparison is true, or simply proceed with the sequence if false. NOTE: Selection is also known as "branching" and is most commonly seen in if-statements in programs.
"Iteration is the repetition of part of an algorithm until a condition is met or for a specified number of times." -- Where did we see iteration in our human machine language programs?
The JUMP command (as well as JUMP...IF) in the Human Machine Language allows us to move to a different point in the program and start executing from there. This allows us to re-use lines of code, and this is a form of iteration or looping. (NOTE: Iteration is also known as "looping" in most programming languages.)
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
This is an important essential knowledge statement directly from the CSP Framework. Students should see the connection between the the Find-Min problem and the Min-to-Front problem.
Low-Level languages exist
Most programming languages that you use in every day life are simply higher level, perhaps easier-to-read commands that are translated into more primitive machine commands. So-called "low level" languages are the most basic, primitive, set of commands to control a computer. The Human Machine Language is similar to something called Assembly Language.
From the CSP Framework: 2.2.3C "Code in a programming language is often translated into code in another (lower level) language to be executed on a computer."
The Human Machine Language is a "low level" language because the commands are very primitive and tie directly specific functions of the human machine.
Video: You Should Learn to Program: Christian Genco at TEDxSMU
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.
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.