Module 2 Unit 2 - Building an Algorithm using Computational Thinking

Callysto.ca Banner

Module 2 Unit 2 - Building an Algorithm using Computational Thinking#

Unit Learning Outcomes#

By the end of this unit, you will be able to

  • Create an algorithm, based on a task you want to solve

Can you Solve The Bridge Riddle?#

Please note watching this video is important for understanding the next sections in this unit.

from IPython.display import YouTubeVideo
YouTubeVideo('7yDmGnA8Hw0')

🗣️ Post-video Discussion#

Recall, the basic idea is that there are four people who have to get across the bridge – but only two at a time (carrying a lantern) and in a limited time – or else the zombies eat them. The crossings may involve some people going over the bridge, and then crossing back to help the others cross.

The problem is to find a method that gets all four people safely across the bridge in the limited time, knowing that some people cross more slowly than others.

How do we solve it? It is not good enough to say that a solution exists, we have to actually state what the solution is.

What does a solution look like? Well, it will be a list of who crosses the bridge (or comes back) and in what order.

You might have a list like this:

  • Prof and Janitor cross

  • Janitor comes back

  • Janitor and Lab Assistant cross

  • Lab Assistant crosses back

  • Lab Assistant and “me” cross

We need an algorithm that finds a solution for us. One algorithm would be to try all possible ordering of who crosses and when, subject to the rules. Add up the time for each ordering, and find one that is less than the allotted time.

A better algorithm might be to notice that we need to minimize the crossing by the slow people. So you might want to only consider orderings where the Janitor and Prof go across together, but do not ever go back.

For the computer to “read” the algorithm, you might want to write the orderings symbolically, rather than as English sentences. This could simplify the code.

You might also look for patterns. For instance, in the example list, it looks like people cross forward on the odd numbered steps, and cross back on the even numbered steps. Is that always true? Does that reduce the number of possible lists of crossings?

Is there ever a case where 2 people would cross in the backwards direction? If true, that also limits the possible lists.

Bridge

Activity#

  • Can you list all possible options for crossing that get all 4 people across? How many are there?

  • Of these listings, which one takes the least time?

  • Is there one that takes a maximum amount of time?

It would be great to have a tool that lets you and your students explore these computational ideas. This is the motivation behind the Callysto project – to get those tools in your hands. In the next module, you will learn about Jupyter notebooks. These are online documents that let you combine your lecture notes with pictures, graphics, and computer code, so your students can learn how to connect ideas to code. It is a powerful way to learn computational thinking.

More examples

Callysto.ca License