✍️Writing Algorithms

Learn how to write and interpret algorithms using pseudocode.

An algorithm is a set of instructions to solve a problem. Real world examples include:

1. Recipe for baking a cake

2. Instructions for sorting a deck of cards

3. Steps to find the shortest route on a map

In terms of computers, algorithms are step-by-step procedures for solving a problem digitally, some examples include:

1. Binary search algorithm

2. Bubble sort algorithm

3. Dijkstra's algorithm for shortest path

4. RSA encryption algorithm

5. Quick sort algorithm

Here are a few problems that have been solved by algorithms:

• Routing Problems: Routing packets of data around the internet by the shortest route. Finding the shortest route for a salesman to cover his territory.

• Timetabling Problems: Commercial aircraft crews so that they do not exceed their permitted flight hours.

• Searching Problems: Finding information on the internet or from a database.

• Encrypting Problems: Encrypting data so that it cannot be read by others.

• Sorting Problems: Sorting large amount of data in a specific format.

• Compiling Problems: Translating high level language code into machine code.

Good Algorithms

A good algorithm must have clear and precisely stated steps that produce the correct output; It should allow for valid inputs; it must terminate at some point; it should execute efficiently, in as few steps as possible; It should be designed in such way so the algorithm is easy for others to understand and edit.

Designing an Algorithm

You can use hierarchy charts, flowcharts, or pseudocode in order to design an algorithm.

Hierarchy Charts

Hierarchy charts are very useful for identifying major tasks and breaking them down into small subtasks.

An example of a hierarchy chart

Flowcharts

Flowcharts are useful for getting down initial ideas for individual subroutines.

An example of a flowchart

Pseudocode

Pseudocode can help us understand what the actual code of the subroutines may look like, so it can easily be later translated into source code by a programmer.

Sorting Algorithms

Sorting is a common operation whilst processing data. There are many sorting algorithms, some that are very simple and slow (e.g. insertion sort), while others that are more complex and fast (e.g. merge sort).

On a given computer, a fast algorithm may sort 10M numbers in 15 minutes, whereas an inefficient algorithm may take months to do the same thing. This highlights the importance of a good algorithm.

Insertion Sort

Insertion sort is an efficient algorithm for sorting a small number of elements. It works in the same way you may sort a deck of playing cards: Start with all the cards facing down, pickup each card in turn and insert it into the correct place in the deck.

How it works

• Suppose we have six numbers to sort.

• The pink card is the card you pick up each time.

• Insert it in the right place, and pick up another.

Python Example

arr = [12, 11, 13, 5, 6]
for i in range(1, len(arr)):
    key = arr[i]
    j = i - 1
    while j >= 0 and key < arr[j]:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key
print("Sorted array via insertion sort:", arr)

Bubble Sort

This sorting algorithm is useful when there are small number of items to be sorted. To sort an array of n items, n-1 passes are made through the array, with each item being compared to the adjacent item and swapped if necessary.

arr = [64, 34, 25, 12, 22, 11, 90]
n = len(arr)
for i in range(n):
    for j in range(0, n-i-1):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]
print("Sorted array via bubble sort:", arr)

Searching Algorithms

There are two most common searching algorithms: linear search and binary search.

Linear search starts from the beginning of the list and examines every item. On the other side, binary search uses the “divide and conquer” tactic to halve the search area each time an item is examined, this makes it much faster than linear search. A disadvantage of binary search is that it can only be used on pre-sorted data.

Python Example

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
# Example usage:
my_list = [2, 4, 7, 10, 14, 19, 22, 25]
target = 14
result = binary_search(my_list, target)

Video for understanding binary search