Graph Paper Programming

Meta Description


A fun and easy activity to introduce general programming concepts and to help anyone understand what an algorithm is using just graph paper and markers.

Learning Objectives


Understanding how coding works in general.

Understanding what an algorithm is and how to make one.

Awareness that computers work by following an algorithm.

Key Terms


Algorithm
A list of commands or steps that must be followed in order to complete a task.

Central Processing Unit (CPU)
This is the core instrument responsible for running and managing all arithmetic and logical processing tasks.

Coding
Programmers use coding to build computer programs that can then be used in different applications around the world.

Computer Program
This is usually a piece of software (for example an application) which runs on electronic devices (such as a PC or mobile phone) that performs some functions in order to meet the needs of the user.

Graphical Processing Unit (GPU)
This is the core instrument responsible for running and managing all graphic-related tasks, i.e. image and video processing.

Random Access Memory (RAM)
The storage space for temporary data that is being processed in the CPU.

Step 1
Mark as many 4-by-4 boxes as possible on the sheet of graph paper. Some graph papers already have these boxes marked out. Each 4-by-4 subgrid will be a used for one round of the game.

Step 2
Use the marker to draw a star in the top left-hand corner of each sub-grid. The stars mark the starting point of each game.

Step 3
Give each subgrid a different finishing point, such as the box in the bottom left corner or the box in the top right corner of the subgrid.

Step 4
‘Obstacles’ (filled boxes) can then be added to the the grid to make the activity more interesting, particularly for older individuals. It is imperative that the algorithm must not be allowed to pass through these filled boxes.

Step 5
The grids are then given to the participants in the experiment and they are tasked to create an algorithm which will trace a path from the start box to the finish box, avoiding any ‘obstacles’ (filled in boxes) along the way.

The algorithm can be written down. When creating the algorithm, the following commands are allowed:

Move one box right.
Move one box left.
Move one box down.
Move one box up.

Participants may need to be guided through the construction of the first algorithm.

Step 6
Once the tasks are completed, invite participants to explain the reasoning behind their algorithms.

  • Alternative commands could be used to make the activity more interesting. For example, diagonal movements between boxes may be allowed, or a rule which prohibits algorithms entering the same box twice could be introduced.
  • The activity could be changed to create a desired pattern on the grid rather than move to a finishing point by using the additional command: Fill-in box with a marker.
  • The size of the sub-grid could be increased from 4 boxes by 4 boxes to a larger size, say 6 boxes by 6 boxes and more obstacles could be added.
  1. Reuse and recycle any extra papers when possible!

When we want to travel from point A to point B, our brain chooses the path and sends signals to our legs to move towards our destination. Similarly, the ‘brain’ of the computer – its central processing unit (CPU)- is continuously sending commands to different parts of the computer system so that different processes can be carried out. These processes could include putting a screensaver on the monitor or opening a web browser. The CPU knows how to carry out these processes because it is instructed by a computer program. Computer programs and their associated algorithms contain a list of instructions which explain how to achieve certain tasks – they are a lot like the path chosen to move from point A to point B.  Thus, computers can be used to carry out different jobs by using different computer programs. For example, a word processor can be used to write a letter and a web browser can be used to surf the internet.

What is an algorithm?
A list of steps that are followed to finish a task.

What is a computer program?
An algorithm that was coded and can be run by a computer.

Can only one algorithm be used to solve a specific problem?
No. Multiple algorithms can be created to solve the same problem.

What do we have to consider when choosing the best algorithm to solve a problem?
In this case, the algorithm with the shortest number of steps would be the best algorithm to use.

Are algorithms only used in computing?
No, they can be used to solve problems in mathematics as well (they require a different approach in the mathematical case).

The aim of this activity is for participants to grasp the concept of an algorithm. Each step that is made on the graph paper represents a small part of the algorithm. Hence, an algorithm can be used to describe a number of steps one after the other.

Algorithms are used everywhere in life. Even in the kitchen, when a person is following each step of a recipe to cook the next meal. They are even used in mathematics to describe each step of a method. However, the most notable example of algorithm use is in computer science. In computer science, algorithms are used to tell the computer what it should do.

The way you design an algorithm is completely up to the creator. There is no good or bad algorithm as long as it solves the problem you intended it to do. However, it is true that one algorithm can be more efficient than the other. The creator must always aim to keep the algorithm simplistic, fast and easy for other people to understand.

In a computer, everything is powered by the central processing unit (CPU). The CPU is responsible for running and managing all the computational processes that the computer requires to run efficiently. Nowadays, CPUs are more customizable such that consumers are able to choose the clock speed and the number of cores amongst other factors. Multiple cores allow users to run multiple computational processes in one go.

Hence, a computer algorithm is run by the CPU. However, it is important to keep in mind that an algorithm can only be as fast as the CPU can process it. For heavy and complex algorithms, a user might require a computer with a high number of cores and a high clock speed. Sometimes, a user might require additional power especially when it comes to video processing and gaming. In this case, a GPU (Graphical Processing Unit) can be used. The GPU works hand in hand with the CPU and processes graphical based algorithms. This increases the efficiency and overall speed of the computer.

An interesting fact is that the CPU also uses algorithms to manage its processes. Two of these algorithms are the First Come, First Served (FCFS) scheduling algorithm which manages the processes one after the other without one having a priority over another. The other algorithm is the Shortest-Job-Next (SJN) scheduling algorithm which manages the processes by running the task which takes the shortest time possible to compute.

Ideally, an algorithm must be designed to be as efficient as possible. As mentioned before, the speed algorithm is limited by the number of processes the CPU can handle every second. However, there are various other factors that make different algorithms more efficient than the other. For example, an algorithm that minimises the number of steps it takes to get to the same result is usually said to be the better and faster algorithm. The memory of the computer can also be an important aspect. When a user is working with big data, the computer must create a large number of partitions to store the temporary values it is calculating. The amount of temporary data a computer can handle depends on the RAM (Random Access Memory). When the computer reaches the RAM limit, the computer is forced to slow down.

Additionally, there might be a case where two different methods can lead to the same result. However, one algorithm is accurate and slow and the other algorithm is not so accurate but fast. The tradeoff between the two algorithms is completely based on the user’s needs and requirements. For example, when the algorithm is used to process data for a scientific experiment, the algorithm is expected to give a more accurate representation and hence the first algorithm mentioned should be chosen.

Application
Computers use algorithms to carry out all kinds of functions and tasks including word processing, calculations, running computer games and searching the web.

Although computers are often used for clerical work and leisure activities, powerful algorithms have increased the problem-solving potential of computers. Machine learning and artificial intelligence algorithms are currently being used by the technology industry in a range of applications including robotics, big data processing and managing of social media platforms.  These algorithmic tools are gaining speed because they give machines the ability to learn and improve its own architecture (the current algorithm it is using). This is leading to better processing of data. Companies are investing heavily in the development of these algorithmic tools because they promise to improve user-machine interaction and the adaptability of computer systems to new environments.

Research
Apart from storing and processing information using bits (0s and 1s), quantum computing uses quantum bits (known as qubits) which enable them to process 1s and 0s both at the same time. This is a more complex and advanced way of transmitting and maintaining information than is used in typical computer systems. Ultimately, these powerful machines will be able to enhance computational performance up to a level never experienced before.

In the one of the multiple theoretical quantum computing projects, O’Donnell and Say collaborated to study on the computational complexity of time travel and they showed that there was not much algorithmic benefit of using a fixed number of time-travelling quantum bits rather than single time-travelling classical bits.

  • Challenge participants to finish the required task with the minimum amount of algorithmic steps possible. The sheets can be designed so that there are a number of different paths which lead to the destination. Friendly competition between participants can be encouraged.
  • Question participants why the algorithms should be as short as possible.
Download as PDF

Education

Time Required

  • ~30 minutes

  • Preparation: 5 minutes

  • Conducting: 20 minutes

  • Clean Up: 1 minute

Recommended Age

Number of People

Supervision

Location

Materials

Graph paper

Markers

Paper to write on

Contributors


First published: November 15, 2017
Last modified: November 16, 2017

Was this experiment helpful?

 Yes
 No

We can always improve. Tell us how.