Web Design/Introductory algorithm challenges

From Wikiversity
Jump to: navigation, search
Web Design Introductory algorithm challenges
DeliciousFruitFromOSWD.png
This page is part of the Web Design project.
CSSZenGardenLikeTheSea.png
Learning to think like a computer can be a struggle and take a lot of practice!

One of the most difficult things about learning any new language (spoken or computer) is learning how to express yourself!

Most people seem to think that it's much easier to learn to read another language - or even listen and understand bits and pieces - but much more difficult to use that new language to express your own ideas! Why do you think this is? It's no different for us when we're learning computer programming... it is a totally new language - a new way of expressing ideas. It takes a lot of time and practice to be able to express simple ideas, let alone become fluent! These activities are designed to help you start speaking your first words in computer programming.

An algorithm is a process used to solve a specific problem. It's just like a recipe - a small set of instructions in a language that takes some ingredients and does something with them to produce a cake! We're not going to learn anything too complicated about algorithms (if you're after more detail, you can read the Wikipedia article on Algorithms), we're going to instead focus on learning to think like a computer and express our ideas to a computer!

We actually use algorithms all the time in our lives, from serving people a cup of coffee, through to making a decision whether to go out on Saturday night... but we do it all without thinking because it's so familiar to us. For the following tasks, we might need to slow down and examine our own thinking (also called metacognition) to find out exactly what goes on in our minds!

If you find it helpful for revision, you might also be interested in the Introductory algorithm quiz questions

Challenge 1: Be specific and in the right order![edit]

We'll start with something that you've done so often in life that it's probably hard to actually define what you do - serving coffee! Here's the scenario:

You've just purchased a new toy called a Servitude3000 - a small robot that can handle most tasks around the house and understands plain English. After adoringly giving him the name "ScrapMetal', you decide to invite a few friends around to show off!

Note: Even though Scrappy understands plain English, he needs everything spelled out very precisely. Any ambiguity and he starts doing his dance routine for "Do the Locomotion", so be very careful!

After inviting Neville, Bhim and Addye over for some coffee, you decide to get Scrappy ready. Using the examples below from Scrappy's instruction manual, write down the steps that you will take to make a cup of coffee for your friend Neville who's always early.

Note to self: you remember that Neville doesn't take any sugar, but can't quite remember whether he has milk in his coffee!

Example statements to use (not in order, and not exhaustive - you'll probably need more!)

  • Pour ...... into ......;
  • Get ...... from ......;
  • Give ...... to ......;
  • Put ...... in/on .......;
  • Fill ...... with ......;
  • Move to ......;
  • If Neville takes milk then do the following:

Once you've got your algorithm down, give it a name, such as ServeNevilleCoffee and get someone else to follow your algorithm to see if it works! It should look something like this:

PROCEDURE ServeNevilleCoffee

  Get mug from cupboard;
  ... (lots of instructions here)
  ...
  Give mug to Neville;

END PROCEDURE

Isn't it amazing how complicated a simple process like making a cup of coffee can be!

Challenge 2: Writing Algorithms Visually[edit]

Milk or no milk?

Some people are much better at thinking visually - with pictures and lines. Flowcharts provide a way for us to do exactly that: visualise our algorithms! You can read more about Flowcharts on Wikipedia.

Click on the provided image and print out the full size version (or just draw it yourself!), and then have a go at adding arrows to indicate how our ServeNevilleCoffee algorithm works!

As usual, test your algorithm by running through it using your flowchart. If it seems to work, take a few minutes to convert this into pseudo-code. Did you find it easier to write your pseudo-code from the flowchart? If so, perhaps flowcharts are the way to go for you!

Challenge 3: Making decisions in an algorithm[edit]

The doorbell rings and it's your next friend, Bhim, who has a sweet tooth. Now you'll need to modify your algorithm so that you can put a teaspoon of sugar into our coffee as required by your friends! Although, you can't quite remember how many sugars Bhim takes...

Create a new algorithm called ServeBhimCoffee using the pattern above, but adding the following commands for Scrappy:

  • Put a teaspoon of sugar into mug;
  • If Bhim likes 1 sugar then do the following:
  • If Bhim likes 2 sugars then do the following:
  • End If

Your new algorithm should follow this pattern (you'll need to fill in the instructions!):

PROCEDURE ServeBhimCoffee()

  Get mug from cupboard;
  ... (lots of instructions here)
  ...
  Give mug to Bhim;

END PROCEDURE

As always, test your code by pretending to follow it yourself. When you are happy with your code, create a visual flowchart for your ServeBhimCoffee algorithm.

Challenge 4: Loops are repetitions[edit]

You might have noticed when testing your algorithm above that it works fine if Bhim likes 1 or 2 sugars, but if he likes 3 sugars then we've got a problem. Of course we could always add the following to our algorithm:

  If Bhim likes 3 sugars then do the following:
    Put teaspoon of sugar in mug;
    Put teaspoon of sugar in mug;
    Put teaspoon of sugar in mug;
  End if

but then what if he asks for 4 sugars? 5 sugars? We can't keep adding more and more code to our algorithm like this! We need to ask our friends how many sugars they would like and then remember this value (we might use a variable called 'numsugars' to remember this). But how will we modify our algorithm so that it puts this many sugars in the cup? Unfortunately we can't just say to scrappy "put 4 sugars in the cup" - if you think about your own thought process, you count out each spoon without thinking too much. If you don't think this is the case, imagine if a friend asked for 13 sugars in their coffee!

Try arranging the following statements in an algorithm for putting the right amount of sugar in cup:

  • Set numSugarsInCup to 0;
  • Add one teaspoon of sugar to cup;
  • Add 1 to numSugarsInCup;
  • Ask Bhim how many sugars he likes and remember this as numSugars;
  • While numSugarsInCup < (is less than) numSugars, do the following:
  • End While

Re-write your ServeBhimCoffee() algorithm using this new way of adding sugar. Again, try getting someone else to follow your execute your algorithm for you and see if it works!

How many sugars?

Once you're happy with your algorithm, let us see how Repitition works with a flowchart! Try re-arranging the displayed flowchart symbols to describe an algorithm that adds the correct amount of sugar to your cup:

  • click on the "How many sugars?" image,
  • print out the full resolution version,
  • cut out the shapes
  • have a go at arranging them on a blank sheet of paper
  • when you're happy with your arrangement, stick them with glue and add your arrows!

As always, test your algorithm by going through your flowchart yourself, or ask others to test it for you! Make sure that you try it with both 0 sugars and 3 sugars.

Challenge 5: If-statements and repetition[edit]

Making toast for your friends[edit]

You're away on a holiday weekend with a bunch of 15 friends. You're in charge of programming Scrappy the robot to toast the bread slices in the morning! Initially, let's assume that your toaster can only toast one slice at a time.

You will need:

  • a variable to store how many slices of toast we need to make
  • a variable to store how many slices of toast have been made already (you'll need to set it to 0 initially)
  • a "while-loop" that keeps on going until Scrappy's made all the toast required.

Here's some suggested statements (not in the right order):

  • Press Toaster down
  • Put slice of bread in toaster
  • add 1 to .............
  • Set .............. to 0
  • While .......... is less than .............
  • Ask how many people would like toast and remember as .............

Have a go at working together with a few others to write your procedure for Scrappy! Make sure you test it by running through your code with real examples!

If you get a working procedure, try the following extra challenges:

  1. Modify your procedure to work with a new toaster that can toast 4 slices at a time. Initially, don't worry if you toast a few extra slices than required.
  2. Modify your procedure so that it toasts only the exact number of pieces in the most efficient way!

Setting the table for a dinner party[edit]

Everything you need is stacked on the bench. 8 Forks, 8 knives, 8 spoons, 8 plates and 8 glasses. Scrappy knows the seats as Seat 0, Seat 1, Seat 2, ...., Seat 7.

Here's some suggested statements:

  • Put .......... on ..........
  • Set .......... to 0
  • Move to seat number ..........
  • Get .......... from ..........
  • Add 1 to ..........
  • while .......... is less than ............

To make this one really efficient, we'll need to learn what an Array is, but we can still do it without this knowledge.

Adding up the numbers from 1-50[edit]

You might want to try this one in a group! Have a go at designing an algorithm to add all the numbers between 1 and 50! Try doing this with a flowchart first, then convert your flowchart into pseudo-code.

Hint: Make sure that you break this problem down into two smaller problems:

  1. Design your algorithm to count from 1 to 50 (you will need statements like "set myCounter to 0" and "Add 1 to myCounter".
  2. Modify your algorithm to keep a running tally, adding up the numbers as you go through.

Challenge 6: Something from your everyday life[edit]

Take 5-10 minutes to choose a simple task from your own everyday life (it could be "leaving the house", "rolling a cigarette", or "tending the garden") and create an algorithm describing your task! Try to find something that involves making simple decisions as well as repeating some steps.

If you find it difficult to write pseudo-code, have a go at creating a flowchart instead! Once you have described your algorithm using a flowchart, you can then turn it into pseudo-code a lot easier.

Challenge 7: Passing arguments![edit]

Finally your friend Addye arrives - and she's brought 4 other friends too! We don't really want to create a separate algorithm for every person...

We need to quickly generalise our ServeNevilleCoffee() and ServeBhimCoffee() algorithms into something like:

PROCEDURE ServeFriendCoffee(friend)
   ...
   If friend has milk then do the following:
     ...
     ...
   ...
END PROCEDURE

That way we can just call ServeFriendCoffee(Neville) or ServeFriendCoffee(Bhim) and it should work. Use this template to create your own ServeFriendCoffee algorithm.


Challenge 10: Ordering objects (a sorting algorithm)[edit]

(Too hard for here!) Alls these every-day tasks seem a long way from our JavaScript, but bear with us! What we're learning is how to use the fundamental structures of all computer programming languages:

  • Sequence (executing our statements in order)
  • Selection (if-statements, or decision statements)
  • Repetition (loops such as while or for-each loops)

One last task before we move out of the real world! If you're in a class, get a bunch (say 8) people to stand up in a row. (If you're not in a class, any bunch of objects of different heights will do!)

Sorting without thinking[edit]

First, just have a go at re-arranging yourselves into order - from tallest to shortest.

What strategy or algorithm did you use? Would this work with Scrappy?

Your first sorting algorithm[edit]

We want to see if we can get scrappy to arrange your friends into order! Working in small groups where possible, see if you can come up with an algorithm together!

In addition to the statements we've already used, you may need some of the following:

  • currentPerson is person number 1
  • If ..... > ...... then do the following:
  • tallestPerson is person number 1
  • Remove tallestPerson out of the group
  • Measure the height of the currentPerson and store the measurement as currentPersonHeight
  • set tallestPerson equal to the currentPerson
  • set maxheight equal to currentPersonHeight

Note: This activity is quite difficult! Don't worry if you need lots of help! It's pretty amazing to think that we do all this automatically without even thinking much about it!