Category: Data Structure and Algorithm

# CSE 205: Radix sort and Hashing

Friends,

Here is the textbook notes for Radix sort and Hashing (sorting techniques).

Thank You

# CSE 205: Complexity of various sorting techniques

Friends,

Here is the complexity details for the various sorting techniques for CSE 205: Data Structure and Algorithm.

Click to get it

Thank you.

# Stack

The stack was first proposed in 1946, in the computer design of Alan M. Turing (who used the terms “bury” and “unbury”) as a means of calling and returning from subroutines.

A stack is a list of elements in which an element may be inserted or deleted only at one end called the TOP of the stack. It is Last In First Out (LIFO) or First In Last Out (FILO) data structure. Elements are removed in the reverse order of which they were inserted into the stack.

Examples: Stack of Dishes, Stack of Books, A packet of biscuits, etc.

AVAIL LIST (List of free memory spaces) is also implemented using Stack.

Algorithm: (Array representation)

– Inserting elements into the stack –

PUSH (STACK, TOP, MAXSTK, DATA)

1. If TOP = MAXSTK, then, write: overflow and exit.                //checking the stack is full or not
2. Set TOP = TOP+1.                                  //Increasing TOP by 1
3. Set STACK [TOP] = DATA.                   //Inserting DATA into the TOP
4. Exit.

//STACK: Name of the stack

//TOP: Pointer that points to the topmost element of the stack

//DATA: information/data to be inserted.

//MAXSTK: Maximum index of the stack (maximum size)

– Deleting elements from the stack –

POP (STACK, TOP, DATA)

1. If TOP = 0, then, write: underflow and Exit.        //checking for underflow
2. Set DATA = STACK [TOP]               //DATA is the TOP element
3. Set TOP = TOP-1                               //decreasing the size of the STACK
4. Exit

Author: Sonia Behal

In circular, the last node is linked to the header node and in grounded, the last node is linked to the NULL.

1. Set PTR = LINK [START]                                        //initializing a pointer
2. Repeat step 3 and 4, while PTR ≠ START       //PTR ≠ NULL for grounded list
3. Apply PROCESS to INFO [PTR]
4. Set PTR = LINK [PTR]                                           //PTR points to the next node

[End of while loop]

1. Exit

Insertion (INFO, NEXT, PREV, AVAIL, LOCA, LOCB, ITEM)

1. If AVAIL = NULL, then write: Overflow and Exit                             //checking for overflow
2. Set NEW = AVAIL, AVAIL = NEXT [AVAIL], INFO [NEW] = ITEM.

//removing node from AVAIL list and copy the ITEM into it

1. Set NEXT [LOCA] = NEW, NEXT [NEW] = LOCB,

PREV [LOCB] = NEW, PREV [NEW] = LOCA                                 //inserting node into the list

1. Exit.

//INFO: Data part of the node

//NEXT: Next pointer of the node

//PREV: Previous pointer of the node

//AVAIL: First node of the AVAIL list

//LOCA and LOCB: Locations in which the new node is to be inserted.

Deletion (INFO, NEXT, PREV, AVAIL, LOC)

1. Set NEXT [PREV [LOC]] = NEXT [LOC] and PREV [NEXT [LOC]] = PREV [LOC]

//deleting node

1. Set NEXT [LOC] = AVAIL and AVAIL = LOC //inserting node to the AVAIL list
2. Exit.

Author: Indrajeet Gupta

Traversing:

1. Initialize the Current pointer with the beginning of the List.
2. Move the Current pointer to point to the next node in the list and go to step-1, till the list is not over or else quit.

Searching:

1. Initialize the Current pointer with the beginning of the List.
2. Compare the KEY value with the Current node value; if they match then quit here.                                else go to step-3.
3. Move the Current pointer to point to the next node in the list and go to step-2, till the list is not over or else quit.

Insertion :

1. Get the value for NEW node to be added to the list and its position.
2. Create a NEW, empty node by calling malloc(). If malloc() returns no error then go to step-3 or else say “Memory shortage”.
3. Insert the data value inside the NEW node’s data field.
4. Add this NEW node at the desired position (pointed by the “location”) in the LIST.
5. Go to step-1 till you have more values to be added to the LIST.

At Beginning:

Insert_At_Beg (INFO, START, NEXT)

1. Create a new node and assign the address to any node say PTR.
2. Overflow, If(PTR = NULL)
1. write: Overflow and EXIT.
4. If(START = NULL)
1. Assign NEXT[PTR] = NULL
2. Else
3. Assign NEXT[PTR] = START
5. Assign START = PTR                               //inserting in the beginning
6. Exit.

## INTRODUCTION

Generally the daily life term “list” refers to the linear collection of data,whether the list may be shopping list,a daily routine, invitation list,a schedule,a meeting plan,a grocer’s list.If you want to insert any item in the list simply what you do is:delete that and insert any new item wherever n whenever you want.You can extend,add,remove,modify any item at any time with no constraints in your list.
One such way we know is we can implement list with arrays but why list lets know.

## What is need of Linked list?

Well we know how arrays work and the representation of arrays in contiguous memory locations.You have also considered the problems
associated with arrays:-

• If there is not enough memory available for allocation??
• If you have to insert the data in sorted order??
• If you want to insert the item at any location??
• If you want to create your list dynamically??
• If you want to delete any item at any location??
• If you want to insert the data of different data types??

Well the above problems are not every time associated with your programming but the Linked list is the smartest way to solve above problems.With arrays we have to make a “for loop” taking the time equal to the size of the arrays. Even if there enough memory spaces available for allocation but not in contiguous manner, your program crashes but with Link list it won’t happen.That’s why Linked list comes into picture and is of great use.

## DEFINITION

A linked list is a linear collection of data items called nodes and each node is connected to another node with the help of pointers,a node is divided into two subparts first for storing the data item and another for storing the address of the next node.The pointer stores the address and forms a link between two nodes thus this representation to store the data is called Linked list.

## Memory representation of linked list

Linked list is not stored in the contiguous memory locations.Each node contains the link of next node,so the nodes can be created in the memory irrespective of the order of the data items.

## Is linked list a linear data structure or non linear?

This is the best question asked by the interviewer whether a Linked list is a linear data structure or not because there is controversy and usually student’s get confused.
Yes, the Linked list is a linear data structure.We have seen the memory representation of linked list it is not stored in contiguous memory allocation but while accessing each item in a linked list we move in a linear way.That’s why it is called a Linear data structure.

Traversal
Accessing each element in the list is called traversal . A particular process is applied to the data whether addition,division, subtraction,or even just printing the data elements.
Insertion
Adding a data element into the list is called insertion.Insertion can be dynamic, in the middle, at end, at beginning.
Deletion
Removing a data element from the list is called deletion. Deletion can be at end,after some element, at beginning.
Searching
Finding a particular element in the list is called searching.

# Deleting element from an array

Deleting element in an array

#include<iostream>

#include<conio.h>

using namespace std;

main()

{

int n;                                      //initialising the size of an array

cout<<“Enter the size of the array: “;

cin>>n;                                 //Taking the size from the user

int arr[n],i=1,loc;

cout<<“Enter the elements of the array: “;

while(i<=n)                         //While loop

{

cin>>arr[i];                               //Taking the elements form the user

i++;                                              //Increment the iteration variable

}

cout<<“Enter the location to be deleted: “;

cin>>loc;                            //Taking the value of location from the user

i=loc;                                   //Initialise the iteration variable

while(i<=n)                      //while loop

{

arr[i]=arr[i+1];                        //shifting the elements upward

i++;

}

i=1;

while(i<n)

{

cout<<arr[i]<<“\t”;               //Displaying the elements

i++;

}

getch();

}

* Algorithm of the above program:

Delete (ARR, LOC, N)

1. Set I=LOC                                            //Initialise counter/iteration variable
2. Repeat steps 3 and 4 while I<=N
3. Set ARR[I] = ARR[I+1]                    //shifting the elements upwards
4. Set I = I+1;                                          //Increment the counter

[End of loop]

1. Set N=N-1;                                      //Reset the size of the array
2. Exit

* Complexity = O(n)

Note:

1. For deleting element from an array, the elements are needed to be shifted upwards starting from the location that we want to delete. Then the size of the array should be reduced.

# Inserting element into an Array

Inserting elements into an array
#include<iostream>
#include<conio.h>
using namespace std;
main()
{
int n;                                          //intitialising the size of the array
cout<<“Enter the size of the array: “;
cin>>n;                                   //taking the size from the user
int arr[n],i,loc,item;        //initialising array, iteration variable, location, item
cout<<“Enter the elements of the array: “;
for(i=1;i<=n;i++)
{
cin>>arr[i];                        //taking the elements of the array from user
}
cout<<“Enter the location to be inserted: “;
cin>>loc;                          //taking the location from the user
cout<<“Enter the item to be inserted: “;
cin>>item;                      //taking the item from the user
for(i=n;i>=loc;i- – )
{
arr[i+1]=arr[i];            //shifting operation
}
arr[loc]=item;            //inserting the item in that location
for(i=1;i<=n+1;i++)
{
cout<<arr[i]<<“\t”;    //displaying the elements
}
getch();
}
* Algorithm of the above program:
Insert (ARR,LOC,ITEM,N)
1. Repeat for  I=N to LOC
2.    Set ARR[I+1] = ARR[I]    //Shift the elements downwards
[End of loop]
3. Set ARR[LOC] = ITEM.        //insert the item in that location
4. N = N+1                                   //Reset size of the array
5. Exit
* Complexity: O(n)
Note:
1. For inserting an element in an array, we have to shift the last element to the next location till the location of the new item to be inserted reach. Then we can insert the new element to the location.

Author: Udipto Goswami

# Traversing in a Linear Array

Traversing in a Linear Array

Line 1:   #include<iostream>

Line 2:   #include<conio.h>

Line 3:   using namespace std;

Line 4:   main()

{

Line 5:        int arr[5]={1,2,3,4,5};    // initialising the elements in an array

Line 6:        int i;                                   // initialising an iteration variable

Line 7:        for(i=0;i<5;i++)             // a loop that goes to repeat the process till the end of the array

{

Line 8:              cout<<arr[i];        // printing the elements on the screen

}

Line 9:        getch();

}

Algorithm for the above program

[Note: LB = Lower Bound: starting value for the iteration,

UB = Upper Bound: ending value for the iteration,

A = name of the array]

Traverse (LB, UB, A)                 // Name of the algorithm and the variable that used in the algorithm

1. Repeat for K = LB to UB       // This statement is similar to line 7

Apply PROCESS to A[K]  // This statement is similar to line 8

[End of Loop]

1. Exit                                  // we have to write exit at last as this shows the algorithm have finished.

Complexity: O(n)

PROBLEM 1: Find the number of elements in an array which are greater than 25.

SOLUTION:         Traverse (A, LB, UB, count)

1. Set count = 0, K = LB        //Setting the value of count and iteration variable
2. While K<=UB                       //Repeating the operation till it reached UB
3. if A[K] > 25, then:              //Checking condition for the elements >25
4. count = count+1.              //counting the elements >25
5. Set K = K+1                        //Incrementing the iteration variable

[End of while loop]

1. Exit

Complexity: O(n)

PROBLEM 2: Find out the sum of all the two digit numbers in an array.

SOLUTION:         Traverse (A, N, sum)

1. Set sum=0                                                 //Setting the value of sum
2. Repeat K = 0 to N                                   //Repeating the operation
3. if A[K]>=10 and A[K]<=99, then:      //Checking for two digit number
4. sum = sum+A[K]                                    //Taking sum of all the two digit numbers

[End of for loop]

1. Exit

Complexity: O(n)

NOTE:

1. We can give any name of the algorithm of our wish.
2. We can use any loop of our own wish; whether for loop of while loop.
3. Loop can go from LB to UB or 0 to N. There is no difference between these two statements. And N denotes the size of the array.
4. We have to write all the major variables that used in the algorithm inside the parenthesis just besides the name of the algorithm

# Complexity

Complexity:

The term complexity is defined as the time or space requirement of an algorithm to be executed completely in terms of the input size.

TIME and SPACE are two major requirements of efficiency of an algorithm.

TIME: Measured by counting the number of key operations.

SPACE: Measured by counting the maximum of memory needed by the algorithm.

By increasing the amount of space for storing the data, one may be able to reduce the time needed for processing the data, or vice versa.

Cases of Complexity:

1. Worst Case: The maximum value of a function (consider algorithm) for any possible input.
2. Average Case: The expected or average value of a function.
3. Best Case: Minimum possible value of a function.

Standard Functions of Complexity:

1. log2n
2. n
3. nlogn
4. n2
5. n3
6. 2n

(Arranged in increasing order)

Asymptotic Notations:

These are languages that allow us to analyse an algorithm’s running time by identifying its behaviour as the input size for the algorithm increases. This is also known as an algorithm’s growth rate.

BIG-OH (O) Notation:

Big-oh defines the upper bound of a particular function (here specifically algorithm).

FORMULA: f(n)=O(g(n)) if f(n)<=C g(n) for n>=n0 ; C and n0 are constants.

ALSO CALLED THE WORST CASE OF AN ALGORITHM

Big-Omega (Ω) Notation:

Big-omega defines the lower bound of a particular function (here specifically algorithm).

FORMULA: f(n)= (g(n)) if f(n)>=C g(n) for n>=n0 ; C and n0 are constants.

ALSO CALLED THE BEST CASE OF AN ALGORITHM

Big-Theta (Ө) Notation:

Big-theta defines the tight bound of a particular function (here specifically algorithm).

FORMULA: f(n)= Ө (g(n)) if C1(n) <= f(n) <= C2 g(n) for n >= n0; C1, C2 and n0 are constants.

f(n) = Ө (g(n)), iff f(n) = O(g(n)) and f(n) = Ω (g(n))

ALSO CALLED THE AVERAGE CASE OF AN ALGORITHM

Little-Oh (o) Notation:

Big-theta defines the non-tight analogue of Big-oh.

FORMULA: f(n) = o (g(n)), if for every c, there exists n0 such that, f(n) <= c g(n) for n >= n0

Used for comparisons of running times.

PROBLEM FOR FINDING COMPLEXITY:

Problem1:

function ()

{

if (condition)

{

for (i=0; i<n; i++)

{ // simple statements}

}

else

{

for (j=1; j<n; j++)

for (k=n; k>0; k–)

{// simple statement}

}

}

Complexity:

1. Check the for If for statement is increasing serially i.e i=0,1,2,3… then write n for that loop.
2. Check again the other for. It is also increasing serially so n.
3. The third loop is also making n, but it is inside the second loop so it will contribute n2.

THEREFORE COMPLEXITY:

n+n2 (considering only the highest power of n).