Computer Program vs. Algorithms

• An algorithm is a self-contained, step-by-step set of operations
  • they are performed to solve a specific problem or a class of problems
• A computer program is a sequence of instructions
  • they comply to the rules of a specific programming language
  • they are written to perform a specific task with a computer
  • may contain multiple algorithms

Defining an Algorithm

• Algorithms consist of:
  • a problem: defined to be a real-world problem
  • an algorithm: a defined step-by-step process designed for the problem
  • inputs: algorithm is provided necessary and desired inputs
  • a processing unit: inputs are processed to produce a desired output
  • output: the outcome of the algorithm

Example of an Algorithm

• Sorting cards by their respective colour

  1. Pick up all the cards
  2. Pick a card from your hand and look at the colour
  3. If there is a pile of cards with that colour already, add it to that pile
  4. If there is not a pile of cards with that colour, make a new pile for this colour
  5. If there is a card still in your hand, go back to the second step
  6. If there are no cards in your hand, then the cards are sorted, and you are done

• The above example is readable by a human

• For a machine to understand it would require functions and nested if statements and control statements

Pseudocode

• Pseudocode is a language used to describe algorithms
• Written in a high-level method so anyone can read it and understand it
• Language similar to programming code will be used
  • therefore, it feels natural whilst developers read it

Pseudocode for Card Sorting

SORT_CARDS(CARDS)
  DATABASE COLORS = EMPTY
  FOR i <- 0 to length(CARDS)
    IF CARDS[i] == COLORS[i]
      COLORS[i] <- COLORS[i] + 1
    ELSE
      COLORS[i] = 1 

Flow Diagram of Card Sorting

• Flow diagrams are great for visualising the steps of an algorithm
• Easy to visualise what is happening at each step

Characteristics of an Algorithm

• An algorithm will consist of the following characteristics:
  • some sort of input
  • a collection of results, known as an output
  • instructions should be unambiguous and easy to understand
  • the algorithm should be finite and conclude to something
  • it should be effective
  • the algorithm should language agnostic

Writing an Algorithm

• When writing an algorithm, keep these ideologies in mind:
  • an algorithm is a step-by-step process
  • try and go-back to a step if a loop or condition fails
  • jump between statements if certain conditions are met
  • use the break keyword to stop and terminate the process when the condition is met

Growth Rate of Complexity

Examples of Big-O Notation (1)

O(1)

• Will always execute in the same time (or space)

def equal_to_one(_list):
    if _list[0] == 1:
        return True

O(n)

• Performance will grow linearly and in direct proportion of input data

def contains_number(_list, _number):
    for x in _list:
        if x == _number:
            return True
        else:
            return False

Examples of Big-O Notation (2)

O(n²)

• Performance is directly proportional to the squared size of the input data
• Most common with algorithms that have nested iterations
  • deeper nested iterations will result in O(N³), O(N⁴) etc.

def contains_duplicates(_list):
    for i in range(len(_list)):
        for j in range (len(_list)):
            if i == j:
                continue
            if list[i] == list[j]:
                return True
    return False

Examples of Big-O Notation (3)

O(2ⁿ)

• Denotes an algorithm where the growth doubles with each addition to the input
  • growth curve is considered to be exponential

def fibonacci(number):
    if number <= 1: return number
    return fibonacci(number - 2) + fibonacci(number - 1)

Calculating the Big-O Value of an Algorithm (1)

1. Break the algorithm into individual operations
2. Calculation the Big-O of each operation
3. Add up the Big-O of each operation together
4. Remove the constants
5. Find the highest-order term
   • this will be what we consider to be the Big-O of the algorithm

Calculating the Big-O Value of an Algorithm (2)

Instructions

1. Break the algorithm into individual operations
2. Calculation the Big-O of each operation
3. Add up the Big-O of each operation together
4. Remove the constants
5. Find the highest-order term
   • this will be what we consider to be the Big-O of the algorithm

def add(x, y):
    total = x + y
    return total