Course Content
L1: Algorithm Decomposition and Abstraction
In this topic we will focus on the definition of: - Algorithm - Decomposition - Abstraction You will also decompose and develop abstraction from given problems.
0/2
L2: Developing Algorithms using Pseudocode
0/1
L3: Developing Algorithm using flowcharts
0/1
L4: Linear and Binary Search
0/1
L5: Bubble Sort
0/1
L6: Merge Sort
0/1
L7: Assessment
0/1
8525 Unit 1: Fundamentals of Algorithm – COMING SOON
About Lesson

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.

4bf129d0 6784 482a acb8 816ae167454d 4 5005 c

The following algorithm will solve the problem:

  1. Move A to Tower 3
  2. Move B to Tower 2
  3. Move A to Tower 2
  4. Move C to Tower 3
  5. Move A to Tower 1
  6. Move B to Tower 3
  7. 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.

A8260c15 24b6 4750 96c1 a02920b82b72

Here we have broken down the big problem (moving 3 disks from tower 1) into three smaller problems:

  1. Move 2 disks from tower 1 to tower 2
  2. Move 1 disk from tower 1 to tower 3
  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. 

F5838b21 69f6 4f4f a0d0 9eb9592c04ee

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.

95169886 dc28 40b2 bfac c98d19a0ab69 4 5005 c

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.

2b6524a8 ba0b 462f 97ad 8b54ecf8dde2

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:

  1. the sum() and len() functions are examples of abstraction. We use them to perform complex operations without needing to understand all the details of how they work.
  2. 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.
Exercise Files
1_1 Worksheet 1.pdf
Size: 153.07 KB
0% Complete
Scroll to Top