Data Structures, Algorithms, and Their Applications

Desklib provides solved assignments and past papers to help students understand complex topics like data structures and algorithms.

Data Structures and Algorithms

Table of Contents
List of Figures..................................................................................................................................3
Introduction......................................................................................................................................4
LO1..................................................................................................................................................5
P1.................................................................................................................................................5
P2.................................................................................................................................................5
M1................................................................................................................................................6
M2................................................................................................................................................8
LO2................................................................................................................................................12
P3...............................................................................................................................................12
M3..............................................................................................................................................15
LO3................................................................................................................................................16
P5...............................................................................................................................................16
LO4................................................................................................................................................18
P6...............................................................................................................................................18
P7...............................................................................................................................................19
M7..............................................................................................................................................20
Conclusion.....................................................................................................................................21
References......................................................................................................................................22

List of Figures
Figure 1: Linear Representation of Stack........................................................................................5
Figure 2: Representation of Queue..................................................................................................6
Figure 3: First In First Out Implementation....................................................................................7
Figure 4: Queue output....................................................................................................................7
Figure 5: Example of selection sort.................................................................................................8
Figure 6: Flow Chart of Selection sort............................................................................................9
Figure 7: Implementation of Selection Sort using C#...................................................................10
Figure 8: Output Selection sort......................................................................................................10
Figure 9: Partition function in Quicksort Figure 10: Quicksort
methodology, Divide and Conquer................................................................................................11
Figure 11: Output Quicksort..........................................................................................................11
Figure 12: C# code for Quick sort.................................................................................................11
Figure 13: Implementation of Stack in C#....................................................................................14
Figure 14: Encapsulation...............................................................................................................15
Figure 15: Various type of Exception............................................................................................18
Figure 16 Invalid Choice...............................................................................................................19
Figure 17 Main Screen of Program in Console.............................................................................19
Figure 18 Insertion of Job in Queue..............................................................................................20
Figure 19 Deleting a Job From Queue...........................................................................................20
Figure 20 Displaying the front Job................................................................................................21
Figure 21 Number of Available Job in Queue...............................................................................21
Figure 22 Clearing the List of Jobs in queue.................................................................................22
Figure 23 Peek...............................................................................................................................22
Figure 24: Omega notation............................................................................................................23
Figure 25: Big Oh notation............................................................................................................24
Figure 26: Quick sort representation.............................................................................................25

Introduction
In this report, we will learn and discuss various aspects, methods, and ways of data structure and
their respective algorithms. In LO1 we will examine the type of Abstract data type, concrete data
structure, and algorithms. Furthermore, we will see how the linear data structure like stack and
queue works and how their methodology FIFO and FILO works on real-world application. Also,
we will compare two sorting algorithms which are selection sort and quick sort with their
respective parameters.
In LO2 we will learn about ADT and various advantages of Encapsulation and data hiding and
how information hiding helps the user and the programmer.
In LO3 we will discuss cases of exception handling and what are the keywords used in various
cases of this function. Lastly, in LO4 we have to determine asymptotic notations for each type of
test cases and what is a trade-off between space and time complexity.

LO1
P1
ADT or Abstract Data Type is a class or type which have objects and their values are set by a
certain value set or set of various operations. In ADT or Abstract Data Type, the only disclosure
is about what operations to perform and not about how those operations are performed. This
means that if a value is declared the user will only understand what is its type but not about how
those certain values or operations are set (Alsuwaiyel, et.al.,2016).
For example, in many of our computer programs we use integer(int), float, char(character), bool
(Boolean), etc. for declaring so many values and at the user end we only knew what type of value
is declared but not how those value with their respective data types are getting declared and all
this is responsible because of ADT or Abstract Data Type. To simplify this concept, we can
consider ADT as the Black Box which protects the inner structure and the design configuration
of any given data type or data structure.
There are three types of ADT:
1. List ADT
2. Stack ADT
3. Queue ADT
P2
There are 2 types of data structure, first is linear data structure and the second type is non-linear
data structure. The linear data structures are the one whose store data only in one dimension
which means they store data sequentially or linearly. One of the examples of linear data structure
is Stack. The key characteristic of the stack is that it’s generally for the most of is cases proceeds
in a sequential approach which is the only way of performing operations in data structures like a
stack. The stack can be determined as two of the following methodology, one of which is LIFO
which stands for Last In First Out or another of looking at stack is FILO which understand for
First In Last Out.
Figure 1: Linear Representation of Stack

To explain in general terms stack can be said as the set of plates set on a dining table which
means that in order to get to the last plate we have to remove all of the above ones which means
the plate which is placed first is the one that will get out at the last , or the plate which is placed
at last on top is the one to be removed at first.
There are various functions of the stack in ADT and they are as follows:
1. Push(): to insert a value in the stack.
2. Pop(): to remove a value from the stack
3. Peek(): to remove selected value from the stack without rearranging the rest of the stack.
4. Size(): to return the size of the stack as output.
5. isEmpty(): it will return false if the stack is not empty otherwise true.
6. isFull(): it will return false if the stack is empty otherwise it will return true if the stack is
full.
M1
Another example of a linear data structure is a Queue. The queue is very similar to stack in many
ways but its rear end is used to insert the elements inside the queue and the front end is used to
remove the elements from the queue. The methodology behind Queue is FIFO which
understands for First In First Out. In general terms it means whichever element is inserted in the
queue at first will be the one to be also removed at first and the last element inserted in the queue
will we the last one to get removed from the queue.
Let’s consider a real-life example, in a restaurant the customer which get served first is the only
who arrives at the restaurant first and the last one will get served at last.
Figure 2: Representation of Queue

Figure 3: First In First Out Implementation
Figure 4: Queue output
In ADT queue we have various queue function, which is listed below:
1. dequeue(): use to remove an element from the queue.
2. enqueue(): use to insert an element from the queue.
3. peek(): return the selected element, until the size >0
4. Size(): return the size of the queue.

5. isEmpty(): To check if the queue is empty or not, if it is then it will return true otherwise
false
6. isFull(): To check if the queue is full or not if it is then it will return true otherwise false.
M2
The sorting algorithms for this section are:
1. Selection Sort
2. Quick Sort
Selection Sort
The way in which selection sort works is by selecting the lowest or minimum number again and
again from the array and assigning it at the beginning position and differentiating it from the
unsorted part of the array. There are two subarrays in selection sort method:
1. The subarray part which is already sorted
2. And the rest of the part which is not sorted at the moment
At every given instance of sorting loop, the minimum element from the unsorted subarray is
selected and transferred to the sorted array part (Teng, et.al.,2016).
Figure 5: Example of selection sort

Figure 6: Flow Chart of Selection sort

Selection Sort implementation using C#.
Figure 7: Implementation of Selection Sort using C#
Figure 8: Output Selection sort
Quick Sort
Quicksort also works on the same concept as merge sort which is Divide and Conquer algorithm.
In this algorithm, we select an element called a pivot element and we divide the array around this
said pivot element. There are four different methods to select a pivot element which are as
follows:

1. Always select the first element as the pivot element.
2. Always select the last element as the pivot element.
3. Random selection of any element as the pivot element.
4. Selecting median element as pivot element.
Using the partition function in quicksort is the key to sort the array. For example, we select x as a
pivot element now we divide the array into two groups such as all the numbers less than x are in
one array and all the number greater than x element is in the other array. The main point to focus
on is that this method should be implemented only with linear time.
Figure 9: Partition function in Quicksort Figure 10: Quicksort methodology, Divide and Conquer
Implementation of Quicksort using C#
This is the C# implementation of quicksort. In this, we can see that
how to partition function works in order to sort the elements using
divide and conquer methodology.
Figure 11: Output Quicksort
Figure 12: C# code for Quicksort

Performance comparison of Selection Sort and Quick Sort
Property Selection Sort Quick Sort
Time Complexity Worst case :O(n2)
Average case: Ѳ(n2)
Best case: Ω(n2)
Worst case :O(n2)
Average case: Ѳ(n log(n))
Best case: Ω(n log(n))
Space Complexity O(1) O(1)
LO2
P3
The main characteristic of stack data structure is that all the elements in it are of same data type
which means of one value is float then all the rest of the values will also be of data type float. All
the values in a stack follow a certain sequential order. Stack follows the methodology of LIFO or
Last in First Out, or FILO which means First in last out.