Unit3
Ch. 1
1
2
3
4
5
6
7
8
9
10

Lesson 3: Creativity in Algorithms

Overview

This is the third of three lessons that make the connection between programming and algorithms. In this lesson students 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 swap 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.

Purpose

The purpose of this lesson is to see what "creativity in algorithms" means. Creativity has to do with both the process you invent (an algorithm) to solve a new problem in a given context and how you implement that algorithm in a given language. Creativity often means combining or using algorithms you know 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.

  1. Different algorithms can be developed to solve the same problem
  2. Different programs (or code) can be written to implement the same algorithm.

Furtermore the CSP Framework states:

  • 4.1.1A Sequencing, selection, and iteration are building blocks of algorithms.
  • 4.1.2G Every algorithm can be constructed using only sequencing, selection, and iteration.

The findMin problem and the other problems we solved with the Human Machine Language also have sequencing, selection, and iteration. Here's what they mean:

  • Selection: also known as "branching" 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 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.

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. 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.

Agenda

Getting Started (5 mins)

Activity (25 mins)

Wrap Up (15-20 mins)

Extended Learning

Assessment

View on Code Studio

Objectives

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 the Human Machine Language
  • Describe the properties of the Human Machine Language that make it a "low level" language.

Preparation

Links

Heads Up! Please make a copy of any documents you plan to share with students.

For the Students

Vocabulary

  • Algorithm - A list of steps to finish a task.
  • 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.

Support

Lesson Forum

Report a Bug

Differentiation and accommodations for this lesson

Teaching Guide

Getting Started (5 mins)

Conclusions from Find Min

  • If you didn't finish FindMin wrap up from the previous lesson, do it now.

  • Before moving on to the activity students should all have some solution to FindMin written in the Human Machine Language.

Creativity in Algorithms

Content Corner

This is almost verbatim a line from the CSP Framework.

  • 4.1.1E Algorithms can be combined to make new algorithms.
  • 4.1.1F Using existing correct algorithms as building blocks for constructing a new algorithm helps ensure the new algorithm is correct.

Transition to next challenge

One thing about algorithms is that once you know a few, and know how they work, you 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.

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 you don't have to reinvent the wheel.

For example, you 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? (no).

Today we'll challenge you with a few more problems that will require you to get creative!

Activity (25 mins)

Adding SWAP to Human Machine Language

Distribute: Activity guide - Human Machine Language - Part 2: Min To Front - Activity Guide

  • Put students into pairs
  • Review the first page of the activity guide and the addition of the "swap" command.

Do the example program

  • Give students a few minutes to trace the example program with their partner.

Review the example

Teaching Tip

You can either bring the whole class back together to review the example or you can check in with each pair as they finish the example and move them onto the challenge.

Make sure that students understand the example before moving on to the challenge.

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: 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.

As students work encourage them and challenge them to solve the problem in pieces.

Here are some suggestions you can make along the way:

  • IDEA: Solve move-to-front first

    • Remember: "Algorithms can be combined to make new algorithms"
    • Students should know a solution to find min, so they can put that out of mind for a minute.
    • So, start by assuming that you've found the min card, and writing a procedure to move some card to the front of the list, by swapping.
    • Once you've got that you can tack the two together

  • IDEA: Don't be afraid to invent a completely new algorithm

    • get creative - they might need or want to invent a whole new algorithm

Wrap Up (15-20 mins)

Review Min-to-Front Solutions

Teaching Tip

If students did some of the extra challenges (e.g. sorting, partition, etc.) you might give them an opportunity to showcase it for the class. Alternatively, if two or more people attempted a particular challenge you can put them together to compare solutions.

Put groups together to have students compare Min-to-Front solutions

  • You can also have groups trade algorithms to test out each others' solutions

If necessary, show or reveal one or more of the solutions from the answer key.

  • Make sure students see that it is possible to design a program to do Min-to-Front with the human machine language.

Identify Sequencing, Selection, Iteration in Human Machine programs

Remarks

The CSP Framework states:

  • 4.1.1A Sequencing, selection, and iteration are building blocks of algorithms.
  • 4.1.2G 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.

I'll give you a quick definition of each and you tell me if or where we saw it in our Human Machine Language programs...

Prompt:

  • "4.1.1B 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.

Prompt:

  • "4.1.1C 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” most commonly seen in if-statements in programs.

Prompt:

  • "4.1.1D 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.

Content Corner

Here is an example of a simple program written in IBM Assembly Language.

Discussion

After reviewing solutions there are a few points to make to wrap up this foray in to 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

Teaching Tip

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 students are programming in a high level language (like JavaScript). 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.

  • 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 (see graphic)

  • 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 - Video

NOTE: this video is 10 minutes long. If possible, and to save time, you might ask students to watch it outside of class.

Remarks

Learning to program is really learning how to think in terms of algorithms and processes. And it can be really fun and addicting. It also can make you feel like you have magical powers.

In the next lesson we'll start writing programs that a real machine (not a human machine) will execute. But since programming is really about thinking and problem solving your "human machine" skills will come in handy - reasoning about program is also about reasoning about what a computer can and cannot do, and what the given language you're using let's you and doesn't let you do.

If you didn't want to learn how to program before, perhaps this video will change your mind...

Extended Learning

Try out Human Machine Language on a computer: Try out this Plugged Version of the Human Machine Language designed by CS Principles teacher Brian Dahelm. Consider using this tool to plug in some of the activities in this lesson.

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

View full course alignment

Computer Science Principles

2.2 - Multiple levels of abstraction are used to write programs or create other computational artifacts
2.2.3 - Identify multiple levels of abstractions that are used when writing programs. [P3]
  • 2.2.3C - Code in a programming language is often translated into code in another (lowerlevel) language to be executed on a computer.
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.1E - Algorithms can be combined to make new algorithms.
  • 4.1.1F - Using existing correct algorithms as building blocks for constructing a new algorithm helps ensure the new algorithm is correct.
  • 4.1.1G - Knowledge of standard algorithms can help in constructing new algorithms.
  • 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.
5.2 - People write programs to execute algorithms.
5.2.1 - Explain how programs implement algorithms. [P3]
  • 5.2.1A - Algorithms are implemented using program instructions that are processed during program execution.
  • 5.2.1B - Program instructions are executed sequentially.
  • 5.2.1D - An understanding of instruction processing and program execution is useful for programming.
  • 5.2.1E - Program execution automates processes.
  • 5.2.1J - Simple algorithms can solve a large set of problems when automated.

CSTA K-12 Computer Science Standards (2017)

AP - Algorithms & Programming
  • 2-AP-17 - Systematically test and refine programs using a range of test cases.
  • 3A-AP-13 - Create prototypes that use algorithms to solve computational problems by leveraging prior student knowledge and personal interests.