Data Structure: Lecture 2

MARWARI COLLEGE, RANCHI

(AN AUTONOMOUS UNIT OF RANCHI UNIVERSITY FROM 2009)

- Prakash Kumar, Dept. of CA

-Archana Kumari, Dept. of CA
Raju Manjhi, Dept. of CA 

__________________________________________________________________________________ 

Algorithm

An algorithm is a set of rules that must be followed when solving a specific problem.

Informally, we can also define an algorithm as well-defined computational procedure which takes some value or set of values as input and generates some value or set of value as output.

Thus it can also be defined as “a finite sequences of computational steps that transforms the given input into the output for a given problem”.

Note:

An algorithm is considered to be correct, if for every input instance, it generates the correct output and gets terminated.

Characteristics of an Algorithm

An algorithm should have the following characteristics: −

·         Definiteness: Algorithm should be clear and unambiguous.

·         Input: It should have 0 or more well-defined inputs.

·         Output: It should have 1 or more well-defined outputs, and should match the desired output.

·         Finiteness: It must terminate after a finite number of steps.

·         Effectiveness: Every instruction must be a very basic so that it can be carried out, in principle, by a person using pencil and paper.

Analysis of algorithm: 

The term "analysis of algorithms" was coined by Donald Knuth.

The analysis of algorithm focuses on:-

1. Time complexity

2. Space complexity.

1. Space complexity: The amount of memory needed by program to run to completion is referred to as space complexity.

2. Time complexity: For an algorithm time complexity depends upon the size of the input, thus, it is a function of input size “n”. The amount of time needed by an algorithm to run to completion is referred as time complexity.

          The minimum amount that an algorithm requires for an input of size “n”, is referred to as best case time complexity, similarly average case time complexity is the execution of an algorithm having typical input data of size “n”. And lastly the maximum amount of time needed by an algorithm for an input size ,”n”, is referred to as worst case time complexity.

Asymptotic Notations:

Asymptotic Notations are certain notations which describe the algorithm efficiency and performance in a meaningful way.

Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.

·         O: Big Oh

·         Ω: Big omega

·         Ɵ: Big theta

·         o: Little Oh

·         ω: Little omega

Big oh Notation (Ο)/( Asymptotic Upper Bound)

The upper bound for the function ‘f’ is provided by the big oh notation (O).

In general,

Big omega Notation (Ω)/ (Asymptotic Lower Bound)

The lower bound for the function ‘f’ is provided by the big omega notation (Ω).

In general,

Big theta Notation (Ɵ)/ (Asymptotic Tight Bound)

The lower and upper bound for the function ‘f’ is provided by the big theta notation (Ɵ).

Little Oh Notation (o)

The asymptotic upper bound provided by O-notation may or may not be asymptotically tight. Intuitively, in the o-notation, the function f(n) becomes insignificant relative to g(n) as n approaches infinity; that is,

Little omega Notation (ω)

We use ω-notation to denote a lower bound that is not asymptotically tight.

In ω-notation f(n) becomes arbitrarily large relative to f(n) as n approaches infinity.

Arrays: C implementation

Array

Array is a container which can hold a fix number of items and these items should be of the same type. Most of the data structures make use of arrays to implement their algorithms.

Following are the important terms to understand the concept of Array.

·         Element − each item stored in an array is called an element.

·        Index − each location of an element in an array has a numerical index, which is used to identify the element.

Array Representation

Arrays can be declared in various ways in different languages. For illustration, let's take C array declaration.

int array[5];

Basic Operations

Following are the basic operations supported by an array.

·         Traverse − Prints all the array elements one by one.

·         Insertion − Adds an element at the given index.

·         Deletion − Deletes an element at the given index.

·         Search − Searches an element using the given index or by the value.

·         Update − Updates an element at the given index.

Insert Operation in array

Insert operation is to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array.

Algorithm

Let Array be a linear unordered array of N=size elements.

Algorithm for insertion of an element in an array:-

Step 1:   Input the element into an array a[size].

Step 2:   Input the location number loc

Step 3:   input the value

Step 4:   newsize=size+1

Step 5:   while newsize>loc

              a[newsize] = a[newsize-1]

                   newsize--

Step 6:   a[newsize] = value

Step 7:     size=size+1

Algorithm for deletion of element in array:-

Step 1:   Input the element into an array a[size].

Step 2:   Input the location number loc

Step 3:   while  loc < size

              x[loc] = x[loc + 1]

              loc = loc + 1

Step 4:   size--

Implementation of above algorithm in C