Higher Nationals

Internal verification of assessment decisions – BTEC (RQF)

INTERNAL VERIFICATION – ASSESSMENT DECISIONS
Programme title Higher National Diploma in Computing

Assessor Internal Verifier

Unit 19 – Data Structures and Algorithms
Unit(s)
Specification, Implementation, and Assessment of Data Structures for a
Assignment title sample scenario.

Student’s name
List which assessment criteria Pass Merit Distinction
the Assessor has awarded.

INTERNAL VERIFIER CHECKLIST

Do the assessment criteria awarded match

those shown in the assignment brief?
Y/N
Is the Pass/Merit/Distinction grade awarded
justified by the assessor’s comments on the Y/N
student work?

Has the work been assessed

accurately? Y/N
Is the feedback to the student:
Give details:
• Constructive?
• Linked to relevant assessment criteria?
Y/N
• Identifying opportunities for improved
Y/N
performance? Y/N
• Agreeing actions? Y/N
Does the assessment decision need
amending? Y/N

Assessor signature Date

Internal Verifier signature Date

Programme Leader signature (if required)
Date
 Confirm action completed

Remedial action taken

Give details:

Assessor signature Date

Internal Verifier
signature Date
Programme Leader
signature (if required) Date

Higher Nationals - Summative Assignment Feedback Form

Signature & Date:
 * Please note that grade decisions are provisional. They are only

confirmed once internal and external moderation has taken place and grades decisions have been agreed at the assessment board.

Assignment Feedback
Formative Feedback: Assessor to Student

Action Plan

Summative feedback

Feedback: Student to Assessor

Assessor Date
signature

Student signature Date

Pearson Higher Nationals in
Computing
Unit 19: Data Structures & Algorithms
Assignment 01

General Guidelines

• A Cover page or title page – You should always attach a title page to your assignment.
Use previous page as your cover sheet and make sure all the details are accurately
filled.

• Attach this brief as the first section of your assignment.

 •

All the assignments should be prepared using a word processing software.

• All the assignments should be printed on A4 sized papers. Use single side printing.

• Allow 1” for top, bottom, right margins and 1.25” for the left margin of each page.

Word Processing Rules

• The font size should be 12 point, and should be in the style of Time New Roman.

• Use 1.5 line spacing. Left justify all paragraphs.

• Ensure that all the headings are consistent in terms of the font size and font style.

• Use footer function in the word processor to insert Your Name, Subject, Assignment
No, and Page Number on each page. This is useful if individual sheets become
detached for any reason.

• Use word processing application spell check and grammar check function to help editing
your assignment.

Important Points:

• It is strictly prohibited to use textboxes to add texts in the assignments, except for the
compulsory information. eg: Figures, tables of comparison etc. Adding text boxes in the
body except for the before mentioned compulsory information will result in rejection of
your work.

• Carefully check the hand in date and the instructions given in the assignment. Late
submissions will not be accepted.

• Ensure that you give yourself enough time to complete the assignment by the due date.
• Excuses of any nature will not be accepted for failure to hand in the work on time.

• You must take responsibility for managing your own time effectively.

• If you are unable to hand in your assignment on time and have valid reasons such as
illness, you may apply (in writing) for an extension.
 •

Failure to achieve at least PASS criteria will result in a REFERRAL grade .

• Non-submission of work without valid reasons will lead to an automatic RE FERRAL.

You will then be asked to complete an alternative assignment.

• If you use other people’s work or ideas in your assignment, reference them properly
using HARVARD referencing system to avoid plagiarism. You have to provide both
intext citation and a reference list.

• If you are proven to be guilty of plagiarism or any academic misconduct, your grade
could be reduced to A REFERRAL or at worst you could be expelled from the course

Student Declaration

I hereby, declare that I know what plagiarism entails, namely to use another’s work and to
present it as my own without attributing the sources in the correct form. I further understand
what it means to copy another’s work.

• I know that plagiarism is a punishable offence because it constitutes theft.

• I understand the plagiarism and copying policy of Edexcel UK.
 •

I know what the consequences will be if I plagiarise or copy another’s work in any of the
assignments for this program.
• I declare therefore that all work presented by me for every aspect of my program, will be
my own, and where I have made use of another’s work, I will attribute the source in the
correct way.
• I acknowledge that the attachment of this document signed or not, constitutes a binding
agreement between myself and Pearson, UK.
• I understand that my assignment will not be considered as submitted if this document is
not attached to the assignment.

Student’s Signature: Date:

(Provide E-mail ID) (Provide Submission Date)

Higher National Diploma in Business

Assignment Brief
Student Name /ID Number
Unit Number and Title Unit 19 : Data Structures and Algorithms
Academic Year 2021/22
Unit Tutor
Assignment Title Specification, Implementation, and Assessment of Data Structures
for a sample scenario.
Issue Date
Submission Date
IV Name & Date
 •

Submission format
The submission should be in the form of a report, which contains code snippets (which must
be described well), text-based descriptions, and diagrams where appropriate. References to
external sources of knowledge must be cited (reference list supported by in-text citations)
using the Harvard Referencing style.

Unit Learning Outcomes:

LO1. Examine abstract data types, concrete data structures and algorithms.
LO2. Specify abstract data types and algorithms in a formal notation.
LO3. Implement complex data structures and algorithms.
LO4. Assess the effectiveness of data structures and algorithms.

Assignment Brief and Guidance:

Scenario
ABC Pvt Ltd organizing Car Racing event across western province and they decided to
have maximum of 6 cars(participants) to compete.
There are totally 3 Rounds and at the end of each round lowest rank car will be eliminated
from the Race.
Each car has unique number, brand, sponsor and driver details.

In order to manage this particular event ABC Pvt Ltd decided to develop an Application.
Application functions are listed down.
1.Register Car Details
2.Delete a car
3.Insert 3 Rounds Results.
4.Find out the winners (1st,2nd,3rd)
5.Search for a particular car

Task 1: Examine and create data structure by simulating the above scenario and explain the
valid operations that can be carried out on this data structure.
Determine the operations of a queue and critically review how it is used to implement
function calls related to the above scenario.

Task 2: Implement the above scenario using the selected data structure and its valid
operations for the design specification given in task 1 by using java programming. Use
suitable error handling and Test the application using suitable test cases and illustrate the
system. Provide evidence of the test cases and the test results.

Task 3 : Registered Car details are stored from oldest to newest. Management of ABC Pvt
Ltd should be able to find from the newest to oldest registered car details. Using an
imperative definition, specify the abstract data type for the above scenario and implement
specified ADT using java programming and briefly discuss the complexity of chosen ADT
algorithm. List down the advantages of Encapsulation and Information hiding when using
an ADT selected for the above scenario.
“Imperative ADTs are basis for object orientation.” Discuss the above view stating
whether you agree or not. Justify your answer.

Task 4: ABC Pvt Ltd plans to visit all of these participants through the shortest path within
a day.
Analyse the above operation by using illustrations, of two shortest path algorithms, specify
how it operates using a sample graph diagram. Sort the cars based on numbers with two
different sorting algorithms and critically review the performances of those two algorithms
by comparing them.

Task 5: Evaluate how Asymptotic analysis can be used to assess the effectiveness of an
algorithm and critically evaluate the different ways in which the efficiency of an algorithm
can be measured.

Critically review the sort of trade-offs exists when you use an ADT for implementing
programs. You also need to evaluate the benefits of using independent data structures for
implementing programs.
Grading Rubric

Grading Criteria Achieved Feedback

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.

P2 Determine the operations of a

memory stack and how it is used to
implement function calls in a computer.
M1 Illustrate, with an example, a
concrete data structure for a First In
First out (FIFO) queue.

M2 Compare the performance of two

sorting algorithms.

D1 Analyse the operation, using

illustrations, of two network shortest
path algorithms, providing an example
of each.

LO2. Specify abstract data types and

algorithms in a formal notation.

P3 Using an imperative definition, specify

the abstract data type for a software stack.

M3 Examine the advantages of

encapsulation and information
hiding when using an ADT.

D2 Discuss the view that imperative

ADTs are a basis for object orientation
and, with justification, state whether
you agree.

LO3. Implement complex data

structures and algorithms.
P4 Implement a complex ADT and
algorithm in an
executable programming
language to solve a welldefined
problem.

P5 Implement error handling and report

test results.

M4 Demonstrate how the

implementation of an ADT/algorithm
solves a well-defined problem.

D3 Critically evaluate the complexity of

an implemented ADT/algorithm.

LO4. Assess the effectiveness of data

structures and algorithms.

P6 Discuss how asymptotic analysis can

be used to assess the effectiveness of an
algorithm.

P7 Determine two ways in which the

efficiency of an algorithm can be measured,
illustrating your answer with an example.

M5 Interpret what a trade-off is when

specifying an ADT using an example to
support your answer.

D4 Evaluate three benefits of using

implementation independent data
structures.
 HND in Computing and Systems
Development

1 Task
1.1 Definition of Data structures and Algorithms
A data structure is a method of organizing data in a virtual system. Think of sequences of
numbers or tables of data - both are well-defined data structures. An algorithm is a series
of steps performed by a computer that takes input data and converts it into target output.
Together, data structures and algorithms come together and allow programmers to create
the computer programs they need. An in-depth study of data structures and algorithms
ensures efficient and well-optimized code. (springboard, 2021)
Benefits of using data structure
• The data structure helps to store data efficiently on the storage device.
• Using a data structure provides convenience when retrieving data from a storage
device.
• The data structure enables efficient and efficient processing of small and large
amounts of data.
• Using the correct data structure can help the programmer save a lot of time or
processing time on operations such as storing, retrieving, or processing data.
• Managing large amounts of data can be easily accomplished using a good data
structure approach.
• Most well organized data structures like array, stack, queues, chart, tree, linked list
have a well-structured and pre-planned approach to operations like store, add,
retrieve, manipulate, delete, etc. When using them, the programmer can completely
depend on these data structures.
• Using a data structure can simply promote long-term reuse.
• Data structures like array, linked list, tree, chart, stack, etc. They are well tested
and proven so anyone can use them directly without the need for research and
development. (Tutorials Inhand, 2021)

1.1.1 Types of Data Structure

Basically, data structures fall into two categories:
1. Linear data structure
2. Non-linear data structure
1.1.1.1 Linear data Structure
In linear data structures, elements are arranged sequentially one after another. Since the
elements are arranged in a specific order, they are easy to implement.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 1 of 66
 HND in Computing and Systems
Development

However, as the complexity of the program increases, linear data structures may not be the
best choice due to operational complexity. (programiz, 2021)

1.1.1.1.1 Array Data Structure

In an array, memory elements are organized into contiguous memory. All array elements
are of the same type. And the type of elements that can be stored as arrays is determined
by the programming language.

1.1.1.1.2 Stack data structure

In the data structure of the stack, items are stored according to the LIFO principle. That is,
the last item stored on the stack will be removed first.
It works like a stack of dishes, where the last dish stored in the stack will be removed first.

Basic operations of Stack

Several basic operations allow us to perform various actions on the stack.
Push - Adds an item to the beginning of the stack.
Pop - removes an item from the top of the stack.
Is Empty: check if the stack is empty
Is Full: check if the stack is full
Peek: get the value of the top element without removing it

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 2 of 66
 HND in Computing and Systems
Development

1.1.1.1.3 Queue data structure

Unlike a stack, a queue data structure works on a FIFO basis, where the first item stored in
the queue will be removed first.
It works like a queue of people at the ticket booth, where the first person in line will get
the ticket first.

Linked list data structure

In a linked list data structure, data items are linked through a series of nodes. And each
node contains data items and the address of the next node.

Types of Linked List

The different types of linked lists are shown below.
Simple linked list - items are navigated forward only.
Doubly linked list - items can be moved back and forth.
Circularly linked list - the last element has a link to the first element like the next, and
the first element has a link to the last element as above.

Basic Operations
The basic operations supported by the list are shown below.
Insert: add an item to the beginning of the list.
Delete: removes the item at the beginning of the list.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 3 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 4 of 66
 HND in Computing and Systems
Development

Display: displays the complete list.

Find: Find an item with a certain key.
Delete: deletes an item with the specified key.

1.1.1.2 Non-Linear Data Structure

Unlike linear data structures, the elements of nonlinear data structures are not in any order.
Instead, they are arranged hierarchically, where an item will be associated with one or
more items.
Nonlinear data structures are further classified as graph and tree-based data structures.

1.1.1.2.1 Graph Data Structure

In a graph data structure, each node is called a vertex, and each vertex is connected to
other vertices through edges.

Trees Data Structure

Like a graph, a tree is also a collection of vertices and edges. However, in a tree data
structure, there can only be one edge between two vertices.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 5 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 6 of 66
 HND in Computing and Systems
Development

1.2 Choose a suitable Data structure for given scenario

How appropriate is the data structure of the linked list for this scenario
The linked list is suitable for this scenario because it works in the same way as all of the
system functions listed below; Main functions:
1. Add Car details 2. Delete a car 3. Insert 3 rounds results 4. Find out the
winners 5. Search a particular
ABC Pvt ltd is organizing an automotive event for 6 people and they decide to create an
app for it. In this basic application method, the first thing required to register an auto part
is called sequentially. It can also be used as a queue, nor can it be used as a queue as other
functions cannot use the ones specified here. If we use a Linked List we can do this
however we want. By entering the vehicle data, we can enter more than one vehicle data at
the same time. As an example, please enter the controller network card number as a string,
but we need to enter its age as a whole number. We need to enter different kinds of details
at the same time, then I suggested a possible function: Linked List. The next feature is the
app's Lift Car feature. For this we can use three stacks, queues and Linked List for our
needs. Using the stack function we can remove only the last item from the given list. This
is because this is a first-in, last-out, or last-in, first-out theory, and the order cannot be
used because the general theory is first-in, first-out. This means we can delete the initial
data from the list. So we can use Linked List function to do this, then we can easily
control what we want to do.
Add 3 round results for the next function. We can use the last-in, first-out method of the
stack functions, but the same can be done using the Linked List function here. The next
step is that we want to find the winners and the position as 1, 2 and 3. As mentioned
above, three functions can be used for this, but Linked List is the most convenient
function because other functions cannot do what is required here. The last function will be
Find custom car from the list. We can't use the other 2 builds here because neither of these
2 builds can do what is required. So the most suitable structure for this is the linked list.
Therefore, it is better to choose the linked list for the next function.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 7 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 8 of 66
 HND in Computing and Systems
Development

Operation of the Queue

Enqueue Operation
The queues contain two data pointers, a front and a back. Therefore, their operations are
relatively difficult to implement than stack operations.
To put (insert) data into the queue, you need to perform the following steps:
• Step 1: Check if the queue is full.
• Step 2: If the queue is full, throw an overflow error and exit.
• Step 3: If the queue is not full, increase the back pointer so that it points to the
next empty spot.
• Step 4: Add the item to the position of the back of the queue.
• Step 5: return success.

Dequeue Operation
Accessing the data in a queue is a two-task process: accessing the data pointed to by the
front-end, and deleting the data after access. To carry out the remove queue operation,
follow these steps:
• Step 1: Check if the queue is empty.
• Step 2: If the queue is empty, throw an overflow error and exit.
• Step 3: If the queue is not empty, access the data pointed to by the front-end.
• Step 4: Raise the front pointer to point to the next available data item.
• Step 5: get back on track.

For the above queue operation to be effective, a few more functions are required. These
are:
• Peek (): places the item at the beginning of the queue without removing it.
• Is full (): check if the queue is full.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 9 of 66
 HND in Computing and Systems
Development

• Is empty (): checks if the queue is empty. (tutorialspoint, 2021)

Using these operations for a specific scenario
The necessary functions are given by the scenario, Save car details, delete a car, add 3
round results, Search for winners (1st, 2nd, 3rd) Search for a car while using a single row,
we can use it to create the following system. Queue, Queue, Empty, Full or Watch
functions to access "Add 3-lap car results". This only allows data from those who
complete the first lap at the end of a lap to enter this queue. Find out who the winner is by
showing only the remaining data in the relevant queue at the end of the match using the
Dequeue function. Before using the Save car Details function, we can use the Full
function to check if it is possible to save another person in the queue before entering the
data. When creating the Delete Car and Find a Specific Car functions, we can use the
View function to check if the queue is empty when the Delete Car function is active, or to
determine whether it is an Empty or a new view. Likewise, the event queue list can be
used for a specific scenario as needed.

2 Task
2.1 Car racing system for ABC Pvt Ltd
Below show what system created for ABC private limited. hope to show you the code for
the key components that should be in the system and the test cases to test them. Here
showing the codes and some of the main features that will apply to the system.

 Car registration data  Deleting a Car  Search a Car  Adding the results of
3 rounds and determining the winners (1st, 2nd, 3rd) Codes and Test Case for
Register Car Details
Here are some methods and basic functions in the system for this section and if it is not
possible to create this section correctly1 it will cancel the proposed system. Because the
data we get from this section refers to the last section of the system. "Identification of
winners (1, 2, 3)". Accordingly, if we don't properly create this segment here, ultimately
all the data we get from this system is doomed to be out of core. For this reason, I have
tried to make this section meticulously down to the smallest detail. Below have used two
main strategies for this segment where necessary and would like to independently clarify
what is going on with them. Methods used

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 10 of 66
 HND in Computing and Systems
Development

• Add method
• Add to list method
Add Method
This is done by validating the data provided by the client and sending each information to
the Addtolist method. Similarly, will get all the data about id, make, sponsor, driver name,
driver age and registration date of the currently registered vehicle and then export it to the
Addtolist method.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 11 of 66
 HND in Computing and Systems
Development

Addtolist Method
What I've done using this technique is to add details to this strategy using the Add ()
method above, and then check if it's possible to enter the data into a linked list that
matches the current tool ID. If there is no room in the linked list, the PC screen will show
again that the corresponding client cannot enter additional data into the system.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 12 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 13 of 66
 HND in Computing and Systems
Development

Below are 6 basic linked lists to enter all the data mentioned above. When data is added
to the system with the new tool, the relevant card is included in a separate linked list.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 14 of 66
 HND in Computing and Systems
Development

Test Case for Add Car details

Test Feature Add a car
Testing Car Details Add
Inputs Car Id = C2
Brand = Mitsubishi
Sponsor = ABC PVT LTD
Driver’s First Name = Thilina
Driver’s Last Name= Dhananjaya
Driver’s Age = 28
Expected outcome Successfully add Car Details You Added Details are:
[C2, Mitsubishi, ABC PVT LTD , Thilina,
Dhananjaya,28]
Actual Outcome Successfully add Car Details You Added Details are:
[C2, Mitsubishi, ABC PVT LTD , Thilina,
Dhananjaya,28]
Test successful Yes/No Yes

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 15 of 66
 HND in Computing and Systems
Development

Codes and Test Case for Delete a Car Details

Code for deleting a car

This feature is also an important part of this system. So, in a situation where at any
moment we need to remove unnecessary data related to the car from this system, we need
this section "Delete car". Likewise, I was extremely careful when doing this part in light
of the fact that the key user car key data entered here must be able to be properly
retrieved from this system. Since I entered the vehicle ID here as C1, C2, C3, C4, C5 and
C6, important data should be properly deleted from the system no matter how the
customer enters this ID. I have used a method for this and it takes the car id entered by
the client. The vehicle ID matched to the ID is to remove the vehicle ID from the linked
list containing the current vehicle ID for the race and remove the details from the linked
list created for that vehicle ID.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 16 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 17 of 66
 HND in Computing and Systems
Development

Test Case for Delete a Car details

Test Feature Delete a Car
Testing Car Details Delete
Inputs Car Id = C2
Expected outcome Car details deleted Successfully
Actual Outcome Car details deleted Successfully
Test successful Yes/No Yes

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 18 of 66
 HND in Computing and Systems
Development

Codes and Test Case for Search a Car Details Code for Search a Car
This function is also an important component of this system, allowing users of the
relevant system to search for vehicle data stored in the system at any time. When entering
a Car ID, we need to know the data in this system, the customer will really want to see the
relevant vehicle data stored in this system under a meaningful Car ID. Later, I was more
careful when creating this function. This is because this segment needs to provide the
customer with certain data that is consistent with the Car ID entered by the customer. I
also used a method for this, so when the relevant customer logs in, it shows the vehicle
IDs added to the system and the relevant customer can enter the required Car ID into the
system so that the person can see it.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 19 of 66
 HND in Computing and Systems
Development

Test Case for Delete a Car details

Test Feature Search a Car
Testing Searching a Car details
Inputs Car Id = C1
Expected outcome [C1, Mitsubishi Lancer, ABC PVT LTD, Thilina
Dhananjaya,28]
Actual Outcome [C1, Mitsubishi Lancer, ABC PVT LTD, Thilina
Dhananjaya,28]
Test successful Yes/No Yes

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 20 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 21 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 22 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 23 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 24 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 25 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 26 of 66
 HND in Computing and Systems
Development

Codes And Test Case for Inserting 3 rounds results and finding the winners Code
for Inserting 3 rounds results and finding the winners
This is the main function of this system. Since this is the intended main function of this
system. That is, after we have entered each of the details, this is the technique we will
finally use to select the champions of the car race. Therefore, this function is vital and
special care must be taken in the manufacture of this product. So I've basically used the
technique here, and the client has to enter car 6 details before they can start the game.
Otherwise, I made this part of the system so that it could not be opened. As needed,
entering each of the details and opening this segment, I created the linked list I made
earlier to respectively duplicate the linked list I made above to enter the car ids and car id
of the player who finished that round near the end every confrontation. I planned for it to
be remembered by this system. Then, at this point, he planned the system so that by the
end of the last round, the client could display on the PC screen the identifiers of the cars
of the rivals who took first, second and third place.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 27 of 66
 HND in Computing and Systems
Development

Test Case for Inserting 3 rounds results and finding the winners
Test Feature Find winners
Testing Selecting winners
Inputs Round 1 last car Id = C3
Round 2 last car Id = C1
Round 3 last car Id = C5
Expected outcome Winners Are: [C2, C4, C6]
Actual Outcome Winners Are: [C2, C4, C6]
Test successful Yes/No Yes

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 28 of 66
 HND in Computing and Systems
Development

Error handling techniques used

This technique is important when creating a program. Because we can use error handling
techniques to prevent recurrence of an error that is difficult for us to detect. There are
several error handling methods used in this regard and they are listed below.
• Try
• Catch
• Finally
• Throw
Although there are so many error handling methods, when I created this system, I used
two main methods: try and catch. The following code is a basic example of how I used
these two error handling methods.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 29 of 66
 HND in Computing and Systems
Development

Using codes gives me the ability to use 2 methods to display an error message saying that
once users have to log in, they won't be able to enter letters for the corresponding location

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 30 of 66
 HND in Computing and Systems
Development

if they enter a letter in a number field. The following test case can be used as an example
to display an error message.
Test Case for Error handling techniques
Test Feature Home
Testing Error Handling
Inputs A
Expected outcome Warning...! You Can’t Enter Letters
Actual Outcome Warning...! You Can’t Enter Letters
Test successful Yes/No Yes

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 31 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 32 of 66
 HND in Computing and Systems
Development

3 Task Introduction to Sorting

Sorting means sorting data in ascending or descending order according to some linear
relationship between data items.
Sorting can be done by names, numbers and records. Sorting reduces the number of
searches. For example, searching for a friend's phone number in a phone dictionary is
relatively easy, as the names in the phone book are sorted alphabetically. (Thakur, 2022)
Types of Sorting Insertion sort
In this method, sorting is done by adding items to an existing sorted list. The initially
sorted list contains only one element. Other items are gradually added to the list in the
appropriate place.

Merge Sort
In this method, items are divided into sections until the items in each section are sorted.
These sections are then combined and the items conveniently placed to produce a fully
sorted list.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 33 of 66
 HND in Computing and Systems
Development

Quick Sort
In this method, an element called a pivot is defined, and all smaller elements are shifted to
the left, and all larger elements are shifted to the right, and this element is fixed in place.

Radix Sort
In this method, sorting is done by the number of digits. In this scheme, sorting is done on
the least significant digits first. When all numbers are sorted by most significant digit,
numbers with the same digit in that position but different digits in the least significant
position are already sorted by least significant position.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 34 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 35 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 36 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 37 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 38 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 39 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 40 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 41 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 42 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 43 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 44 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 45 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 46 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 47 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 48 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 49 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 50 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 51 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 52 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 53 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 54 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 55 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 56 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 57 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 58 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 59 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 60 of 66
 HND in Computing and Systems
Development

Heap Sort
In this method, the sorted file is interpreted as a binary tree. An ordered representation of
a binary tree, an array is used to implement heap sorting.
The basic premise for sorting an array is that its elements must start in random order and
be ordered from smallest to largest.
Easy to see list
1, 5, 6, 19, 23, 45, 67, 98, 124, 401
Ordered list
4, 1, 90, 34, 100, 45, 23, 82, 11, 0, 600, 345
No. What makes the latter "messy" is that the adjacent elements are messy. The first
element is greater than the second, not less, just as the third element is greater than the
fourth, and so on. Once this observation has been made, it is easy to design a source that
examines neighboring elements to see if they are okay and replaces them if they are not.
Selection Sort
In this method, the first item is selected and compared to all other items. If the other
element is smaller, the first element must be replaced. At the end of this comparison, the
smallest element is placed at the top of the array. This is known as transition1. II. On pass,
the second item is selected and compared to all other items. The replacement occurs if
there is another element smaller than the selected element. This process continues until
the array is sorted.
The number of passes in the array is compared to the size of the array -1.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 61 of 66
 HND in Computing and Systems
Development

Bubble Sort
This method compares the last element with the previous element. A swap occurs if the
last element is less than the previous element. The previous item is then compared to the
previous item. This process continues until items II and I are compared with each other.
This transition is known as 1.
Therefore, the number of passes will be equal to the size of the array -1. (Thakur, 2022)

Best sorting method for the above scenario

Considering the situation described above, it was extremely difficult to choose the most
reasonable classification method. The reason for this is that when we register each
machine here, we use 6 separate linked lists for each machine, one linked list for each
machine. Then, at this point, the registration dates of these vehicles are entered
independently into 6 linked lists. Consequently, when we sort this 6-linked list, it's
unimaginable to expect us to do everything at the same time, and we need to change this
6-linked list to possibly match the most well-known common sort methods we can use. So
I changed this 6 linked list to a collection sort that allows you to enter any information.
Then, at this point, I sorted the information of these 6 cars by assortment sorting methods,
and with this assortment sorting, I used the collection sorting method. The main reason I
used this collection sorting method is because we need to sort this as a direct result of a
small number of items, like 6 items. Because with this classification method, we can do it
quickly. That is, sorting the 6 linked lists used for sorting won't take much time.
According to this main reason for using the classification, the choice of this classification
was that this classification can certainly quickly apply the appropriate fix. The

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 62 of 66
 HND in Computing and Systems
Development

fundamental reason why this collection classification is so appropriate in this situation is

that we need to classify a small part of the information in this situation. Also, when we
use this classification method, we don't have to write a very long code, so we can run this
system on a PC very quickly while working. This is another reason I chose collection sort
for this sort. In any case, in case I use another sorting method for this, I really want to
complete this task. However, I noticed that the other sort method doesn't make this sort as
fast as sorting a collection. I also realized that if I used another sorting method for this, it
could have a huge impact on system speed due to its long code. So I decide that sorting
the collection is very suitable for this scenario. Below are the codes and test cases for the
sort method I created for this system.
Coding and Test case for sorting method
Here included a list of cars, usually here, and includes important data related to 6 of the
listed listings. The following shows the client entering the number "1" assuming they
want to sort linked list 6 from newest to oldest, or "0" assuming they want to sort from
oldest to oldest and sort and return the linked list 6 based on the number they come in.
How I invented this system.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 63 of 66
 HND in Computing and Systems
Development

Test case for sorting

Test Feature Sorting

Testing Oldest to newest
Inputs 0

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 64 of 66
 HND in Computing and Systems
Development

Expected outcome Car details of order by Oldest to Newest

Car Details [Registered Date=1993, Car
Id=1]
Car Details [Registered Date=1996, Car
Id=2]
Car Details [Registered Date=1996, Car
Id=1] Car Details [Registered Date=1998,
Car Id=3]
Car Details [Registered Date=1998, Car
Id=4] Car Details [Registered Date=2005,
Car Id=5]

Actual Outcome Car details of order by Oldest to Newest

Car Details [Registered Date=1993, Car
Id=1]
Car Details [Registered Date=1996, Car
Id=2]
Car Details [Registered Date=1996, Car
Id=1] Car Details [Registered Date=1998,
Car Id=3]
Car Details [Registered Date=1998, Car
Id=4] Car Details [Registered Date=2005,
Car Id=5]

Test successful Yes/No Yes

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 65 of 66
 HND in Computing and Systems
Development

Test Feature Sorting

Testing Newest to Oldest
Inputs 1
Expected outcome Car details of order by Newest to oldest
Car Details [Registered Date=2005, Car
Id=5]
Car Details [Registered Date=1998, Car
Id=4]
Car Details [Registered Date=1998, Car
Id=3]
Car Details [Registered Date=1996, Car
Id=1]
Car Details [Registered Date=1996, Car
Id=2]
Car Details [Registered Date=1993, Car
Id=1]

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 66 of 66
 HND in Computing and Systems
Development

Actual Outcome Car details of order by Newest to oldest

Car Details [Registered Date=2005, Car
Id=5]
Car Details [Registered Date=1998, Car
Id=4]
Car Details [Registered Date=1998, Car
Id=3]
Car Details [Registered Date=1996, Car
Id=1]
Car Details [Registered Date=1996, Car
Id=2]
Car Details [Registered Date=1993, Car
Id=1]
Test successful Yes/No Yes

Introduction to Abstract Data Type (ADT)

An abstract data type (ADT) is a type (or class) of objects whose behavior is defined by a
set of values and a set of operations.
The ADT definition only mentions what operations will be performed, not how those
operations will be implemented. It does not specify how the data will be organized in
memory and what algorithms will be used to implement the operations. It is called
"abstract" because it offers an implementation-independent representation. The process of
providing only the essentials and hiding the details is known as abstraction.
(geeksforgeeks, 2022)

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 67 of 66
 HND in Computing and Systems
Development

Let us see some of the operations of the mentioned ATDs:

 Stack
Is Full () is used to check if the stack is full.
IsEmpry () is used to check if the stack is empty or not. Push
(x), used to push x onto the stack
Pop () is used to remove an element from the top of the stack.
Peek () is used to get the top element of the stack.
Size (), this function is used to get the number of elements present in the stack.

 Queue
Is Full () is used to check if the queue is full or not.
IsEmpry () is used to check if the queue is empty or not.
Insert(x), used to add x to the tail at the end
Delete () is used to remove an element from the front of the queue.
Size (), this function is used to get the number of elements present in the queue.

 List
Size (), this function is used to get the number of elements present in the list.
Insert(x), this function is used to insert an element into a list
Remove(x), this function is used to remove the given element from the list
Get (i), this function is used to get the element at position i
Replace(x, y), this function is used to replace x with the value of y (Chakraborty, 2019)

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 68 of 66
 HND in Computing and Systems
Development

ADT using in java programming

Abstract data types are data types where you can logically work with a data type, but you
don't know how that data type works. There are many different kinds of abstract data
types in Java. We will talk about them in this article. Just a tip, if you define a data type
with a programming language and then hide its implementation, then it's an abstract data
type. The Java library has abstract data types like list, stack, and queue, set, map as builtin
interfaces which are implemented using various data structures.
In Java, abstract data types extend the collection interface that a data type represents. It is
part of the Java collection system and is the root interface in the collection hierarchy. A
collection is a group of objects, called its elements.
The JDK does not provide any direct implementation of this interface. Provides more
specific sub interface implementations such as List, Set. This interface is typically used
for passing and manipulating collections where maximum versatility is required. But if
we do this with an ADT, we can use a very limited number of variables and store the
relevant data in a single variable until we have the time we need. And using this ADT
allows us to run our program very quickly. This is because we have to use a limited
number of variables and use a very short number of lines of code, so the amount of space
this program takes up in our computer's RAM is very small. Due to this, we can greatly
increase the speed of program execution.
Is the complexity of our program high when use ADT? Or is it low?
By using ADT, we can greatly reduce the complexity of our program. This is because the
number of variables and methods we need to use when creating a program using any ADT
is extremely limited. For example, suppose we get the name, address, and contact number
of several groups and use them for a particular loop. It must be eliminated independently
for each factor. So, at this point, the complexity of our program turns out to be extremely
high. However, if we use an ADT for this, we don't need to store individual coefficients
for each person's data. We can only do the required number of factors per person and add
any relevant individual information to the ADT using the system's while loop, so we don't
have to worry about countless factors. Therefore, I assume that the complexity of the
system when we use ADT That is extremely low.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 69 of 66
 HND in Computing and Systems
Development

Encapsulation
Encapsulation is one of the four core concepts of OOP. The other three are inheritance,
polymorphism, and abstraction.
In Java, encapsulation is a mechanism for combining data (variables) and code that affects
data (methods) as a whole. With encapsulation, class variables will be hidden from other
classes and can only be accessed by methods in your current class. For this reason, it is
also known as data hiding. (tutorialspoint, 2022)

To achieve encapsulation in Java -  Declare

class variables privately.

 Provide global setter and getter methods for modifying and displaying variable
values.

Advantages of Encapsulation
Encapsulation has many uses in everyday programming. Some of its most common uses
include:
• Encapsulation makes programming flexible. Essentially this means you can edit
and update the code for new features.
• This will help you achieve a weak connection.
• Encapsulation simplifies implementation and makes debugging easier.
• You can make changes and edits to your code base without interrupting the normal
operation of your program.
• Allows the programmer to control the accessibility of class data.

Data Hiding
Data hiding is a technique used in object-oriented programming to hide information in
computer code. Objects inside the code do not have access to information that is

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 70 of 66
 HND in Computing and Systems
Development

considered hidden. This has several advantages for programmers, since objects cannot be
associated with irrelevant data, and hackers are less likely to gain access to the data. At
the same time, hiding data can make it difficult for the programmer, who may need to use
more code to create effects on hidden data than would be necessary if the data were
public.
Object-oriented programming is a type of programming in which pieces of code are
broken down into objects. Each of these objects is programmed in capsules, so each
object has its own encoding that applies only to that object. Without specifying the data as
hidden, all the data is exposed to the objects.
Data hiding takes certain parts of the code and hides those parts from objects. Objects
cannot directly access any hidden data. If the object accesses hidden data, it returns an
error. This is because the object cannot see the data, so any features or data marked as
hidden will be invisible to the object. In most cases, hidden data is internal components
that are not needed by the user and can be dangerous if the data is exposed to the user.
The advantage for programmers is that the programmer cannot accidentally refer to
invalid data. Data hiding ensures that if the programmer makes this hook, the program
will simply return an error so that the programmer can quickly fix it. It also ensures that
all objects are truly isolated units, which is the basic concept of object-oriented coding.
Volatile data is usually hidden because if such data were made public, it could corrupt the
object and destroy the entire program.
Another benefit of hiding data is increased protection against hackers. If all the internal
data is public, a hacker can easily break into the internal data and make any changes to
maliciously manipulate the program. By hiding the data, it is much more difficult to break
the code, because the data will appear invisible to the objects and the hacker.
The downside of data hiding is that sometimes programmers have to use extra coding. If a
programmer can bind hidden data, he can make objects run faster or reduce the amount of
code. However, most developers don't keep all the information in the public domain
because of all the problems associated with this type of coding. (Newth, 2022)
Encapsulation and Data hiding being advantage for above scenario

This was definitely the best benefit for me in building the system. The reason is that when
we talk about encapsulation, it is very important when building a system. Because
entering data about a new driver and his car into the system helps a lot. I wasn't able to
enter the data directly into the linked list separately. At first I couldn't get car numbers

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 71 of 66
 HND in Computing and Systems
Development

only through a separate Linked List. The reason why if I entered the drivers data into the
linked list for the first time, at that time it was not possible to enter the Cars ID into a
separate linked list. So I got the relevant data from the main method and included all the
data in the add car function, moving only the car id in that link to another related list. So
the user has no problem accessing the linked list which only contains the car id and has to
use the add car function, so furthermore it can be called encapsulation and the
corresponding code is below.

Detailing the code below, I first wrap the relevant data in a scheduled method such as
Addtolist. The relevant data is then added to a meaningful Linked List. At the same time,
data is added to a Linked List called CarsInRace of an important vehicle ID. This can be
called encapsulation since we can't bind it to this part in the main method itself. The
following are the codes identified using the Addtolist method mentioned above.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 72 of 66
 HND in Computing and Systems
Development

Also, a car race is one of the times used the hide data method in this system. This is
because when the car race starts here, the Linked List included in the car id above is
compiled into another Linked List. This is also the data hiding method used in this
system, since it is not visible to the user at any time. The relevant code is below

Object Oriented Programming

Object-oriented programming combines a group of data attributes with functions or
methods into a unit called an "object". OOP languages are generally class-based, which

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 73 of 66
 HND in Computing and Systems
Development

means that a class defines attributes and data functions as a template for creating objects
that are instances of the class. Popular class-based OOP languages include Java, Python,
and C++. The same class can create or represent multiple independent objects and interact
with each other in complex ways. (Herrity, 2022)
Advantages of Object Oriented Programming Modularity for easy troubleshooting
When working with object-oriented programming languages, you know exactly where to
look when something goes wrong. "Oh, the item in the car is broken? The problem must
be in the class of the car!" You don't have to go through your code line by line. That's the
beauty of encapsulation. Objects are self-contained, with each piece of functionality doing
its job, leaving the other pieces alone. Additionally, this modularity allows the IT team to
work on multiple objects simultaneously, minimizing the possibility of one person
duplicating the functions of another.
Code Reuse by Inheritance
In addition to the Car object, let's say one of your colleagues needs a Racecar object and
the other a Limousine object. They all build their objects separately, but find common
ground among themselves. In fact, each object is just a separate type of car. This is where
inheritance saves time: create a public class (Car) and then define subclasses (Career and
Limousine) that will inherit the properties of the public class.
Of course, Limousine and Race Car still have their own unique qualities and features. If
the Racecar object needs a method for "fire Afterburners" and the Limousine object needs
a Driver, each class can implement separate functions only for itself. However, since both
classes inherit core features of the Car class, such as the "drive" or "fillUpGas" methods,
their derived classes can reuse existing code instead of rewriting these functions. What if
you want to make changes to all Car objects regardless of their type? This is another
advantage of the OOP approach. Modify your car class and all car objects inherit the new
code.

Flexibility through polymorphism

Based on this example, now you only need a few drivers or features like "drive Car",
drive Racecar and "Drive Limousine". Racecar Drivers has some similarities to
Limousine Drivers, but other things like Race Helmets and Beverage Sponsorships are

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 74 of 66
 HND in Computing and Systems
Development

unique. This is where the polymorphism of object-oriented programming comes into play.
Since a single function can change shape no matter what class it is in, you can create a
function named "drive" in the main Car class, not "drive Car" or "driveRaceCar". This
feature is available for Racecar Driver, Limousine Driver etc. will work with In fact, and
it could even be “racecar. Drive (myRaceCarDriver) or limo. Drive (my Chauffeur).
Effective problem solving
Many people avoid learning OOP because the learning curve is steeper than top-down
programming. But take the time to learn object-oriented programming and you will find
that it is the easiest and most intuitive approach to developing large projects.
Object-oriented programming is ultimately about taking a big problem and breaking it
down into manageable chunks. For each mini task you write a class that does what you
need. And best of all, you can make the next problem even faster by reusing these classes.
This does not mean that OOP is the only way to write software. But there is a reason
languages such as C++, C# and Java are preferred for serious software development.
(roberthalf, 2022)
Imperative Data types
The synthesis of imperative programs for hierarchical and algebraically defined abstract
data types is investigated. Two aspects of synthesis are considered: the choice of data
structures for efficient implementation, and the synthesis of related applications for a class
of ADTs that insert and access data without a public key. The methodology is based on the
analysis of the algebraic semantics of ADT. The operators are segmented according to the
behavior of their corresponding operations in the original algebra. A family of relations,
ADT storage relations, is defined. They depend only on the operator side and reflect the
observational view of the ATD. Storage relationships extend to storage graphs: directed
graphs with a designated subset of nodes for efficient access. Data structures in our
command language are chosen according to storage relationships and storage graph
properties. Connected applications are synthesized step by step by applying a given ADT
first with storage graphs and then with associated data structures in an imperative
language.
Some cases in which the resulting programs have a fixed time complexity are discussed.
(st-andrews, 2022)

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 75 of 66
 HND in Computing and Systems
Development

Imperative ADTs are basis for object orientation

Yes, the essence of object oriented programming is procedural data abstraction where
procedures are used to represent data and procedural interfaces provide information
hiding and abstraction. This technique complements ADTs that use concrete algebras to
represent data, and abstraction of types provides information hiding. The two paradigms
can be derived from the basic dichotomy by decoupling a set of observers and
constructors that define abstract data. CCP divides this array into constructors: each
constructor has a class associated with it, and observations become attributes or methods
of instances of the class. Indeed, values in abstraction are nothing more than a collection
of legal statements about them. ADTs, on the other hand, decompose a sequence into
observations: each observation is an operation defined in an abstract type that includes
constructors as representation options.
This is because mandatory ADTs are fundamental to object orientation. This is because
ADT is one of the main components of object orientation.
Here the ADT is doing the work that we do inside the system, from the outside
perspective of the system that the meetings cannot perceive. Take, for example, our
system. In other words, all the food we take into our mouth is processed by the stomach
system, but we do not see it. This also applies to abstraction. That is, regardless of
whether we enter information by one method, its interaction occurs in another method.
So, whether or not we consider object orientation, such a loop exists. Thus, the
importance of these mandatory ADTs for object orientation can be clearly stated. In
addition, one of the mandatory elements of ADT is to limit the complexity of the code we
create and maintain the quality and speed of the system. Therefore, we treat this ability as
the fundamental ability of the matter aspect. This is due to the fact that the system we are
creating can be divided into separate elements in order to eliminate the complexity of our
system and unnecessary lines of code. Then at this moment there will be no problems
with the speed and adequacy of our system. This is because the meaningless system string
size has been omitted. Thus, these components involve the use of object orientation with
ADTs, which can lead to a clear conclusion that Mandatory ADTs are starting to direct the
package for object orientation and that ADTs are the foundation of object orientations. 4
Task Algorithm used to find the shortest path Introduction to Graph

Simply put, graphs are data structures that are used to represent the links between a pair of
elements, where these elements are called nodes (or vertices), which are usually real-time

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 76 of 66
 HND in Computing and Systems
Development

objects, people, or entities, and the links between nodes are called edges. Also, two nodes
are connected only if there is an edge between them.
“A graph is essentially a relationship of nodes/vertices connected by edges.”
Typically, graphics are suitable for real-life applications such as graphics that can be used
to illustrate a transportation system/network where nodes represent objects that transmit
or receive products and edges represent routes or subways connecting nodes.
The diagrams can be divided into two parts;
Undirected graphs: For every pair of connected nodes, if a person can move from one
node to another in both directions, then the graph is called an undirected graph. Directed
graphs: For every pair of connected graphs, if a person can move from one node to
another in a certain (unique) direction, then the graph is called a directed graph. In this
case, instead of simple lines, arrows are used to indicate directed edges.
Weighted graph
Weight charts are charts where the edges of the chart have a "weight" or "cost" and also
where the weight can reflect distance, time, money, or anything else that shows an
"association" between the pair of nodes it links. These weights are an important element
of Dijkstra's algorithm. (Tyagi, 2022)
Dijkstras algorithm
Dijkstra's algorithm uses breadth-first search (which is not a single source shortest path
algorithm) to solve the single source problem. Impose a restriction on the graph: there
cannot be edges with a negative weight. However, due to this single limitation, Dijkstra
significantly improves Bellman-Ford's run time.
Dijkstra's algorithm is also sometimes used to solve the shortest path problem for all pairs
by simply running it on all vertices in a VV. Again, this requires that all edge weights be
positive.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 77 of 66
 HND in Computing and Systems
Development

Graph to find the shortest path for above scenario

S1 S2 S3 S4 S5 S6

S1 0 ∞ ∞ ∞ ∞ ∞

S2 0 6 ∞ ∞ 4 2

S3 0 6 ∞ ∞ 4 2

S4 0 6 7 8 4 2

S5 0 6 7 8 4 2

S6 0 6 7 8 4 2

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 78 of 66
 HND in Computing and Systems
Development

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 79 of 66
 HND in Computing and Systems
Development

5 Task Asymptotic analysis

Asymptotic analysis of an algorithm refers to determining the mathematical limit/basis of
its performance at runtime. Using asymptotic analysis, we can very well determine the
best case, average case, and worst case of an algorithm.
Asymptotic analysis is input-bound, that is, if there is no input to the algorithm, it is
concluded that it runs in constant time. Other than "input", all other factors are assumed to
be constant.
Asymptotic analysis refers to the calculation of the execution time of any operation in
mathematical units of calculation. For example, the execution time of an operation is
calculated as f(n), and for another operation it can be calculated as g(n2). This means that
the execution time of the first operation will increase linearly as n increases, while the
execution time of the second operation will increase exponentially as n increases.
Similarly, the execution time of both operations will be almost the same if n is
significantly small.
Generally, the time required by the algorithm is divided into three types.
• Best Case – Minimum time required for program execution.
• Average Case – Average time required for program execution.
• Worst Case – Maximum time required for program execution. (tutorialspoint,
2022)
Asymptotic Notations
The following are the asymptotic notations commonly used to compute the running time
complexity of an algorithm.
• Ο Notation  Ω Notation

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 80 of 66
 HND in Computing and Systems
Development

• θ Notation
Big oh Notation (O)
The notation Ο (n) is a formal way of expressing an upper limit on the execution time of
an algorithm. It measures the worst case time complexity, or the maximum time an
algorithm can take to complete.

Omega Notation (Ω)

The Ω (n) notation is a formal way of expressing a lower bound on the execution time of
an algorithm. It measures best-case time complexity, or the best amount of time an
algorithm can take to complete.

Theta notation, θ
The notation θ (n) is a formal way of expressing both the lower and upper bounds on the
execution time of an algorithm. It is presented as follows:

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 81 of 66
 HND in Computing and Systems
Development

Analyzing the Performance of a Program

Program performance analysis Performance analysis is a technique for examining or
comparing the performance of a particular situation as opposed to the goal and at the
same time being executed. In HR, performance analysis can help evaluate an employee's
contribution to an assigned project or task.
Importance of Performance Analysis
Importance-Performance Analysis (IPA) is an established method of measuring service
quality, well known for its simplicity and ease of use. In this way, IPA focuses on the gap
between the customer's expectations of importance and the performance judgment of a
particular attribute of the service being consumed.
We distinguish three main steps in the performance analysis process: data collection, data
transformation, and data visualization. Data collection is the process by which we obtain
program performance data from the executable program. The data is collected in a file
during or after execution, although in these situations it is presented to the user in real
time.
Therefore, programmers always focus on the average case.
Average Performance of a Program
Worst and best case execution times are used for completely unexpected purposes
compared to the average case execution. For advancement in programming, the average
execution is used. Information about the average execution of cases is especially
applicable when writing program blocks rather than the entire program. The average case
behavior can be used to identify areas of interest caused by bad algorithms, bad codes,
poor choice of guide, or other variables.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 82 of 66
 HND in Computing and Systems
Development

In most cases, we are not interested in the best situation, since it happens only
occasionally, and usually we rely too much on a meaningful estimate of the algorithm's
execution time. In other words, research focused on the best situation is probably
irrelevant to the behavior of the algorithm. There are, all things considered, a couple of
events for which best case analysis is appropriate.
Most worst-case analyzes may not be part of the algorithm mapping agent, especially
when we want to summarize the cost of running a program normally on various different
data sources. Usually we want to know the worst case execution time imaginable. This
means that we would rather know what the average behavior of the algorithm is. To
perform an average case analysis, we must first decide how the program's actual sources
of information are distributed versus the distribution of all possible information.
In the average scenario, we take the average number of executions for all possible
combinations of information. The execution time serves as a lower and upper bound on
the transition complexity of the algorithm in this situation. In short, the lower the time
complexity of an algorithm, the faster it will get the job done in practice. When working
with or using algorithms, you need to keep this in mind, as it can make a significant
difference between a useful calculation and a completely useless one.
Trade-offs
The best algorithm, and therefore the best program for solving a given problem, is the one
that requires the least amount of memory and takes the least amount of time to execute its
instruction or generate output. But in practice, it is not always possible to achieve both
goals. As stated above, there can be more than one approach to solving the same problem.
One of these approaches may require more space but take less time. So we may have to
sacrifice one at the expense of the other. That is, we can say that there is a space-time
exchange between the algorithms.
Therefore, if space is our constraint, we should choose a program that requires less space
at the cost of more execution time. Also, if time is our constraint, then we should choose a
program that takes less time to complete the execution of statements at the expense of
more memory.
When analyzing algorithms, we are interested in the average case, the amount of time the
program is expected to take on typical inputs, and in the worst case, the total time
required by the program or algorithm. Here would take the worst possible inputs of this
algorithm.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 83 of 66
 HND in Computing and Systems
Development

Types of Trade-offs Lookup tables Vs Recalculation

An algorithm involving a lookup table is an implementation can include the entire table,
which reduces computing time, but increases the amount of memory needed, or it can
compute table entries as needed, increasing computing time, but reducing memory
requirements.
Compressed Vs Un compressed data
The data storage problem can also be solved using space-time compensation algorithms.
If the data is stored uncompressed, it takes up more space, but it takes less time to access
it than if the data is stored compressed (because data compression reduces the amount of
space it takes up, but the decompression algorithm takes time). to run). It depends on the
particular instance of the problem, it's handy anyway. There are also rare cases where it is
possible to work directly with compressed data, for example in the case of compressed
bitmap indexes, when working with compression is faster than without compression.
Re Rendering Vs Stored images
In this case, keeping only the SVG source of the vector image and rendering it as a bitmap
each time the page is requested would mean trading time for space; used more time but
less space. Rendering an image on page change and saving the rendered images would
mean trading space for time; uses more space but less time. This technique is more
commonly known as caching.
Smaller code Vs loop unrolling
This technique is typically used to increase the length of the code for each iteration of the
loop, but saves the computation time required to return to the beginning of the loop at the
end of each iteration. The larger code size can be traded for faster program speed when
loop unwinding is applied. Others types are:
• Add and store data
• Access data
• Remove data
• It works as specified
• It is easy to understand and modify
• It is reasonably efficient
• Implementations of ADTs can be changed (e.g., for efficiency) without requiring
changes to the program that uses the ADTs

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 84 of 66
 HND in Computing and Systems
Development

• ADTs can be reused in future programs

Benefits of using independent data structures for implementation program
Representation Independence
One of the goals of type checking in programming languages is to provide a certain
degree of "representation independence": programs should not depend on the way stacks
are represented, but only on the behavior of stacks with respect to push and pop
operations. In languages with abstract data type declarations, representation independence
must be preserved for both user-defined types and built-in types. We study representation
independence properties of a typed functional language (second-order lambda calculus)
with polymorphic functions and abstract data type declarations where data type
implementations (packages) can be passed as function parameters and returned as results.
Modularity
A basic programming rule is that a subroutine should never exceed the size of the page.
This is achieved by dividing the program into modules. Each module is a logical unit and
can perform a specific job. ADT can be seen as a modular design.
Interchangeability of Parts
Different implementations of an abstract data type may have different performance
characteristics. It becomes easier for each program component to use the implementation
of its data types that is most efficient for the part of the program that uses the abstract data
types.
Data structure that changes over time
As a dynamic data structure, a linked list can grow and shrink at runtime through memory
allocation and deallocation. As a result, there is no need to specify the initial size of the
linked list. As for the scenario, if it is necessary to increase the number of participants in
the event, then there will be no problem.
Deletion and insertion
Inserting and deleting at the beginning or end of a linked list is one operation. Insertion
and deletion in the middle may involve iterating forward or backward from the end to n-1
nodes, but this is usually more efficient than insertion and deletion in an array because
you need to move all elements to the right of the insertion. Forward or left for the kill.
The script needs to remove a vehicle from any position, so using linked lists made it
possible.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 85 of 66
 HND in Computing and Systems
Development

No Memory Wastage
Efficient memory usage can be achieved in a linked list because the size of the linked list
grows or shrinks at run time, so there is no memory wastage and no need to pre-allocate
memory. Implementation
Linear data structures such as stacks and queues are often easily implemented using a
linked list.

S. Pakeen Data Structure & Algorithm Pearson No: Fill here Page 86 of 66