beanz Magazine

Computational Thinking

Randy Robertson on Flickr

The ability to identify patterns, decompose large problems into small parts, develop algorithms to solve problems, and generalize to find solutions.

In certain circles there is a fairly well-known game called fizzbuzz. When played correctly, the outcome looks as follows:

1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz, ...

Can you identify any patterns?

In the its current state, the fizzbuzz sequence likely appears as a hodgepodge of numbers and funny-sounding words. But if we break it into its two main parts, the patterns become much clearer:

Let us start with what I call the fizz portion:

1, 2, fizz, 4, 5, fizz, 7, 8, fizz, 10, 11, fizz, 13, 14, fizz, …

Now consider the buzz part:

1, 2, 3, 4, buzz, 6, 7, 8, 9, buzz, 11, 12, 13, 14, buzz, …

Did you notice that the fizz part of the pattern can be described as counting by one and replacing every third number with the word fizz? Likewise, in the buzz part of the pattern every fifth number is replaced with the word buzz. The original sequence is formed by combining the fizz pattern with the buzz pattern.

Pattern recognition and decomposition are two characteristics of computational thinking, a fundamental skill for computer science. In this case we took a complicated sequence and decomposed it into two strands to help us recognize what numbers are replaced by fizz, and what numbers are replaced by buzz.

In 2006, computer scientist Jeannette Wing (at the time at Carnegie Mellon University) wrote a paper introducing much of the world to the term “computational thinking”. In the article she describes one characteristic of computational thinking as “a way in which humans, not computers, think”.

Imagine teaching a human, let’s say a friend, how to play the game of fizzbuzz. It would be helpful to come up with a step by step explanation of the game. This is something computer scientists do when they program a computer. It is a third characteristic of computational thinking: algorithm development. In the case of explaining fizzbuzz to a friend, the algorithm might go as follows:

  1. Start counting at 1.
  2. Every time you get to a number divisible by 3, replace the number with the word fizz.
  3. Every time you get to a number divisible by 5, replace the number with the word buzz.
  4. Every time you get to a number divisible by both 3 and 5, replace the number with the word fizzbuzz.

If your friend has completed the 4th grade or so, and follows along well in math class, she can likely use this algorithm to play fizzbuzz. However, if she is unfamiliar with the word divisible, steps 2-4 need further decomposition.

In September of 2016, ten years after writing her original paper on computational thinking, Jeanette Wing participated in a Google hangout with members of the CSTA in which she broadened her definition of computational thinking. Not only is it a way that humans think, it is a way for any computer, human or machine, to solve a problem. In light of this, let us take a look another look at fizzbuzz and design an algorithm for a machine-computer to follow.

For this task, not only do steps 2-4 need to be decomposed, several more details must be added to the algorithm.

Like some of our friends, most computers programming languages do not understand the word divisible. This forces the programmer to rethink divisibility in a way that the computer can handle. Programming languages often make use of the idea of remainders when faced with divisibility. For example, if a number is divisible by 3, we know that when we divide it by 3 the remainder is 0. The same idea holds for divisibility by 5. This way of thinking about divisibility comes from modular math, and in many programming languages it is written with the percent sign.

Using pseudocode, we have something along the lines of:

if x%3 == 0 say fizz
if x%5 == 0 say buzz
if x%3 == 0 and x%5 == 0 say fizzbuzz

Computers always need to be told when to start and stop, so if we want to start at 1 and stop at 100, the pseudocode might look something like:

for (x = 1; x <= 100; x = x+1):
    if x%3 == 0 say fizz
    if x%5 == 0 say buzz
    if x%3 == 0 and x%5 == 0 say fizzbuzz

Now we have a two complete algorithms, one for human computers and another for machine computers. The machine algorithm is a bit more difficult for most people to understand because it involves a layer of abstraction. Abstraction is the last main characteristic of computational thinking that we will learn to begin to become better computer scientists. It is perhaps the most challenging part of computational thinking, but it may also be the most powerful.

To demonstrate, let us add a bit more abstraction to our pseudocode. There is nothing particularly special about the numbers 3 and 5 when it comes to replacing numbers in a sequence by words. Likewise there is nothing particularly special about the words fizz and buzz. With a little more abstraction, we can create a more general, customizable, game of fizzbuzz. Following the pseudocode below, the computer would be programmed to allow the user to choose her own words for fizz and buzz, and decide what numbers she will replace:

word1 = enter a word
word2 = enter another word
divisor1 = pick the first divisor
divisor2 = pick the second divisor

for (x = 1; x <=100; x = x+1):
    if x%divisor1 == 0 say word1
    if x%divisor2 == 0 say word2
    if x%divisor1 == 0 and x%divisor2 == 0 say word1 word2

As we add more variables to the code and eliminate specific numbers, the algorithm becomes more abstract. It takes people more effort to read through and understand. But with the abstraction comes more flexibility and more opportunity for quick modifications to the game. Sometimes it even allows one algorithm to be applied to solve different problems, provided they can be formulated in the same way.

As it turns out, these skills that we develop when we practice computational thinking are applicable far beyond computer science. Yes, they are very useful when we write code, and they are essential to understanding the foundations of computer science. However, they apply to just about every branch of science and engineering. They even make their way into the humanities and social sciences.

The ability to identify patterns, decompose large problems into smaller parts, develop algorithms to solve these problems, and abstract or generalize to find solutions, is cross-curricular. Just about all fields welcome those with strong problem solving skills and practicing computational thinking is a great way to become a superior problem solver!

Learn More

Computational Thinking by Jeanette Wing

https://www.cs.cmu.edu/~15110-s13/Wing06-ct.pdf

Computational Thinking, 10 Years Later

https://www.microsoft.com/en-us/research/computational-thinking-10-years-later/

Interview with Jeanette Wing, 2016

https://www.youtube.com/watch?v=fSoknljUI4Q&feature=youtu.be

Computational Thinking Workshop Presentation

https://csta.acm.org/Curriculum/sub/CurrFiles/WingCTPrez.pdf

Stephen Wolfram: How to Teach Computational Thinking

http://blog.stephenwolfram.com/2016/09/how-to-teach-computational-thinking/

Exploring Computational Thinking (Google for Education)

https://www.google.com/edu/resources/programs/exploring-computational-thinking/

Center for Computational Thinking Carnegie Mellon

https://www.cs.cmu.edu/~CompThink/

Computational Thinking

https://en.wikipedia.org/wiki/Computational_thinking

Fizz Buzz

https://en.wikipedia.org/wiki/Fizz_buzz


Also In The December 2016 Issue

Hour of Code and EU Code Week are events designed to introduce kids, young adults, and others to programming and computer science.

Real life treasure hunts are a way to get outdoors, learn map skills, and have fun finding hidden caches near you.

A trainable puppy plus treats plus technology equals a dog that can send selfies. Here's how.

An app to help kids remember important stuff like feed your pets, brush your teeth, and smile.

These books include lots of great projects to work on by yourself or with others, from Scratch and Minecraft to fun maker space projects.

The mBot robotics kit is an excellent comparatively low-cost way to begin working with robots.

There are maybe a bazillion Raspberry Pi projects online. Here are really fun projects plus links to find more.

The Wayback Machine lets you travel back in time to see old websites. Plus the Internet Archive has thousands of vintage games, software, books, and more.

Eating dog food doesn't sound like much fun but it's an important part of creating software.

The ability to identify patterns, decompose large problems into small parts, develop algorithms to solve problems, and generalize to find solutions.

To celebrate this wonderful time of the year, let’s create some holiday music using Sonic Pi on our Raspberry Pi.

This project shows how to use the pygame code library to move simple animations with the Python programming language.

This project, shows you how to create your own random password generator in the C# programming language.

These projects mix science and technology in interesting ways. Sewing and electronics, for example, is a different way to learn about electronics.

Links from the bottom of all the December 2016 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for December 2016.

What sounds like a country western dance actually is an efficient way to sort large sets of data randomly.