Data Structures and Algorithms: A Comprehensive Analysis

Desklib provides solved assignments and past papers to help students succeed.

DATA STRUCTURES AND ALGORITHMS

Table of Contents
DATA STRUCTURES AND ALGORITHMS...............................................................................1
List of Figure...................................................................................................................................2
List of Table.....................................................................................................................................3
Introduction......................................................................................................................................4
LO1..................................................................................................................................................5
P1.....................................................................................................................................................5
P2.................................................................................................................................................7
M1..................................................................................................................................................12
M2..............................................................................................................................................13
LO2................................................................................................................................................15
P3...............................................................................................................................................15
M3..............................................................................................................................................17
LO3................................................................................................................................................18
P4...............................................................................................................................................18
P5...............................................................................................................................................20
M4..............................................................................................................................................21
LO4................................................................................................................................................23
P6...............................................................................................................................................23
P7...............................................................................................................................................25
M5..............................................................................................................................................26
Conclusion.....................................................................................................................................28
References......................................................................................................................................29
List of Figure
Figure 1: Classification of Data Structure.......................................................................................6
Figure 2: Stack Implementation.......................................................................................................8
Figure 3: Process of Queue............................................................................................................13
Figure 4: Outcome.........................................................................................................................13
Figure 5: ADT Stack Process........................................................................................................15
Figure 6: Process as Advantage.....................................................................................................17
Figure 7: Source Code...................................................................................................................19
Figure 8: Output of Program..........................................................................................................20
Figure 9: O Notation......................................................................................................................24

Figure 10: Ω Notation....................................................................................................................24
Figure 11: θ Notation.....................................................................................................................25
Figure 12: Source Code.................................................................................................................26
Figure 13: Outcome.......................................................................................................................26
List of Table
Table 1: Queue Operation Methodologies.....................................................................................12
Table 2: Difference between quick and merge sort.......................................................................14
Table 3: Stack ADT Example........................................................................................................16
Table 4: Queue Algorithm Terminologies.....................................................................................18

Introduction
This task is having the analysis of data structure and algorithm with some real life
implementation also. In LO 1, it is having different classification of data structure with the
explanation and their use or application area also. After that, we have to understand the basic of
stack & queue functionality with analysis of complexity and algorithm by explaining the
functions respectively. After that we have compared quick sort & mere sort. In LO 2, we have to
understand the ADT (Abstract Data Type) with the algorithm notations. In LO 3, we have to
practically implement the data structure & algorithm. At last, we have to discuss about the
asymptotic analysis with two efficiency measurement algorithm & ADT tradeoff.

LO1
P1
Data Structure
Data structure is defined as the program used for managing the data or information. This will
completed in such a manner for managing the data or information which are easily available to
the processor & their calculation also.
Classification of Data Structure with Operation also
Here, below is the list of different available data structure with their functionality also and these
are as follows:
 Arrays
 Linked List
 Graph
 Tree
 Queue
 Heap
 Stack
 Hash Table

Figure 1: Classification of Data Structure
Arrays
It is implemented directly in programming language like C & C++ and implementation is done
via statically. The size of the data structure is measured at the time of running stage of program,
however in latest programing language like JAVA, we can perform & manage array with
property like size on the compile or run time also.
Linked List
It is same as array, however having one additional feature which is memory management. The
main reason behind is that the memory allocation is completed at the run time. Hence, there is no
wastage of memory.
Stack
Stack is data structure which is followed by the last in first out LIFO order. In this, element is
stored at the last and removed first. The main application of the task is that solving the recursion,
depth first search and binary conversion.
Queue

Queue is data structure which is followed by the first in first out FIFO order. In this, element is
stored at the first and removed first. The major application area is multi programming as well as
message queue with sharing of resources.
Graph
Graph is defined as the network structure which are used for connecting the nodes named as the
vertices and using connection known as edges. An edge is defined as the path or communication
link which is established in between two nodes (Kumar, 2019).
P2
Stack is defined as the linear data structure used for managing the operation easily in such a
manner LIFO & FIFO (Last in First Out) & (First in First Out) respectively. Here, below is the
operation list which are used in stack and these are as follows:
 Push
 POP
 Peek or Top
 Is Empty
Push
This function is used for adding any item into stack. If there is situation when stack is full then it
is called as overflow situation.
POP
This function is used for the removing or deleting the item from the stack list. The item are
popped in proper manner followed by reverse order. If the stack is empty, then this situation is
known as underflow situation.
Peek or Top
This function is used for returning the top most element of the stack.
Is Empty

It is used for checking the stack is empty or not. If it is empty then it is returning the true or
otherwise false.
Figure 2: Stack Implementation
Implementation
There are mainly two methods through which we can implement a stack for using & calling the
computer functionality and these are as follows:
 Array
 Linked List (SQA, 2019)
Code of Stack Implementation using C# using Array Methodology
using System;
namespace ImplementStack
{
class Stack
{
private int[] ele;
private int top;
private int max;
public Stack(int size)
{
ele = new int [size];//Maximum size of Stack
top = -1;

max = size;
}
public void push (int item)
{
if (top == max-1)
{
Console.WriteLine ("Stack Overflow");
return;
}
else
{
ele[++top] = item;
}
}
public int pop()
{
if(top == -1)
{
Console.WriteLine ("Stack is Empty");
return -1;
}
else
{
Console.WriteLine ("{0} popped from stack ",ele[top]);
return ele[top--];
}
}
public void printStack()
{
if (top == -1)
{

Console.WriteLine ("Stack is Empty");
return;
}
else
{
for (int i = 0; i <= top; i++)
{
Console.WriteLine ("{0} pushed into stack", ele[i]);
}
}
}
}
// Driver program to test above functions
class Program
{
static void Main()
{
Stack p = new Stack(5);
p.push (10);
p.push (20);
p.push (30);
p.printStack ();
p.pop ();
}
}
}
Code of Stack Implementation using C# & Linked List Methodology
public void push(int data) {
StackNode newNode = new StackNode(data);

if (root == null) {
root = newNode;
} else {
StackNode temp = root;
root = newNode;
newNode.next = temp;
}
Console.WriteLine (data , " pushed to stack");
}
public int pop() {
int popped = Integer.MIN_VALUE;
if (root == null) {
Console.WriteLine ("Stack is Empty");
} else {
popped = root.data;
root = root.next;
}
return popped;
}
public int peek() {

if (root == null) {
Console.WriteLine ("Stack is empty");
return Integer.MIN_VALUE;
} else {
return root.data;
}
}
M1
Queue is data structure which is followed by the first in first out FIFO order. In this, element is
stored at the first and removed first. The major application area is multi programming as well as
message queue with sharing of resources. Here, in below table it is having the functionality of
different function used for queue operation and these are as follows:
Table 1: Queue Operation Methodologies
S.N. Function Name Description
1. Enqueue () Used for inserting an element into the list
2. Dequeue () Used for deleting an element from the list
3. head () Top of list element
4. size () Used for finding the size of list
5. Is Empty() Used for checking the queue is empty or not. If it is empty
then it is returning the true or otherwise false.
6. Is Full() Used for checking the queue is full or not. If it is full then
it is returning the true or otherwise false.