Data Structures and Algorithms: A Comprehensive Project

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

DATA STRUCTURES AND
ALGORITHMS

Contents
Introduction:...............................................................................................................................4
LO1 Examine abstract data types, concrete data structure and algorithms................................5
P1 Create a design specification for data structure explaining the valid operations that can
be carried out on the structure................................................................................................5
P2 Determine the operations of a memory stack and how it is used to implement function
calls in a computer.................................................................................................................6
M1 Illustrate with an example, a concrete data structure for a first in first out queue (FIFO)
................................................................................................................................................7
M2 Compare the performance or two sorting algorithms......................................................8
LO2 Specify abstract data types and algorithms in a formal notation.......................................9
P3 Using an imperative definition specify the abstract data types for a software stack........9
M3 Examine the advantages of encapsulation and information hiding when using an ADT
..............................................................................................................................................10
LO3 Implement complex data structures and algorithms........................................................11
P4 Implement a complex ADT and algorithm in an executable programming language to
solve a well-defined problem...............................................................................................11
P5 Implement error handling and report..............................................................................16
M4 Demonstrate how the implementation of an ADT/algorithm solves a well-defined
problem................................................................................................................................17
LO4 Access the effectiveness of data structure and algorithms..............................................18
P6 Discuss how asymptotic analysis can be used to assess the effectiveness of an algorithm
..............................................................................................................................................18
P7 Determine two ways in which the efficiency of an algorithm can be measured,
illustrating your answer with an example............................................................................20
M5 Interpret what a trade-off is when specifying an ADT using an example to support your
answer..................................................................................................................................20
Conclusion:..............................................................................................................................22
References................................................................................................................................23
Appendix:.................................................................................................................................25

List of images:
Figure 1 Constructor of Queue.................................................................................................11
Figure 2 Adding a task in the queue.........................................................................................12
Figure 3 Deleting a task from the queue..................................................................................12
Figure 4 Program Menu...........................................................................................................13
Figure 5 Adding Job option......................................................................................................13
Figure 6 Removing option.......................................................................................................14
Figure 7 Checking next job in the queue.................................................................................14
Figure 8 Total Job available in the queue................................................................................15
Figure 9 Clear all the elements in the queue............................................................................15

Introduction:
Data structure and algorithm is a process that used to define the instructions to execute in a
particular order to get output. These instructions are used as the algorithm of a programming
language with using some terms like search, insert, delete, sort and update. The current
scenario is to define the relationship with the ADTs to the management. The first part of the
report used to define the different types of data types with their algorithms and the next part
includes the formal notation with using the software stack and abstract data types. Implement
the complex data algorithm with using the C# in this third part and the last part contain the
information about the apoptotic notation in different ways.

LO1 Examine abstract data types, concrete data structure and algorithms
P1 Create a design specification for data structure explaining the valid
operations that can be carried out on the structure
Data structure and algorithm is a process to get the output with using an algorithm of the
programming algorithm. The data structure used different operations in the database and its
different category like search, to search an item in the data structure, sort for the sorting
operations, insert to insert an element in the data structure, use an update to update the list of
items and follow delete to remove an element from the database.
Algorithms follow a process with using different characteristics like input, output, feasibility,
unambiguous, finiteness and independent. Here, the input is for the algorithm that has an
input value with zero or more. On the other side, the output is used for the value of one or
more. Finiteness is used to terminate the algorithms by using finite numbers. Feasibility is
used to make feasible the resource. There is no standard formula to write an algorithm as it
defines in different ways. Analysis of the algorithm is possible with two different methods
like a priori analysis and a posterior analysis (tutorialspoint, 2019).
The algorithm uses different factors that are time and space factor in algorithm complexity.
Space complexity is used to represent the memory amount and the time complexity is used to
represent the required time to run the algorithm,
The data structure has different operations in the two types of the data structure as define,
linear and nonlinear is the two types of data structure that used to define the define different
operations of the data structure. The operations of the data structure are, traversing,
searching, inserting, deleting, merging and sorting (Sood, 2019).

P2 Determine the operations of a memory stack and how it is used to implement
function calls in a computer
A linear data structure or the location that used store data in the memory of the computer
system is known as memory stacks. It is also known as the queues. Data that is available in
the stack or the queue is the same type of data. Items or the data used to delete and insert
from the stack in linear order as it does not follow the random sequence order. Data used to
store in the stack in a sequence with using different techniques LIFO. The term LIFO used
two operations as Push and Pop. Sometimes it is also including the Peek and Search
operations.
 Push: it used to insert the data into the stack in the additional plates that are known as
stacks. The first data get a place in the bottom of the stack when it enters into the
stack.
 Pop: this operation used to remove data from the stack as the stack is loaded with the
data. The data removed from the top of the stack using the plate.
 Peek: this operation does not contain any data to add or remove as it just used to
identify the address or the location of the stack.
 Search: used to search any data in the stack with using this operation (GeeksforGeeks,
2019).

M1 Illustrate with an example, a concrete data structure for a first in first out
queue (FIFO)
Queue is an example of the abstract data type that used to follow the operation FIFO (first in
first out). The elements stored in this queue as it arrives in the stack in order to first in first
out. This function has different uses in the operations of the computer system. here provides
an example of the queue as below:
In this below example, the queue is the abstract data type.

M2 Compare the performance or two sorting algorithms
Sorting is the term used to manage data of an algorithm or a process in a sequence form.
Different types of sorting techniques are used to perform these operations like the bubble
sort, selection sort, merge sort, quick sort and many more. Create a comparison on different
factors between two sorting techniques, merge sort and quick sort as:
Factors Merge Sort Quicksort
Average O(n*log(n)) O(n*log(n))
Best O(n*log(n)) O(n*log(n))
Worst O(n*log(n)) O(n2)
Space Depends Constant
Stability Stable Stable
Remarks This sorting technique needs
O(n) spaces on arrays and
required constant space on a
linked list
Random takes a value with the
sorting technique to ignore the
worst case to sort an array
Allain, (2019)

LO2 Specify abstract data types and algorithms in a formal notation
P3 Using an imperative definition specify the abstract data types for a software
stack
ADT (abstract data types) is a class type for an object that used to define its behaviour by
using a set of operations and values. ADT used to define the list operations that are going to
perform and to be implemented. Data can’t be organised in the memory with using these data
types as well as the operations. As this process hides the details then it is known as
abstraction. Different kinds of abstract data types are used to define for a software stack as:
 List ADT: a list of the same type of elements used to arrange this list ADT and
perform different operations on the element of the list as,
o get() to return an element from the list
o isFull() to return true or false as per conditions
o isEmpty() to return true or false as per conditions
o removeAt() to remove a specific location element
o In other common type remove(), insert(), replace() and size()
 Stack ADT: same type of elements arrange in stack with sequential order to perform
different operations
o Push() to insert element
o Pop() to remove element
o Peek() return element from the stack-top when stack is not empty
o In other size(), isEmpty() and isFull()
 Queue ADT: same type of elements arrange in a queue with sequential order to
perform different operations
o enqueue() to insert an element at last of queue
o dequeue() to delete & return element first element from queue when queue is
not empty
o In other peek(), size(), isFull() & isEmpty()
(GeeksforGeeks, 2019)

M3 Examine the advantages of encapsulation and information hiding when using
an ADT
Encapsulation is used to bind the data in a unit and this unit is the single unit. In Java, it binds
the code and data and provides security features like flexibility, security and easy to maintain.
These terms are also the advantages of the encapsulation with reusability and test of the code
with data hiding.
Follow the process to hide the formations during the execution of a system with the object of
the system. This object includes the private methods and information that can change with
effect any other object. In the advantage of the information hiding for the client, it is easy to
understand and protect the implementation details (McKinney, 2016).

LO3 Implement complex data structures and algorithms
P4 Implement a complex ADT and algorithm in an executable programming
language to solve a well-defined problem.
To implement a complex Abstract Data Type, the ADT which is being chosen is the Queue
Data Structure. Queue follow FIFO manner which means that First In First Out. It means that
the job which is being entered in the queue at first will be removed first after completing its
execution. The program of Queue is being built in C# programming language which is an
Object-Oriented Programming Language and follows the fundamentals of OOP’s. In this
way, a more complex data structure is being built on C#. Below are some snippets of C#
program in which Queue is being implemented and the functionalities which are being
performed by the program. This program will have the functionality of adding, deleting and
removing a job and displaying the total number of jobs which are available in the queue and
Showing the job which is present at front and rear of the queue. (Keller et al.,2016)
Figure 1 Constructor of Queue.
The above snippet of code will be defining the constructor which is initializing the array list
and the rear and Front task of the queue and setting those two values as null.

Figure 2 Adding a task in the queue
The code which is being shown above is about adding a new element in the queue and
checking that this element is already present in the queue or not. If this task is already present
in the queue it will dispute lay the message that job already exists in the queue.
Figure 3 Deleting a task from the queue.