Algorithms

What is an algorithm?

An algorithm is a way of solving well specified computational problems. – Cormen et al.

A finite set of rules that give a sequence of operations for solving a specific type of problem. – Donald Knuth

I describe an algorithm as an exact sequence of well-defined instructions that solves a computational problem.

When giving instructions to a computer, every step must be defined in a specific sequence so that the computer can complete the software task. Every code instruction written is part of an algorithm. While different sets of instructions may solve the same problem and complete the same task, some sets of instructions may be more efficient than others.

Why do programmers need to understand algorithms?

• It helps us understand at a high-level how long it will take to solve a problem.
• Having a time estimate will help us understand how to break the problem into smaller pieces.
• Assists us in understanding what the hardware and resource requirements for solving the problem may be.
• Assists us in understanding whether a problem is feasible and can be solved versus impossible to solve.

Why do programmers need to understand data structures?

1. How to store data in a way that enables efficient storage and retrieval of data.
2. How to sort and categorize data to enable efficient operations and analysis on the data.

Euclid’s Algorithm

Find the greatest common divisor (GCD) of 2 positive numbers, ‘m’ and ‘n where m > n.

1. Divide m by n and let the remainder be r.
2. If r = 0, the algorithm ends and n is the GCD.
3. if r ≠ 0, then set m -> n, n -> r and repeat step 1 until r = 0.

public class EuclidAlgorithm {
	
  public static void main (String[] args) {
		
    int m = 297;
    int n = 50;
    int r;

    System.out.println("Finding the GCD of " + m + " and " + n);

    while (n != 0) {
      r = m % n;
      m = n;
      n = r;
    }
		
    System.out.println("The GCD is :" + m);
  }	
}

Big O Notation

The big O notation is used to analyze an algorithm in terms of its space and time complexity and allows us to compare algorithms independently of input size to analyse it’s efficiency.

Space complexity : How much of space is used to store data in memory during algorithm runtime.

Over time, RAM has become cheaper to obtain making the space complexity insignificant in most scenarios.

Time complexity : How long does the algorithm take to execute.

The same algorithm may execute in varying times on different types of hardware. Running the same algorithm on the same types of hardware with exactly the same resource configurations located in different regions but exposed to temperatures would also produce different execution times. It’s important to consider the external factors that may contribute to varying execution times.

To make an algorithm more efficient, you often have to make assumptions about the data such as the data may be sorted in a specific way or the data is of a specific data type. The assumptions you make about the data must be true to be able to generate accurate output from the algorithm.