Lesson 01: Introduction To Algorithms
Specification Points Addressed in this lesson:
- Understand and explain the term algorithm
- Understand and explain the term decomposition
- Understand and explain the term abstraction
- Use a systematic approach to problem solving and algorithm creation representing those algorithms using pseudo-code, program code and flowcharts.
- Explain simple algorithms in terms of their inputs, processing and outputs.
- Determine the purpose of simple algorithms.
1. Algorithm
In Computer science we define
An algorithm is a precise set of instructions that solves a problem when followed.
Think of it like a recipe for cooking a dish. It provides a step-by-step guide to get from your raw ingredients (the input) to your finished meal (the output).
In the tower of Hanoi game, the problem is to move all the disk from tower 1 to tower 3 with the smallest possible moves without putting a larger disk on top of a smaller disk.
The following algorithm will solve the problem:
- Move A to Tower 3
- Move B to Tower 2
- Move A to Tower 2
- Move C to Tower 3
- Move A to Tower 1
- Move B to Tower 3
- Move A to Tower 3
If we follow the algorithm above we can achieve our objective (solve a problem) in 7 moves. It turns out that 7 moves is the optimal solution for this problem.
2. Decomposition
This algorithm can be outlined in the following chart.
Here we have broken down the big problem (moving 3 disks from tower 1) into three smaller problems:
- Move 2 disks from tower 1 to tower 2
- Move 1 disk from tower 1 to tower 3
- Move 2 disks from tower 2 to tower 3
When the three steps above are combined we would have solved the larger overall problem. This approach is called problem decomposition.
Problem decomposition is breaking down a problem into a number of sub-problem so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.
Now if we should examine steps 1 and 3 in our decomposed solution above, we will can further break down the problem as illustrated below.
Decomposition involves breaking down a large or complex problem into smaller, more manageable parts. It’s like solving a big jigsaw puzzle by focusing on smaller sections one at a time. In the diagram above we have further decomposed steps 1 and 3, which in and of themselves are repeating instructions therefore they can be written using a subroutine (more on this later).
In programming, we might decompose the task of creating a digital clock into smaller tasks like getting the current time, formatting the time into hours, minutes, and seconds, and displaying the time. Here’s an example in Python of a program decomposed into smaller functions:
def get_hours(minutes_total):
return minutes_total // 60
def get_minutes(minutes_total):
return minutes_total % 60
minutes_total = 125
hours = get_hours(minutes_total)
minutes = get_minutes(minutes_total)
print(f"{hours} hour(s) and {minutes} minute(s)") # Output: 2 hour(s) and 5 minute(s)
In the Python program example above the problem is to display how many hours and minutes are in a given total minutes. The problem is decomposed by calculating the hours in get_hours() then the minutes in get_minutes() and finally the results are printed to the screen.
3. Abstraction
In computer science
Abstraction means removing unnecessary details and focus on the essential information in a problem.
It’s like looking at a map. You don’t need to see every single house and tree to understand the layout of a town, therefore we ignore unnecessary information and focus on what is important.
In our tower of hanoi problem, we can create an algorithm (eg a function) called “move disk” to solve our problem.
In order to use this algorithm we only need to know:
- its purpose
- what information the algorithm needs in order to produce the result
There is no need to know how the algorithm works, the internal working of the algorithm is hidden, in other words it has been abstracted. This abstracted model can them be further developed and an interface is created as outlined below.
An interface consist of the name of an algorithm (Move Disks), the purpose, the expected inputs and output data type. Here an interface contains the minimum information that is needed in order to use the abstracted model.
In programming, abstraction helps us use complex systems or operations without understanding all the details. When we use a function to calculate the average of a list of numbers, we don’t need to know exactly how Python’s sum()
or len()
functions work. Here’s an example of a Python program that finds the average of numbers in a list:
def calculate_average(numbers):
total = sum(numbers) # We use sum() without knowing how it works
count = len(numbers) # We use len() without knowing how it works
return total / count
numbers = [4, 2, 9, 6, 5]
print(calculate_average(numbers)) # Output: 5.2
There are two observation to be made from the example above:
- the
sum()
andlen()
functions are examples of abstraction. We use them to perform complex operations without needing to understand all the details of how they work. - calculate_average() is itself an abstraction. We have created an interface that can be used with other list, so later in the program if we want to find the average of another list we can simply call the calculate_average() function.