Data Structure and Algorithm

A data structure is a collection of data pieces that provides an efficient method for storing and organising data in a computer so that it may be used effectively. Arrays, Linked Lists, Stacks, Queues, and other Data Structures are examples.

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

6
Data Structure and Algorithm Individual Assignment
Identification of Data Structure for given Scenario
As per scenario mentions that Player 1 will be inserting balls on top of each other in a
tube container and Player 2 fires whichever ball is on top and then the next one
becomes available. So the last ball that enters the tube is fired at first. Therefore, the
most suitable data structure is the Stack data structure as it is Last In First Out (LIFO)
or First In Last Out (FILO) which meets the criteria in the scenario. Pushing and
Popping occurs only at one end and that is what Stack Data structure is about.

7
Data Structure and Algorithm Individual Assignment
Task 1. B)
Figure 3: Stack Class - Java
Figure 4: Stack Main Class - Java

8
Data Structure and Algorithm Individual Assignment
Figure 5: Stack DS Output
Please note:— Stack data structure source code is added to the folder attached with
this document in “Stack DS” sub-folder

9
Data Structure and Algorithm Individual Assignment
Task 2. A)
Sorting Algorithms
There are many Sorting algorithms such as Quick, Bubble, Insertion, Selection, Heap,
Quick3, Counting, Combo sorting etc. This report focuses on 3 simple Sorting
Algorithms. They are: -
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
1. Bubble Sort
Repeatedly compares and if needed swapsadjacent elements in every round. In i-th
round of Bubble Sort (ascending order), last (i-1) elements are already sorted, and i-th
largest element is placed at (N-i)-th position, i.e. i-th last position.
Time Complexity:
Best Case: Sorted array as input. Or almost all elements in proper place.[O(n)].
O(1) swaps.
Worst Case: Reversely sorted / Very few elements are in proper place. [O(n2)] .
O(n2) swaps.
Average Case: [O(n2)] . O(n2) swaps.
Space Complexity:
A temporary variable is used when swapping [auxiliary, O(1)]. Therefore it
sorts in-place

10
Data Structure and Algorithm Individual Assignment
2. Selection Sort
Selects i-th smallest element and places at i-th position. This algorithm divides the
array into two: sorted (left) and unsorted (right) subarray. It selects the smallest
element from unsorted subarray and places in the first position of that subarray
(ascending order). It repeatedly selects the next smallest element.
Time Complexity:
Best Case: [O(n2)]. Also O(n) swaps.
Worst Case: Reversely sorted, and when the inner loop makes a maximum
comparison. [O(n2)] . Also, O(n) swaps.
Average Case: [O(n2)] . Also O(n) swaps.
Space Complexity:
[auxiliary, O(1)]. In-Place sorting.
3. Insertion Sort
Simple comparison based sorting algorithm. It inserts every array element into its
proper position. In i-th iteration, previous (i-1) elements (i.e. subarray Arr[1:(i-1)]) are
already sorted, and the i-th element (Arr[i]) is inserted into its proper place in the
previously sorted subarray.
Time Complexity:
Best Case: Sorted array as input, [O(n)]. And O(1) swaps.
Worst Case: Reversely sorted, and when inner loop makes maximum comparison,
[O(n2)] . And O(n2) swaps.
Average Case: [O(n2)] . And O(n2) swaps.
Space Complexity:
[auxiliary, O(1)]. In-Place sorting.

11
Data Structure and Algorithm Individual Assignment
Algorith
m
Time
Complexity
(Best)
Time
Complexity
(Average)
Time
Complexity
(Worst)
Space
Complexity
Bubble
Sort
O(n) O(n2) O(n2) O(1)
Insertion
Sort
O(n) O(n2) O(n2) O(1)
Selection
Sort
O(n2) O(n2) O(n2) O(1)
Table 3: Big O Time Complexity Chart
In the best case scenario there is one difference with Selection Sort. Selection Sort
requires more time even when the data is almost sorted. Bubble Sort and Insertion
Sort require very few swaps. Also, Selection Sort requires the same amount of
searching process even within almost sorted data.
Identification of Pros and Cons among Sorting Algorithms
Algorithm
s
Advantages Disadvantages
Bubble
Sort
It is the simplest sorting approach. It is comparatively a
slower algorithm
Best case complexity is of O(N) [for
optimized approach] while the array is
sorted.
Using optimized approach, it can detect
already sorted array in first pass with
time complexity of O(1).
Stable sort: does not change the relative
order of elements with equal keys.
In-place sorting.

12
Data Structure and Algorithm Individual Assignment
Selection
Sort
It can also be used on list structures that
make add and remove efficient, such as
a linked list. Just removes the smallest
element of unsorted part and end at the
end of sorted part.
Time complexity in all
cases is O(n2), no best
case scenario.
The number of swaps reduced. O(N)
swaps in all cases.
In-place sorting.
Insertion
Sort
Can be easily computed It is generally used when
the value of N is small.
For larger values of N, it
is inefficient.
Number of swaps are lesser than bubble
sort
Stable
In-place
Best case complexity is of O(n)
while the array is already sorted
For smaller values of N, insertion sort
performs efficiently like other quadratic
sorting algorithms
Adaptive: total number of steps is
reduced for partially sorted array
Table 4: Pros and Cons of Sorting Algos

13
Data Structure and Algorithm Individual Assignment
Justification
To sort the given array in the assignment, Insertion sorting is chosen as it is most
efficient algorithm out of the 3 due its optimization on smaller arrays and it requires
less swapping than Bubble sort which results in quicker output and the reason
Insertion sort is chosen over Selection Sort is due to its less swapping and quicker
access to data elements comparatively as seen on Table 3. Selection sort can be used
in places where swapping is costly
Task 2. B)
Figure 6: Insertion Sort Function

14
Data Structure and Algorithm Individual Assignment
Figure 7: Display and Main method
Figure 8: Insertion sort Output
Please note:— Insertion
sort source code is added to
the folder attached with
this document in “Insertion
Sort” sub-folder

15
Data Structure and Algorithm Individual Assignment
Task 3. A)
Recursion
The process of a function calling itself directly or indirectly is known as recursion and
the corresponding function is called as recursive function. With the help of recursive
algorithm some complex tasks can be made simple. Examples of such problems are
Towers of Hanoi (TOH), Fibonacci series, Factorials, Inorder/Preorder/Postorder Tree
Traversals, DFS of Graph, etc.
Identification of Advantages and Disadvantages of Recursion Algorithms
Advantages Disadvantages
Lines of code becomes shorter than
iterative since only base case and
recursive case has to be defined.
Space complexity — System needs to
store activation record each time a
recursive call is made therefore more
storage is required.
Much easier to understand. Time complexity — It also has greater
time requirements because each time the
function is called, the stack grows and the
final answer is returned when the stack is
popped completely.
More efficient due to latest enhancements
in CPU.
Must have an if statement somewhere to
force the function to return without the
recursive call being executed, otherwise
the function will never return.
Table 5: Pros and Cons of Recursive Algorithm

16
Data Structure and Algorithm Individual Assignment
Task 3. B)
Figure 9: Recursion Algorithm
Figure 10: Recursive Algorithm output
Please note:—Recursion Algorithm source code is added to the folder attached with
this document in “Recursion Algo” sub-folder

17
Data Structure and Algorithm Individual Assignment
References
Premakumar, P., 2020. Stack.
Premakumar, P., 2020. Queue.
Premakumar, P., 2020. Recursion.
GeeksforGeeks. 2020. Comparison Among Bubble Sort, Selection Sort And Insertion
Sort - Geeksforgeeks. [online] Available at:
<https://www.geeksforgeeks.org/comparison-among-bubble-sort-selection-sort-and-
insertion-sort/> [Accessed 24 November 2020].
Robert, C., 2020. The Advantages Of A Queue In Data Structure | Techwalla. [online]
Techwalla. Available at: <https://www.techwalla.com/articles/the-advantages-of-a-
queue-in-data-structure> [Accessed 24 November 2020].
GeeksforGeeks. 2020. Stack Data Structure - Geeksforgeeks. [online] Available at:
<https://www.geeksforgeeks.org/stack-data-structure/> [Accessed 24 November
2020].
Tuteja, S., 2020. Recursion - Geeksforgeeks. [online] GeeksforGeeks. Available at:
<https://www.geeksforgeeks.org/recursion/> [Accessed 24 November 2020].

18
Data Structure and Algorithm Individual Assignment
Appendix A
Gantt Chart
Figure 11: DSA Gantt Chart