HIGHER NATIONAL DIPLOMA IN

SOFTWARE ENGINEERING

Acknowledgement
I’m really grateful because I managed to complete my Data Structures & Algorithms
within the time given by my lecture Praveena this assignment can’t be completed without
the assistance and the support of my lecture. I would like to thank my lecture for the
guidance and encouragement given, and also for teaching us in this course. Finally, I
would like to express my gratitude to my friends and respondents for the support and
willingness to spend some time with me to full fill my assignment.

Introduction
Data structures are a programmatic way of storing data so that data can be used
effectively. Almost every enterprise application uses different types of data structures in
one way or another.

The algorithm is often combined with terms that refer to the function in which the set of
rules is designed. A search algorithm, for example, is a process of determining what kind
of information is retrieved from a large amount of data. An encryption method is a set of
rules that encrypts information or messages so that unauthorized persons cannot read
them.

S. ARTHEKA DSA PEARSON ID: Page 1 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

TASK 01
1. Abstract data types
Abstract data types (ADT) is a kind (or class) of object whose behavior is
specified by a set of values and a set of operations. The definition of ADT merely
says what operations must be completed, not how these operations will be carried
out. It does not specify how data will be stored in memory or which algorithms
will be utilized to carry out the actions. It is named "abstract" because it provides
a view that is independent of implementation.
2. Data structure
A data structure is a method of organizing data so that it may be used efficiently.
1. Mathematical/ Logical/ Abstract models/ Views: A data structure is a method of
organizing data that necessitates the use of protocols or rules. These rules, which
fall under the logical/abstract model, must be modeled.
2. The second section is the implementation section. The rules must be written in a
computer language.
Why data structure?
1. These are the necessary factors for developing quick and powerful algorithms.
2. They assist us in managing and organizing data.
3. Data structures make the code more readable and understandable.
Some examples where the data structure used in the computer technologies:

a) Storing data
b) Managing resources and services
c) Data exchange
d) Ordering and sorting
e) Indexing
f) Searching
g) Scalability
3. Differentiate ADT and DS
Abstract Data Type Data Structure
A data type is one of the forms of a A data structure is a collection of
variable to which only values of a various data kinds. This set of data can
specific type can be assigned. This be represented by an object and used
value can be used throughout the throughout the program.
program.
The implementation of data type is The implementation of data structure
known as an abstract implementation. is known as a concrete
implementation.
It is capable of storing value but not It can store several sorts of data in a
data. As a result, we can say that it is single object.
data-free.
In the case of data types, a value can Certain operations are performed in
be explicitly assigned to the variables. the context of data structures to
allocate data to data structure objects.
There is no issue with temporal When dealing with a data structure
complexity. object, temporal complexity is crucial.
Data types include int, float, and char. Stack, queue, tree, and graph are
examples of data structures.

S. ARTHEKA DSA PEARSON ID: Page 2 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

4. Advantages of data structure

1. The data structure is an excellent choice for storing data on the framework.
2. Data structures make it easier to work with data.
3. Data structures also help us store data on circles more efficiently so that we
can recover it.
4. Data structures are essential for computation planning.
5. As previously stated, data structures are a means for organizing data into a
predefined structure. Presently, the speed of program execution is determined
by the data structure employed.
6. Data structures enable us to reuse information. In particular businesses, we can
construct a few data sets and store them in libraries for use by multiple clients.
7. Charts are data structures that allow us to visually represent, interact with, and
model real-world problems.
8. Trees are data structures that allow us to see, perform, and manipulate
hierarchical data sets. For example, after looking through a, the consumer will
look through b, which is widely employed in exploring related fields.
9. Data structures facilitate data discussion so that the client is not concerned
with how the data is stored in the framework.
10. Data structures given by various programming languages are accompanied by
implicit capabilities (or procedures) that allow us to make better use of the
specific database.
11. When working with huge data sets, the type of data structure utilized greatly
influences the program's effectiveness. As a result, choosing an appropriate
data structure is crucial.
12. In the database administration framework (DBMS) sector, data structures are
also used to create a list, store data using B and B+ trees, and so on.
13. Data structures are used to accomplish a variety of functional goals, including
dynamic memory distribution, process planning, record framework
association, word reference, and so on.

S. ARTHEKA DSA PEARSON ID: Page 3 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

5. Operations of data structures

Each data structure has different types of operations for manipulating data. Some
of the functions are described and explained below:
1. Traversing: Traversing a Data Structure means going from one element to
the next. It goes through data in a systematic manner. This is possible with
any form of DS.
Traversal in an array:

Figure 1

Traversal in a Stack:

Figure 2

S. ARTHEKA DSA PEARSON ID: Page 4 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

2. Searching: The term "searching" refers to the process of locating a certain

piece inside a given data structure. When the required element is
discovered, it is termed a success. Searching is an operation that can be
performed on data structures such as arrays, linked lists, trees, graphs, and
so on.
Searching in an array:

Figure 3

Searching in a Stack:

Figure 4

3. Insertion: It is the operation that we use on all data structures. Insertion is

the process of adding a new element to a data structure. Insertion is
complete when the required element is added to the required data-
structure. It fails in some circumstances when the size of the data structure
is full and there is no room in the data structure to add another piece. The
insertion is known as an insertion in a data structure such as an array,
linked-list, graph, or tree. This operation is known as Push in the stack.
This procedure is known as Enqueue in the queue.

S. ARTHEKA DSA PEARSON ID: Page 5 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

4. Deletion: It is the operation that we use on all data structures. Deletion

refers to the removal of an element from a data structure. When the
required element is deleted from the data structure, the deletion operation
is successful. The deletion is the same as a deletion in a data structure such
as an array, linked-list, graph, tree, and so on. This operation is known as
Pop in the stack. This operation is known as Dequeue in Queue.

Some other method:

1. Create: It declares software elements to reserve memory for them. The

development of a data structure Can be done during
i. Compile-time
ii. Run-time
2. Selection: It chooses specific data from the existing data. By specifying a
condition in the loop, you can select any specific data.
3. Update: It makes changes to the data in the data structure. You can also
update certain data by including a condition in the loop, similar to the
select approach.
4. Sort: Sorting data in a particular order (ascending or descending).
We can take the help of many sorting algorithms to sort data in less time.
Example: bubble sort which takes O(n^2) time to sort data. There are
many algorithms present like merge sort, insertion sort, selection sort,
quick sort, etc.
5. Merge: Merging data from two different orders in the same order may
ascend or descend. To merge sort data, we use merge sort.
6. Split Data: Data is divided into several sub-parts to speed up the process.

S. ARTHEKA DSA PEARSON ID: Page 6 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

6. Classification of Data Structures

a. Explain each classifications
Throughout our daily lives, data structures are used in a variety of ways.
There are numerous data structures that can be utilized to address various
mathematical and logical problems. Data structure allows one to organize
and handle a huge amount of data in a relatively short period of time.

Figure 5

Primitive Data Structures

These are fundamental structures that are directly manipulated by machine

instructions. In general, these have different representations on different
computers, including integers, floating point numbers, character constants,
string constants, pointers, and so on.

Non-Primitive Data Structures

Language, in general, allows us to define our own data type. Such data
types are classified as non-primitive data structures.

hence, these are the more advanced data structure. They are descended
from the basic data structure. Non-primitive data structures highlight the
organization of a collection of homogenous or heterogeneous data objects.

b. Specify and briefly explain about the types of each classifications

S. ARTHEKA DSA PEARSON ID: Page 7 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

Example of Primitive Data Structures

a) Float
A float is a data structure term used in various programming
languages that defines a variable with a partial value.

Because this is the opposite of the integer data type, numbers

formed with float variable declarations will include decimal points,
which implies they must have digits on both sides of a decimal
point. In other words, programmers used the float term before the
name of a variable.
b) Integer
An integer defined as an integer, not a fractional number, can be
positive, negative, or zero. 10, 11, 0, -7, -67 and 5148 are all whole
numbers. An integer should not contain any decimal places.

So, if you add, subtract or multiply two integers, the result will
always be an integer.
c) Character
A character in a data structure represents a character and symbol
such as a, B, f, R, ""., "-" and space. Therefore, it can store the
basic character set. It can hold a letter/symbol like n, F,d.
Characters can also be of different types.
d) Pointer
A pointer represents a memory storage location (RAM). The RAM
contains several cells in which the values are stored. Because each
memory cell is 1 byte in size and the memory address is always an
unsigned integer, each cell has a unique address to identify it.

Example of Non-Primitive Data Structures

S. ARTHEKA DSA PEARSON ID: Page 8 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

a) Arrays
An array is defined as a collection of items stored in adjacent
memory locations. Arrays are also defined as a collection of
homogeneous data items stored in RAM; thus, they can only hold
one sort of data.

Figure 6

Figure 7

Figure 8

b) Lists
A list is defined as a collection of data objects with a variable
number of items. Lists or sequences are abstract data types that

S. ARTHEKA DSA PEARSON ID: Page 9 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

always represent a countable amount of ordered items. Each list

element has at least two fields, one for storing data and the other
for storing the location of the next element.

Figure 9

c) Files
Files contain information, which is permanently kept on the Hard
Disk and Floppy Disk, which is also known as a secondary storage
device. Secondary devices can store both a single byte and a
significant amount of data.

Figure 10

d) Stacks

S. ARTHEKA DSA PEARSON ID: Page 10 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

A stack is a fundamental data structure that is defined as an ordered

collection of elements represented by a physical stack or pile. Liner
data structures have item insertion and deletion at one end known
as the top of the stack.
these are the three basic concepts that can be performed on
stacks.
1. push (insert the items into a stack)
2. Pop (delete an item from the stack)
3. Pip (displaying the content of the stack)

Figure 11

e) Queues
Queue defined (FIFO) First In First Out type of data structure.
Queues are also the part of non-primitive linear data structure, so in
Queues process, we can put an element in a queue from the REAR
end and delete an element from the FRONT end only.
Therefore, implement queues with using two ways:
1. Pointers
2. Arrays

Figure 12

f) Graphs

S. ARTHEKA DSA PEARSON ID: Page 11 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

There are different types of graphs:

1. Connected Graph
2. Non-Connected Graph
3. Directed Graph
4. Non-Directed Graph
g) Trees
Trees are classified as non-primitive and non-linear data structures
in data structure categorization. We can depict a hierarchical
relationship between data components using trees.

Figure 13

c. Explain operations of each classifications

S. ARTHEKA DSA PEARSON ID: Page 12 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

As a result, the most widely used operations are broadly classified into
four classes in the Classification of Data Structure:
1. Create
2. Delete
3. Selection
4. Update
CREATE operation

The CREATE operation (which can be defined) results in memory being

reserved for program elements. A declaration statement can be used to do
this. Data structures can be created either during compile time or during
runtime.

DELETE operation

As a result, the DELETE operation destroys the memory space allocated

for the specified data structure. As a result, the C language functions
malloc () and free () are used for these two operations, respectively.

SELECTION operation

The SELECTION operation is defined as dealing with accessing specific

data within a data structure. The final action, UPDATE, does exactly what
the name implies: it updates or modifies the data in the data structure. As a
result, the operation is classified in the Classification of Data Structures. It
is possible that new data may be input or that previously stored data will
be erased.

As a result, in Data Structure Classification, other procedures done on data

structures include:

a) Searching
b) Sorting
c) Merging

d. List the applications of each classifications

S. ARTHEKA DSA PEARSON ID: Page 13 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

a) Data Storage.
Data structures facilitate efficient data persistence, like specifying attribute
collections and corresponding structures used in database management
systems to store records.
b) Data Exchange.
Organized information, defined by data structures, can be shared between
applications like TCP/IP packets.
c) Resource and Service Management.
Data structures such as linked lists can enable core operating systems
resources and services to perform functions like file directory
management, memory allocation, and processing scheduling queues.
d) Scalability.
Big data applications rely on data structures to manage and allocate data
storage across many distributed storage locations. This function guarantees
scalability and high performance.
7. Select the relevant data structure for the scenario
a. Importance of selecting proper data structure.
b. Justify why you have selected particular data structure or data
structures for the scenario
8. Explain the operations of selected data structure for the given scenario
a. Explanation should relate the operations of the stack with scenario
b. Add suitable pictures
c. Write the algorithm for the operations of selected data structure

9. Memory stack

S. ARTHEKA DSA PEARSON ID: Page 14 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

a. What is memory stack

A stack is a section of memory that stores temporary variables created by a
function. In the stack, variables are declared, stored and initialized at
runtime.
b. Explain operations of a memory stack
i. It allows us to manage data in a Last In First Out (LIFO) manner,
which is not possible with a linked list or array.
ii. When a function is called the local variables are saved in a stack,
and it is automatically deallocated once returned.
iii. When a variable is not used outside of that function, a stack is
used.
iv. It gives you control over how memory is allocated and released.
v. Stack automatically cleans up the object.
vi. It is not easily tainted.
vii. Variables declared only once cannot be resized.
c. Explain how memory stack is used to implement function calls in a
computer
When we compile a program, the compiler enters through the main
function and creates a stack frame on the stack. A structure, sometimes
known as an activation record, is a collection of all data on the stack
connected with a single subprogram call. The main function and all local
variables are saved in an initial frame.

It is a transient storage memory. When the computing work is completed,

the variable's memory is automatically wiped. The stack section primarily
contains methods, local variables, and reference variables.

10. Queue data structure

S. ARTHEKA DSA PEARSON ID: Page 15 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

a. Explain queue data structure with real world example (add picture)
A Queue is defined as a linear data structure that is open at both ends and
the operations are performed in First In First Out (FIFO) order.
FIFO Principle of Queue:
i. A queue is similar to a line of people waiting to buy tickets, with
the first person in line being served. (For example, first come, first
served).
ii. The position of the entry in a queue that is ready to be served, that
is, the first entry that will be removed from the queue, is referred to
as the front of the queue (sometimes, the head of the queue), and
the position of the last entry in the queue, that is, the one most
recently added, is referred to as the rear (or the tail) of the queue.
View the diagram below.
b. Explain the operations of a queue data structure with the picture and
algorithm
1. Enqueue: Adds an item from the back of the queue.
2. Dequeue: Removes an item from the front of the queue.
3. Front/Peek: Returns the value of the item in front of the queue without
dequeuing (removing) the item.
4. IsEmpty: Checks if the queue is empty.
5. IsFull: Checks if the queue is full.
6. Display: Prints all the items in the queue.
Coding

Figure 14

S. ARTHEKA DSA PEARSON ID: Page 16 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

Figure 15

Figure 16

S. ARTHEKA DSA PEARSON ID: Page 17 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

Output

Figure 17

c. Critically review how queue data structure is used to implement

function calls related to the above scenario.
 Include short paragraph to justify why queue data structure is
suitable to implement function calls
 Add picture to show enqueue function that is used to call function
 Add picture to show dequeue function that is used to execute the
function

S. ARTHEKA DSA PEARSON ID: Page 18 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

TASK 02

TASK 03

TASK 04
1. Shortest path algorithm
a. Explain about shortest path algorithm
Given a graph and a source vertex in the graph, find the shortest paths from
the source to all vertices in the given graph.
b. Specify and very briefly explain about types of shortest path algorithm
Shortest path algorithms are classified into two types: single-source and all-
pairs. Both sorts of algorithms function well in their respective ways. Because
of the extra complexity, all-pairs algorithms take longer to run. Even if the
format or form of the return values varies from method to algorithm, all
shortest path algorithms return values that can be utilized to calculate the
shortest path.
I. Single-source
If the goal of the algorithm is to find the shortest path between only
two given vertices, s and t, then the algorithm can simply be stopped
when that shortest path is found. Because there is no way to decide
which vertices to "finish" first, all algorithms that solve for the shortest
path between two given vertices have the same worst-case asymptotic
complexity as single-source shortest path algorithms.

II. All-pairs
The most common algorithm for the all-pairs problem is the floyd-
warshall algorithm.

c. Choose more suitable two shortest path algorithm to visit all the places of
the participants of the car race
I. Clearly explain selected shortest path algorithms with the algorithm
II. Draw sample graph for scenario
III. Analyse the operation, using illustrations, of two shortest path
algorithms (Trace out the shortest path algorithms to find out the
shortest paths for all participants from the ABC Pvt Ltd.)

2. Sorting Algorithm
3. Compare and Contrast both sorting algorithms
4. Analyse the performance of both sorting algorithms through Time and space
complexity of both sorting algorithms. (Discuss about Best, Average and
Worst cases of complexity).

S. ARTHEKA DSA PEARSON ID: Page 19 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

TASK 05
1. Effectiveness of an Algorithm
a) Explain how effectiveness of algorithm measure.
b) Determine two ways in which the efficiency of an algorithm can be
measured, illustrating your answer with an example.
2. Asymptotic Analysis
a) Explain about the Asymptotic Analysis
An algorithm's asymptotic analysis pertains to defining the mathematical
boundation/framing of its run-time performance. We may very well deduce
the best case, average case, and worst case scenarios of an algorithm using
asymptotic analysis.
Usually, the time required by an algorithm falls under three types −
a. Best Case − Minimum time required for program execution.
b. Average Case − Average time required for program execution.
c. Worst Case − Maximum time required for program execution.

b) Explain about the Types of Asymptotic Notations

Following are the commonly used asymptotic notations to calculate the
running time complexity of an algorithm.
a. Ο Notation
b. Ω Notation
c. θ Notation
a) Big Oh Notation, Ο
The notation Ο(n) is a formal way to express an upper bound on the
running time of an algorithm. It measures the worst-case time problem
or the longest time an algorithm takes to complete.

Figure 18

b) Omega Notation, Ω
The Ω(n) notation is a formal way to express a lower bound on the
running time of an algorithm. It measures the best case time problem
or the best time an algorithm can take to complete.

S. ARTHEKA DSA PEARSON ID: Page 20 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

Figure 19

c) Theta Notation, θ
The notation θ(n) is a formal way to express both a lower bound and an
upper bound on the running time of an algorithm.

Figure 20

c) Discuss how asymptotic analysis can be used to assess the effectiveness of

an algorithm

S. ARTHEKA DSA PEARSON ID: Page 21 of 22

 HIGHER NATIONAL DIPLOMA IN
SOFTWARE ENGINEERING

One clumsy approach would be to construct both algorithms and run the two
programs on your computer with different inputs to determine which one takes
less time. There are numerous issues with this method of algorithm analysis.
a. It is possible that the first algorithm outperforms the second for some
inputs. And second performs better for some inputs.
b. It's also possible that the first algorithm works better on one machine for
some inputs, while the second works better on another machine for others.

Asymptotic Analysis is the big idea that deals with the concerns mentioned
above while examining algorithms. In Asymptotic Analysis, we evaluate an
algorithm's performance in terms of input size (rather than real execution
time).

To understand how Asymptotic Analysis handles the aforementioned

challenges in algorithm analysis,

a) let us say:
we run the Linear Search on a fast computer A and
Binary Search on a slow computer B and
pick the constant values for the two computers so that it tells us exactly
how long it takes for the given machine to perform the search in
seconds.
b) Let’s say the constant for A is 0.2 and the constant for B is 1000 which
means that A is 5000 times more powerful than B.
c) For small values of input array size n, the fast computer may take less
time.
d) But, after a certain value of input array size, the Binary Search will
definitely start taking less time compared to the Linear Search even
though the Binary Search is being run on a slow machine.
3. Critically review the sort of trade-offs exists when you use an ADT for
implementing programs
a) What is a trade-off is when specifying an ADT using an example to
support your answer.
b) Explain about types of trade-off in ADT
4. Benefits of using independent data structures for implement a program
a) Explain about the independent data structures
b) Evaluate at least three benefits of using implementation independent
data structures

S. ARTHEKA DSA PEARSON ID: Page 22 of 22