An Algorithm is a step by step procedure, which defines a set of instructions to be executed in a certain order to get desired output.

There are four important factors an Algorithm must consider:

  1. Completeness: Is a solution guaranteed to be found if one exists?
  2. Optimality: Is the solution guaranteed to be the best/lowest cost solution if more than one solution may exist?
  3. Time Complexity: The upper bound on the time required to solve the problem, as a function of the complexity of the problem.
  4. Space complexity: The upper bound on the amount of storage space (memory) required at any point while running the algorithm.
    Travelling salesman problem

    Comic courtesy of XKCD, via Creative Commons License

Algorithm Analysis Edit

A problem can be solved in more than one way. So, many solution algorithms can be presented for the same problem. We analyse the available algorithms to find and implement the best suitable algorithm.

A correct and optimal algorithm can be analysed in two ways: time and space, as a measure of execution time and extra space required by the algorithm.

Asymptotic analysis of an algorithm refers to defining the mathematical bounds/framing of its runtime performance. Using asymptotic analysis, we can provide three levels of mathematical binding of execution time of the algorithm:

  • Best case is represented by Ω(n) notation.
  • Worst case is represented by Ο(n) notation.
  • Average case is represented by Θ(n) notation.

Basic Approaches Edit

There are three commonly used approaches to develop algorithms:

  1. Greedy Approach: Finding a solution by choosing the next best option.
    • Travelling Salesman Problem
    • Prim's MST Algorithm
    • Kruskal's MST Algorithm
    • Dijkstra's MST Algorithm
    • Graph - Map Colouring
    • Graph - Vertex Cover
    • Fractional Knapsack Problem
    • Job Scheduling Problem
  2. Divide and Conquer: Dividing a problem into distinct sub-problems and solving them separately.
  3. Dynamic Programming: Dividing a problem into overlapping sub-problems and solving each of these subproblems just once, storing their solutions.
    • Fibonacci Number Series
    • 0/1 Knapsack Problem
    • Tower of Hanoi
    • All Pair Shortest Path by Floyd-Warshall
    • Shortest Path by Dijkstra's Algorithm
    • Project Scheduling