Data Structures and Algorithms: A Comprehensive Report

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

BTEC HND in
Computing
Data Structures and
Algorithms (L5)
Student name
Student ID

Contents
Introduction......................................................................................................................................4
LO1 Examine abstract data types, concrete data structures and algorithms....................................5
P1 Create a design specification for data structures explaining the valid operations that can be
carried out on the structures.........................................................................................................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 (FIFO) queue.6
M2 Compare the performance of two sorting algorithms...........................................................7
LO2 Specify the abstract data types and algorithms in a formal notation.....................................12
P3 Using an imperative definition, specify the abstract data type for a software stack............12
M3 Examine the advantages of encapsulation and information hiding when using an ADT.. .13
LO3 Implement complex data structures and algorithms..............................................................15
P4 Implement a complex ADT and algorithm in an executable programming language to solve
a well-defined problem..............................................................................................................15
P5 Implement error handling and report test results..................................................................23
M4 Demonstrate how the implementation of an ADT/algorithm solves a well defined problem.
...................................................................................................................................................24
LO4 Assess the effectiveness of data structures and algorithms...................................................25
P6 Discuss how asymptotic analysis can be used to assess the effectiveness of an algorithm. 25
P7 Determine two ways in which the efficiency of an algorithm can be measured, illustrating
your answer with an example....................................................................................................26
M5 Interpret what a tradeoff is when specifying an ADT using an example to support your
answer........................................................................................................................................28
Conclusion.....................................................................................................................................30
References......................................................................................................................................31

List of figures
Figure 1 Abstract data types............................................................................................................5
Figure 2 Comparison of quick sort and bubble sort........................................................................7
Figure 3 Quick sort1........................................................................................................................8
Figure 4 Quick sort2........................................................................................................................9
Figure 5 Bubble sorting.................................................................................................................10
Figure 6 Bubble sort using c#........................................................................................................11
Figure 7 Abstract data type in software stack................................................................................12
Figure 8 Code 1.............................................................................................................................15
Figure 9 Code 2.............................................................................................................................16
Figure 10 Code 3...........................................................................................................................17
Figure 11 code 4............................................................................................................................18
Figure 12 Code 5...........................................................................................................................19
Figure 13 Code 6...........................................................................................................................20
Figure 14 Output screen.................................................................................................................21
Figure 15 Insert value....................................................................................................................21
Figure 16 Details of elements.......................................................................................................22
Figure 17 Next value.....................................................................................................................22
Figure 18 removing the elements..................................................................................................23
Figure 19 add element...................................................................................................................23
Figure 20 element already exist.....................................................................................................24
Figure 21 Worst case of quick sort................................................................................................27
Figure 22 Best case of quick sort...................................................................................................27
Figure 23 Average case complexity of quick sort.........................................................................28

Introduction
The data structure is a programmatic method for the storage of data and information is structured
and organized manner. Algorithms are the step by step methods that can be used for problem
solving. This report covers various factors of programming using the C# programming language.
The report has mainly four sections. The first part of the report includes an examination of
various data types along with algorithms and data structures. This also includes various
operations of different type of data structures. The second section will define the type of various
abstract data types. The next section will cover the implementation of these for problem-solving
and a discussion on the algorithm’s effectiveness. The last section will describe the algorithm
efficiency with the help of examples.

LO1 Examine abstract data types, concrete data structures, and
algorithms
P1 Create a design specification for data structures explaining the valid
operations that can be carried out on the structures.
Records are used by the structures like an array to perform different actions in the database. The
data structure is categorized into two categories:
 Linear: In this type of data structure, the data is presented and retrieved in a sequence from
various locations of memory.
 Non-linear: In this type of data structure, data is presented in the form of graph and tree.
Various data structure operations are given below:
 Searching: This operation is used to find the records and files with the help of name or key.
 Traversing: This operation is used to access the records or data from the database.
 Inserting: This operation is used to add a record in the collection of data
 Merging: This operation is used to merge/ combine the records into a file from distinct files.
 Sorting: this operation is used to arrange the records in a particular order. This order can be
ascending or descending.
 Deleting: This operation is used to remove any data record from the database.
ADT (abstract data type) and CDT (Concrete data type) are the opposite of each other. In ADT
behavior is not executed but explained whereas, in CDT, ADT is executed (GeeksforGeeks,
2019).
Figure 1 Abstract data types

(Source: Sqa.org.uk, 2019)
P2 Determine the operations of a memory stack and how it is used to
implement function calls in a computer.
Memory stacks refer to linear data structures that are used as data storage in the memory of the
computer. In the stack, data is always of the same type. Stack only allows insertion and deletion
operations in a sequence. Stack follows last in first out (LIFO) which is useful for the
optimization and management of the data. The PUSH function refers to the insertion of data and
POP function refers to the deletion of data.
Stack uses function calls for the management of de-allocation and allocation of the data in the
memory of stack.
 Call: This function is used in the computer memory for shifting the variables to a new
memory location. First, space is created in the stack of memory and then the function is
called. So, basically, the compiler uses the call function to move the variables into the new
memory location.
 Return: This function is useful to return the control. The function performed by the Return
function in memory stack is known as RET. This is useful for the execution restoration of the
memory stack.
M1 Illustrate, with an example, a concrete data structure for a First In First
Out (FIFO) queue.
Concrete data structure: A simple concept is followed by the concrete data structure. It does
not represent the data records. The concrete data structure is divided into three categories that are
linked, contiguous and hybrid.
Queue: This is an abstract data type. This follows First in first out concept for the operations.
Queue implementation with an array is the best example of a concrete data structure. Usually,
queue stores data that is heterogeneous but when implemented with an array, it is used for
homogenous data. The queue has the following operations:
 Display (): to display the queue elements
 Size (): this function tells the size of the queue by counting the number of elements presented
in it.
 Enqueue(): This operation is used to insert the element in the queue.
 Dequeue(): this operation is used to delete the element from the queue.
 Front (): This operation is used to get the top element of the queue
 isEmpty(): used to check whether the queue is empty
 isFull(): Used to check whether the queue is full
CPU Job scheduling is a great example of the queue data structure. In this, the job which comes
first is executed first (GeeksforGeeks, 2019).

M2 Compare the performance of two sorting algorithms.
Sorting algorithms are used to arrange the elements of data structure in an ascending or
descending order or alphabetical order. These algorithms take the data as an input and perform
different operations on it, in order to do the sorting. There are many kinds of sorting algorithms
available such as bubble sort algorithm, merge sort, quick sort, selection sort, heap sort, etc.
Comparison of two of these algorithms is given below:
Criteria Quicksort Bubble sort
Stability Not stable Stable
Time complexity Worst case O (n2) O (n2)
Average case O (n2) O(n*log(n))
Best case O (n) O(n*log(n))
Space complexity Worst case O (n) O (1)
Memory Worst case N
Average case Log n
Worst case 1
Average case 1
Figure 2 Comparison of quicksort and bubble sort
Quicksort:
It is based on the divide-conquer method of sorting. In this method, the complete array is divided
into sections and these sections are sorted accordingly in a single list. A value is selected in this
that is known as the pivot value (Shanker, 2013).
Figure 3 Quick sort1

Figure 4 Quick sort2
(Source: w3resource, 2019)
Bubble sort:
This sorting algorithm is based on the comparison of each adjacent element and then swaps the
element in order to sort it. This algorithm is easy to understand and implement but the algorithm
is slow. This is only suitable when there are fewer elements in the array.

Figure 5 Bubble sorting

Figure 6 Bubble sort using c#

LO2 Specify the abstract data types and algorithms in a formal notation
P3 Using an imperative definition, specify the abstract data type for a software
stack.
This is a set of autonomous component that supports the execution of the application by working
together with each other. These components may be architectural arrays, operating system,
databases, run-time environments, and function calls. These components are stacked in order to
perform operations (Rouse, 2019).
Using the software stack give various advantages:
 They offer predefined solutions for the problems
 They require minimum software ability to perform operations in order to achieve the goal.
 Mostly software stacks have the support for the complete package.
 These can also be added to the templates to support the automatic execution and installation.
Some of the examples of software stack LAMP which consists of Apache, Linux, PHP, and
MySQL. This software stack is useful in web development. MEAN is the other example of the
software stack (GeeksforGeeks, 2019).
Figure 7 Abstract data type in the software stack
Data type refers to the type of data and used in data processing. It is necessary to define the type
of data before storing it into the database. LIFO (last in first out) is used to perform the insertion

and deletion of the elements in the stack. There are some operations that can be performed on the
stack:
 Push(): This operation is used to add the element in the stack. This element adds on the top of
the stack.
 Pop(): This operation is used to delete the element in the stack. This modifies the stack by
removing the data from the top.
 Peek(): This operation is used to return the top element of the stack. It does not need any
parameter and doesn’t require any kind of parameter.
 MakeEmpty(): This operation is used to delete all the elements from the stack.
 Size(): This operation is used to return the size of stack by counting the elements of it.
 isEmpty(): It is used to check whether the stack is empty or not.
 isFull(): This operation is used to check whether the stack is full or not.
M3 Examine the advantages of encapsulation and information hiding when
using an ADT.
Encapsulation: This is a concept of OOPS (object-oriented programming language).
Encapsulation is used to collect the data in a unit. This is useful to hide the object or the internal
representation of data. This concept is really useful to improve the security of software by data or
information hiding. This does not affect the overall functionality. There are several advantages of
the encapsulation:
 This prevents the information or data from the by mistaken deletion.
 This improves the extensibility and flexibility f the program code
 This minimizes the complexity of the program
 This improves the maintainability (GeeksforGeeks, 2019)
There are many access modifiers such as public, private, protected which is used to perform
encapsulation. Encapsulation is allowed in c# with the help of mutators to get the information
and accessors to get the information (Techopedia.com, 2019).
Information hiding:
This is one of the important of the OOPS. Information hiding and abstraction are co-related with
each other. Information hiding is used to hide the details of implementation for the purpose of
security. This ensures that sensitive information should only be accessible to the authorized
person only and thus improves security. There are some following advantages of the information
hiding principle:
 This minimizes the program complexity
 This helps to improve program security by offering limited access to only authorized persons.
 This also offers flexibility by enabling easy modification.