K-48 International College: Data Structures and Algorithms Report

This report provides an in-depth analysis of data structures and algorithms, focusing on the Stack and Queue data structures and the Insertion Sort algorithm. The report begins by identifying the Stack as the most suitable data structure for a given scenario, due to its Last-In-First-Out (LIFO) behavior, and contrasts it with the Queue data structure. The report then delves into a comparison of various sorting algorithms, ultimately justifying the selection of Insertion Sort. The report also includes source code snippets and outputs to illustrate the concepts. Furthermore, it briefly explains recursive algorithms, highlighting their advantages and disadvantages. The report concludes with an overview of the Java code implementation for the Stack data structure and Insertion Sort.

Data Structure and Algorithm Individual Assignment
Data Structure &
Algorithm
PREPARED BY –
Umar Mahmood
KD/HNDCSE/48/07

Data Structure and Algorithm Individual Assignment
INTERNATIONAL COLLEGE OF BUSINESS & TECHNOLOGY LTD
ASSIGNMENT BRIEF
Assignment Cover Sheet
Qualification Module Number and Title
HD in Computing and Software Engineering Data Structures and Algorithms
SED52013
Student Name & No. Assessor
M.H Umar Mahmood (KD/HNDCSE/48/07)
Hand out date Submission Date
24.11.2020
Assessment type
Coursework
Duration/Length of
Assessment Type
Weighting of Assessment
100%
Learner declaration
I, ………………………………………….<name of the student and registration
number>, certify that the work submitted for this assignment is my own and
research sources are fully acknowledged.
Marks Awarded
First assessor
IV marks
Agreed grade
Signature of the assessor Date
FEEDBACK FORM
INTERNATIONAL COLLEGE OF BUSINESS & TECHNOLOGY
Module:Data Structures and Algorithms - SED52013
Student:M. H Umar Mahmood (KD/HNDCSE/48/07)

Data Structure and Algorithm Individual Assignment
Assessor:
Assignment:
Strong features of your work:
Areas for improvement:
Marks Awarded:

I
Data Structure and Algorithm Individual Assignment
Executive Summary
This report discusses about the basic data structures suitable for the given scenario;
Stack and Queue, and provides a comparison among the 2. Of the 2, the most suitable
data structure was chosen after proper discussion and analysis; Stack. Relevant source
codes are attached as screenshot and in the sub-folder attached with this report.
On the second part of the report is a discussion about the Sorting Algorithms and
analysis to implement for the given scenario. Upon proper analysis Insertion Sort was
chosen. Relevant source codes are attached as screenshot and in the sub-folder
attached with this report.
The third part of the report provides a brief information about the Recursive algorithm
and its advantages and disadvantages with its source code, and factorial numbers as its
example.

II
Data Structure and Algorithm Individual Assignment
Acknowledgement
This module; Data structures and Algorithm is a golden opportunity for learning about
Data structure and Sorting Algorithms and how they contribute towards the
programming environment. It is indeed a matter of great pleasure and proud privilege
to present this project report. I own great thanks to many people who helped and
supported me in completing this project. I would like to express my deepest
appreciation to my family members and my friends especially who provided the
possibility to complete this report.
I would like to express a deep sense of gratitude to our Lecturer Mr. Prabu
Premakumar who was kind enough and always available to help and guided me and
my batch mates to do such a complex yet wonderful and interesting project and made
sure that we understood what we were taught, and a special gratitude to my course
coordinator Mrs. Shyamila Karunarathna for this module.

III
Data Structure and Algorithm Individual Assignment
Table of Contents
Executive Summary........................................................................................................I
Acknowledgement..........................................................................................................II
Table of Contents..........................................................................................................III
Table of Figures.............................................................................................................V
Table of Tables...............................................................................................................V
Task 1. A).......................................................................................................................1
Identification of suitable Data Structures...............................................................1
Identification of Data Structure for given Scenario................................................6
Task 1. B).......................................................................................................................7
Task 2. A).......................................................................................................................9
Sorting Algorithms..................................................................................................9
Identification of Pros and Cons among Sorting Algorithms.................................11
Justification...........................................................................................................13
Task 2. B).....................................................................................................................13
Task 3. A).....................................................................................................................15
Recursion..............................................................................................................15
Identification of Advantages and Disadvantages of Recursion Algorithms.........15
Task 3. B).....................................................................................................................16
References....................................................................................................................17
Appendix A..................................................................................................................18
Gantt Chart............................................................................................................18

IV
Data Structure and Algorithm Individual Assignment
Table of Figures
Figure 1 : Stack Example........................................................................................3
Figure 2 : Queue Example......................................................................................5
Figure 3 : Stack Class - Java...................................................................................7
Figure 4 : Stack Main Class - Java..........................................................................7
Figure 5 : Stack DS Output.....................................................................................8
Figure 6 : Insertion Sort Function.........................................................................13
Figure 7 : Display and Main method....................................................................14
Figure 8 : Insertion sort Output.............................................................................14
Figure 9 : Recursion Algorithm............................................................................16
Figure 10 : Recursive Algorithm output...............................................................16
Figure 11 : DSA Gantt Chart................................................................................18
Table of Tables
Table 1 : Pros and Cons of Stack Data Structure....................................................8
Table 2 : Pros and Cons of Queue Data Structure...............................................11
Table 3 : Big O Time Complexity Chart...............................................................18
Table 4 : Pros and Cons of Sorting Algos.............................................................19
Table 5 : Pros and Cons of Recursive Algorithm.................................................22

1
Data Structure and Algorithm Individual Assignment
Task 1. A)
“POP” is a famous game among school boys. Player one will put the ball one by one
and each ball will locate on top of each other. Very first ball is located in the bottom
of the tube and last ball is located in the top.”
Identification of suitable Data Structures
The suitable Data Structures for above scenario are:
1. Stack, and
2. Queue
1. Stack
 An Abstract Data Type (ADT) that is commonly used in most programming
languages. It is named stack because it behaves like a real-world stack, for
example – a deck of cards or a pile of plates, or a bunch of tennis balls in a tube
 It is an ordered list in which, insertion and deletion is performed at the top end.
 Stack follows the Last-In-First-Out (LIFO) methodology, which means
whichever data that enters at last will be removed at first.
Below is a table (Table 1) that shows the Advantages and Disadvantages of Stack
Data Structure
Advantages Disadvantages
Dynamic memory allocation. Due to dynamic allocation of memory.
Memory is wasted if we don’t use the
entire memory.
Easy to add or remove elements. Hard to access elements that are not at
the top of the Stack.
Widely used for vital features like
undo/redo.
Less flexible.
Capable of automatically cleaning up
objects.
Lack of scalability.
Table 1: Pros and Cons of Stack Data Structure

2
Data Structure and Algorithm Individual Assignment
Operations of Stack
 Stack operations involves initializing the stack, using it and then de-initializing it.
A stack is used for the following two primary operations.
1. push() − Pushing (storing) an element into the Stack
2. pop() − Removing (accessing) an element from the Stack
 To use a stack efficiently, need to check the status of Stack as well. For that
purpose, the following functionalities are added to Stacks.
 peek() - Gets the top data element of the stack, without removing it
 isFull() - Checks if the Stack is full
 isEmpty() - Checks if the Stack is empty
Stack operation 1: push()
Push operation involves following steps: -
Step 1 − Checks if the stack is full.
Step 2 − If the stack is full, produces an error and exit.
Step 3 − If the stack is not full, increments top to point next empty space.
Step 4 − Adds data element to the stack location, where top is pointing.
Step 5 − Returns success.

3
Data Structure and Algorithm Individual Assignment
Stack operation 2: pop()
Pop operation involves in the following steps: -
Step 1 − Checks if the Stack is empty
Step 2 − If the Stack is empty, produces an error and exit
Step 3 − If the Stack is not empty, accesses the data element at which top is pointing.
Step 4 − Decreases the value of top by 1
Step 5 − Returns success
Real-time Example for Stack
A real-time example for Stack would be a bunch of plates put together on top of each
other, therefore the plate at the topmost is accessible. Adding and removing plates
happens at the top end. Neither adding nor removing can be made from the bottom or
middle of the Stack. Resulting in a Last In First Out (LIFO) or First In Last Out
(FILO) basis.
Figure 1: Stack Example

4
Data Structure and Algorithm Individual Assignment
2. Queue
 Also an abstract data type and similar to Stack but unlike Stack, Queue is open on
both ends.
 One opening is used for inserting data and the other is is used for deleting data
which is called enqueuing and dequeuing respectively.
 Queue follows the First-In-First-Out (FIFO) methodology, which means
whichever data that enters at first will be removed at first.
Below is a table (Table 2) that shows the Advantages and Disadvantages of Queue
Data Structure
Advantages Disadvantages
Helpful when multiple users/consumers
share a particular process in special cases.
More complex than Stack Data Structure.
Flexible. Bigger array is needed than the number
of pieces of data.
Can remain active when there are no
entries.
Memory is wasted unless queue is
modified. Ex: - Circular queues
Table 2: Pros and Cons of Queue Data Structure
Operations of Queue
 Queue operations involves initializing or defining the queue, utilizing it, and then
completely erasing it from the memory. Here we shall try to understand the basic
operations associated with queues −
1. enqueue() − Add (store) an item to the queue
2. dequeue() − Remove (access) an item from the queue
 Few more functions are required to make the above-mentioned queue operation
efficient. They are: -
 peek() − Gets the element at the front of the queue without removing it
 isFull() − Checks if the queue is full
 isEmpty() − Checks if the queue is empty

5
Data Structure and Algorithm Individual Assignment
Queue operation 1: enqueue()
Enqueue operation consists of the following steps: -
Step 1 − Checks if the queue is full
Step 2 − If the queue is full, produce overflow error and exit
Step 3 − If the queue is not full, increment rear pointer to point the next empty space
Step 4 − Adds data element to the queue location, where the rear is pointing
Step 5 − Returns success
Queue operation 2: dequeue()
Dequeue operation consists of the following steps: -
Step 1 − Checks if the queue is empty
Step 2 − If the queue is empty, produce underflow error and exit
Step 3 − If the queue is not empty, access the data where front is pointing
Step 4 − Increment front pointer to point to the next available data element
Step 5 − Return success
Real-time example for Queue Data Structure
Real-time example for Queue would be some cars forming a line in a drive-through
waiting to get their order whichever car comes first is served first, and whichever car
comes at the last is served last. Resulting in a First In First Out basis (FIFO) or Last In
Last Out basis (LILO).
Figure 2: Queue Example