1.3 Truth tables

? Learning Objectives

  • Define the term ‘decomposition
  • Define the term ‘algorithm
  • Decompose a problem
  • Define the term ‘sequence’ and use sequence in algorithms and program code
  • Interpret error messages
  • Correct errors in ordering
? Key Vocabulary

  • Decomposition
  • sequence
  • algorithm
  • error
  • abstraction
  • order

? Algorithms

What is an Algorithm?

An Algorithm is a sequence of instructions or steps that can be followed by humans and
computers to complete a specific task.
  • An Algorithm is a series of steps that can be followed to complete a specific tasks.
  • It is not the same thing as a computer program which is an implementation of an algorithm!
  • We use algorithms as part of the planning stage, so that before we can write the program, we have to work out the steps needed to solve a given problem.
  • A working algorithm will always finish and return an answer or perform a series of tasks that it was supposed to.
  • We can use algorithms to carry out everyday tasks, often without really thinking about them.
  • Here are some examples of algorithms that you may be familiar with:
    • Baking a Cake,
    • Recipes,
    • Directions,
    • Knitting Patterns,
    • Instruction manual for building something.

Here’s a Problem

  • How can we create an algorithm to show the steps in getting ready for school:
    1. Get out of bed.
    2. Take a shower and clean teeth.
    3. Get dressed.
    4. Turn on the kettle.
    5. Put bread in the toaster and turn it on.
    6. Wait for the kettle to boil and make tea.
    7. Wait for bread to toast, butter it and add Jam.
    8. Drink tea and eat toast.
    9. Gather school books and put in bag.
    10. Put on shoes and coat.
    11. Leave the house.
The Algorithm above shows the sequence of tasks. Different people will design different
algorithms, as they will do things in a different order, meaning there can be many
solutions to the same problem. Some of these tasks could be further devided into
sub-tasks as they might be made up of smaller steps.
For example "Cleaning your Teeth' could involve many different steps including applying
toothpaste to the brush, checking if all teeth are clean and rinsing out your mouth etc...

Steps to creating an Algorithm

  1. An algorithm does not have to be written in code.
  2. The first steps to working out the design will be to draw diagrams or list the steps involved.
  3. Break down the problem and then structure a solution using standard tools called flowcharts and pseudocode.
  4. Only when the solution has some structure can you effectively start coding it.
  5. Pseudocode is the first step to actually coding your solution, as it outlines the programming contructs, but doesn’t rely on any specific language syntax.

? Decomposition

Learn It: Decomposition

Let’s break it down!

Decomposition is the process of breaking a problem down into smaller, simpler steps or
stages so that problems can be solved much easier.
  • It is one of the four cornerstones of Computational Thinking.

Advantages of using Decomposition

  • Breaking a problem down into smaller sub-problems has a number of advantages:
    1. Smaller problems are easier to solve than larger problems.
    2. Each sub-problem can be developed separately, making planning and working to a timescale easier.
    3. Sub-problems are easier to distribute amongst a team than one large problem.

Sub-Problem Example

  • Think of decomposition as like being faced with a 15ft wall. It’s unrealistic to think you could just jump/climb to the top.
  • However, if we break that wall down into 15 1ft tall steps, we can tackle one step at a time to make it to the top.
Decompositionexample.png

Checkmate

  • Let’s think of another example… Chess!.
  • If we were going to create a program for a chess game, it’d seem quite daunting at first.
  • However, if we Decompose the problem, we see the individual problems within a chess game.
Chessgameexample1.png
  • Starting with just /”chess game”/ we can Decompose it into 5 problems which are easier to solve.
  • But this can be Decomposed even further…
Chessgameexample2.png
  • This is now much easier to understand and can be used to create a flowchart or pseudocode.

? Badge it – Decomposition

? Silver Badge

Decompose the steps involved in the game of Rock, Paper and Scissors:

  • Decompose the game of Rock Paper Scissors
  • You can do this as a numbered list or bullet pointed list
  • Upload to Algorithms – Decomposition: Silver on BourneToLearn
? Gold Badge

Create a flowchart for the game:

  • Use your silver decomposition to create a flowchart
Flowchartsymbols.png
  • Make sure you use the correct symbols!
  • Upload to Algorithms – Decomposition: Gold on BourneToLearn
? Platinum Badge

Using your algorithm, code a solution for the game:

  • Using your numbered list or bullet pointed list and flowchart, write the solution in Python
  • Upload to Algorithms – Decomposition: Platinum on BourneToLearn

Complete the following:

  1. Write a definition of abstraction.
  2. Create a guide with a series of top tips for anyone looking to abstract a problem.
  3. Upload to Algorithms – Abstraction: Gold on BourneToLearn

Write an algorithm is Pseudocode for the following problem:

  • Weight Conversion Program that takes a user input as either KG or Stones and then stores this value in a suitable variable.
  • Give the user a choice of converting either KG to Stones or Stones to KG.
  • Finally output the correct conversion value to the user.

? Abstraction

Learn It: Abstraction

Abstraction is the process of removing all unnecessary details from a problem, until
all that remains is what is needed to solve the problem.
  • It is also one of the four cornerstones of Computational Thinking.
  • We use this to make the problem simpler but also consequently less realistic.
  • Watch the video below and see if you can spot how Abstraction is used:

? Badge it – Abstraction

? Silver Badge

Complete the following abstraction task:

  • Perform Abstraction on this classroom.
  • Think about what details can be Abstracted.
  • Do we need the walls? chairs? keyboards? Think about the seating plan as an example.
  • Produce an Abstracted image of the classroom (Paint/Word/PowerPoint).
  • Upload to Algorithms – Abstraction: Silver on BourneToLearn
? Gold Badge

Complete the following:

  1. Write a definition of abstraction.
  2. Create a guide with a series of top tips for anyone looking to abstract a problem.
  3. Upload to Algorithms – Abstraction: Gold on BourneToLearn
? Platinum Badge

Write an algorithm in pseudocode for the following problem:

  • Weight Conversion Program that takes a user input as either KG or Stones and then stores this value in a suitable variable.
  • Give the user a choice of converting either KG to Stones or Stones to KG.
  • Finally output the correct conversion value to the user.