Data Structures Basics of Algorithms - Data Structure & Algorithms

What is Data Structure Algorithm?

A step-by-step procedure, defining set of instructions to be executed in a particular order to obtain a desired result is an Algorithm. They are usually created independent of the languages, in more than one programming languages, an algorithm can be implemented.

What are the different categories of Algorithms?

Some of the important categories of algorithms from data structure point of view are:

  • Search − Algorithm to search an item in a data structure.
  • Sort − Algorithm to sort items in a certain order.
  • Insert − Algorithm to insert item in a data structure.
  • Update − Algorithm to update an existing item in a data structure.
  • Delete − Algorithm to delete an existing item from a data structure.

What are the characteristics of an Algorithm?

An algorithm should have the following characteristics −

  • Unambiguous – Algorithm should be unambiguous. The phrases of the algorithm its steps and the inputs/outputs should be clear and lead to only one meaning.
  • Input − An algorithm should have 0 or more well-defined inputs.
  • Output – An algorithm should have 1 or more outputs which are well-defined and match with the desired output.
  • Finiteness − Algorithms must terminate after a finite number of steps.
  • Feasibility – An algorithm should be feasible with the available resources.
  • Independent − An algorithm should have step-by-step directions, which should be independent of any programming code.

How to Write an Algorithm?

There are no specific standard for writing algorithms. Algorithm completely depends on the problem and the resources. They are never written in favour of a particular programming Language.

The common code constructs like loops (do, for, while), flow-control (if-else), which are shared by all the programming languages are used to write an algorithm.

It is not mandatory that algorithms are written in a step-by-step manner. It is a process which is executed after defining the problem domain. Hence, it is essential to understand the problem domain, for which an algorithm is written.

Example

An algorithm is written by using an example.

Problem − Design an algorithm to add two numbers and display the result.

The programmers are told by the algorithm on how to code the program. Alternatively, the algorithm can be written as −

The second method is usually used to design and analyze algorithms. The analyzing is made easy to the analysts, by ignoring the unwanted definitions. The analyst can observe the operations used and the process flow.Writing step numbers, is optional.

To get a solution of the given problem, an algorithm is designed, as a problem can be solved in more than one ways.

Problem Solutions

For a given problem, many algorithm solutions can be derived. Analyze the proposed algorithm solutions and the best suitable solution needs to be implemented.

How to analyze the efficiency of an Algorithm?

Efficiency of an algorithm can be analyzed at two different stages, before implementation and after implementation. They are the following −

  • A Priori Analysis – The theoretical analysis of the algorithm is a Priori Analysis. By an assumption that all other factors like processor speed is constant and do not affect the implementation, the efficiency of an algorithm is measured.
  • A Posterior Analysis – The empirical analysis of an algorithm is a Posterior Analysis. By a programming language, the algorithm selected in implemented and executed on the target computer machine. The actual statistics like running time, space required are collected in this analysis.

Basically the analysis of the algorithm deals with the execution or running time of various operations involved. The running time of an operation can be defined as the number of computer instructions executed per operation.

Algorithm Complexity

Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm X are the two main factors, which decide the efficiency of X.

  • Time Factor – By counting the number of key operations like comparisons in the sorting algorithm, time is measured.
  • Space Factor − By counting the maximum memory space required by the algorithm, space of an algorithm is measured.

The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data.

Space Complexity

The amount of the memory space required by an algorithm in its life cycle is represented by Space complexity. The algorithm space is measured by adding the following two components -

  • A fixed part that is a space required to store certain data and variables that are independent of the size of the problem. For example, simple variables and constants used, program size, etc.
  • A variable part is a space required by variables, whose size depends on the size of the problem. For example, dynamic memory allocation, recursion stack space, etc.

Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the fixed part and S(I) is the variable part of the algorithm, which depends on instance characteristic I. A simple example that tries to explain the concept is as follows:

It is observed that there are three variables A, B and C and one constant. Hence S(P) = 1 + 3. Now, space depends on data types of given variables and constant types and it will be multiplied accordingly.

Time Complexity

The amount of time required by an algorithm to run till completion is represented by Time complexity. The time requirements are defined as a numerical function T(n), where T(n) can be measured as the number of steps, provided each step consumes constant time.

For instance, addition of two n-bit integers takes n steps. Consequently, the total computational time is T(n) = c ∗ n, where c is the time taken for the addition of two bits. Here, it is observed that as the size of the input increases, the T(n) grows linearly.


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Data Structure & Algorithms Topics