Higher Nationals

Internal verification of assessment decisions – BTEC (RQF)

INTERNAL VERIFICATION – ASSESSMENT DECISIONS

Programme title Higher National Diploma in Computing

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

H.K. Thimira Maneth 00078123

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 Y/N
improved 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 Date
signature
Programme
Leader Date
signature (if
required)

Higher Nationals - Summative Assignment Feedback Form

Student Name/ID H.K. Thimira Maneth 00078123
Unit 19: Data Structures and Algorithms
Unit Title
Assignment Number 1 Assessor Miss Jaksa

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 2
 Date Received
1st submission
Submission Date
Date Received 2nd
Re-submission Date submission
Assessor Feedback:
LO1 Examine different concrete data structures and it’s valid operations.
Pass, Merit & P1 P2 M1 M2 D1
Distinction Descripts

LO2 Discuss the advantages, complexity of Abstract Data Type and importance concepts of
Object orientation.

Pass, Merit & P3 M3 D2

Distinction Descripts

LO3 Implement, Demonstrate and evaluate complex ADT algorithm.

Pass, Merit & P4 P5 M4 D3

Distinction Descripts

LO4 Examine the advantages of Independent data structures and discuss the need of
asymptotic analysis to assess the effectiveness of an algorithm.
Pass, Merit & P6 P7 M5 D4
Distinction Descripts

Grade: Assessor Signature: Date:

Resubmission Feedback:

Grade: Assessor Signature: Date:

Internal Verifier’s Comments:
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

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 3
 Summative feedback

Feedback: Student to Assessor

Assessor Date
signature

Student Date
signature

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 4
 Pearson Higher
Nationals in
Computing
Unit 19: Data Structures & Algorithms
Assignment 01

H.K. Thimira Maneth

00078123

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 5
 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.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 6
 • 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 in-
text 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.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 7
 • 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.

E001152@esoft.academy
Student’s Signature: Date:
(Provide E-mail ID) (Provide Submission Date)

Higher National Diploma in Business

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

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 8
 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.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 9
 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

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 10
 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.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 11
 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

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 12
 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 well-defined problem.

P5 Implement error handling

and report test results.

M4 Demonstrate how the

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 13
 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.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 14
 Contents
Task 1...............................................................................................................................................5
Examine and create the data structure.............................................................................................5
valid operations and functions in the car racing event................................................................5
Queue Data Structure...................................................................................................................7
Applications of Queue.............................................................................................................8
Dequeue()..............................................................................................................................12
Task 2.............................................................................................................................................13
Implement the above scenario using the selected data structure...............................................13
Register Car details................................................................................................................13
Delete a car............................................................................................................................13
Insert three rounds of the car.................................................................................................13
Find out the winners..............................................................................................................14
Search for a particular car......................................................................................................14
Implementation of the scenario in Java programming..............................................................14
Register Car details................................................................................................................19
Display Car Information........................................................................................................23
Search Car..............................................................................................................................24
Delete Car..............................................................................................................................25
Car Update.............................................................................................................................26
Enter Results Of 3 Rounds....................................................................................................28
Find the Winners Of Race.....................................................................................................30
Introduction to error handle.......................................................................................................31
Syntax error...........................................................................................................................31
Runtime errors.......................................................................................................................31
Logic errors............................................................................................................................31
Suitable error handling for the system.......................................................................................32
Test Cases of ABC Car race event Application.........................................................................33
Task 3.............................................................................................................................................40
Registered Car details are stored from oldest to newest............................................................40
complexity for queue algorithms...............................................................................................41
Introduction to ADT..................................................................................................................42

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 15
 List ADT.....................................................................................42
Stack ADT..................................................................................42
Queue ADT............................................................................................................................43
Benefits of ADT....................................................................................................................43
Encapsulation.............................................................................................................................44
Encapsulation benefits include:.............................................................................................44
Use of Encapsulation for the scenario...................................................................................44
Task 4:...........................................................................................................................................46
shortest path algorithms.............................................................................................................46
Examples for shortest path algorithms......................................................................................46
Nature of a graph...................................................................................................................47
shortest path algorithms chosen for scenario's...........................................................................48
The Dijkstra Algorithm..........................................................................................................48
Algorithm Kruskal.................................................................................................................50
Introduction to sorting algorithms.............................................................................................51
Describe the sorting algorithm...............................................................................................51
Selection sort.........................................................................................................................52
Bubble sort algorithm............................................................................................................53
Comparison the performance of two sorting algorithms.......................................................54
The effectiveness of an algorithm...........................................................................................54
Space complexity...................................................................................................................55
Time complexity....................................................................................................................55
Task 5:...........................................................................................................................................55
Asymptotic analysis is what?.....................................................................................................55
Big-O Notation..........................................................................................................................57
Omega notation..........................................................................................................................58
Theta notation............................................................................................................................58
Types of trade off for ADT implement in programming...........................................................59
Introduction to the Independent data structure..........................................................................60
Independent Data Structure...................................................................................................60
Benefits of independent data structure.................................................................61References
...............................................................................................................................................62

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 16
 Task 1
Examine and create the data structure
Our scenario situation is based on a ABC Pvt Ltd organising race across a western province. For
this racing event, ABC PVT Ltd made the decision to create an application to manage this. The
company provides the functionality needed for the application. We must comprehend each
function's demand and construct it in accordance with the directions given. Finding the race
winners is this application's primary goal. Through our application, five functions must be
performed.
valid operations and functions in the car racing event
We each have five functions to perform.
1. Register Car Details - The operation requires entering car information into an array. Six cars
are reportedly taking part in the competition. Six cars should so be able to enter the variety.
Details about the driver, brand, sponsor and unique car number are required. Data should be
directly entered into the array using this function.
2. Delete a car - Any car in the array could be removed. A car should be able to be deleted from
the arrays based on its variables or array using this method. This procedure must remove a car
from the array.
3. Insert 3 Rounds of Results - The last-placed car in the race must be immediately removed
from the race, and the user should be able to enter the results from the three rounds so that there
would be three winners after the three races. This procedure must remove one vehicle from each
round while keeping the last three cars.
4. Find out the winners (1st,2nd,3rd) - The final three race winners ought to be able to be seen in
this. As the remaining cars from the previous round results, this function should provide the last
three race winners.
5. Search for a particular car - This has to search for a car from the array list. We could use
binary or linear search to fulfil this operation. This should be able to find the car we are seeing
for and its details.

Overall, our application will be used to perform all of these functions. Here, we have the choice
of choosing our own data structure. In order to continue the data structure, I would compare the
stack and queue data structures. To accomplish these requirements.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 17
 One of the most well-liked data structures
among developers is the stack. A collection of
things are stored in this linear data structure. It adheres to the special Last-in-First-Out (LIFO) or
FILO(First In Last Out). Technique. Specific actions are made available to us so that we can
handle a stack.
 Push()- to add a component to the stack

 pop() -to eliminate a stack element

 top() -The top item of the stack is returned top().

 isEmpty()- produces True if the stack is empty; otherwise, false

 size()- provides the stack's size.

These are the essential building blocks of the stack data structure. As previously demonstrated,
applying these techniques is simple and might be used if the case corresponds to the needs of the
stack data structure.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 18
 Queue Data Structure

A queue is described as a linear data structure with open ends and FIFO (First In, First Out)
execution of operations.
A queue is a list in which all additions are made at one end, and all deletions are made at the
other. The operation is started on the element that is pushed into the order first.
Queues have the ability to accommodate numerous data. Having access to both ends ,They are
swift and adaptable.

Queues can be expressed as an array just like stacks: The array is used to implement the Queue
in this representation. The variables in this scenario are

Enqueue: Adds a piece of content to the queue. An overflow condition is referred to as the queue
is full.

Dequeue: Takes something out of the queue. In the same sequence that they are pushed, the
things are popped. An underflow condition is stated to exist if the queue is empty.

Front: Take the first thing in the queue.

Rear: Get the last item from queue.

Basic Queue Operations:

front(): This function just returns the item at the front of the document.

rear(): Without deleting it, this action returns the item at the back of the list.

isEmpty(): returns a boolean value indicating whether or not the queue is empty.

isFull() : If the queue is full or not, the isFull() method returns a boolean value.

Enqueue() :Adds (or stores) a new element at the end of the queue using the method.

Dequeue(): Takes the first element out of the queue or gives access to it.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 19
 Applications of Queue
Queue is used when objects need to be handled
in First InFirst Out sequence, such Breadth First Search, rather than immediately. This feature of
the queue also makes it handy in the following kinds of situations.
 when numerous users share a same resource. CPU scheduling and disk scheduling are

two examples.

 when information is exchanged between processes asynchronously (information is not

always received at the same pace as it is sent). Examples include pipelines and IO

Buffers.

 Use on WhatsApp The WhatsApp server queues up our messages for delivery to friends

who are offline or without an internet connection.

 utilized as waiting times for a single shared resource, such as a printer, disk, or CPU.

 used as buffers in portable CD players and MP3 devices.

 Operating system has been modified to accommodate the interruption.

 Applied to playing from the front or adding a song at the end.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 20
 FIFO Principle of Queue:

The first person in line is serviced first (FIFO) in a queue, which is similar to a line waiting to
buy tickets. (First come, first served, etc.)
The front of the queue (or head of the queue) refers to the position of the entry in a line that is
ready to be serviced or the first one that will be taken out of the line. The rear (or tail) of the
queue, on the other hand, refers to the position of the entry that was most recently added. See the
image below.

Array Representation
import java.*;
class GF {

// A structure to represent a queue

static class Queue{
int front, rear, size;
int cap;
int arr[];
}

// Function to create a queue of given capacity

// It initializes size of queue as 0
Queue createQueue(int cap)
{
Queue queue = new Queue();
queue.cap = cap;
queue.front = 0;
queue.size = 0;

queue.rear = cap - 1;
queue.arr = new int[queue.cap];
return queue;
}
}

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 21
 Enqueue()

Step 1: Check if the queue is full.

Step 2: If the queue is full, return overflow error and exit.
Step 3: If the queue is not full, increment the rear pointer to point to the next empty space.
Step 4: Add the data element to the queue location, where the rear is pointing.
Step 5: return success.

Ex
void queueEnqueue(int data)
{
// Check queue is full or not
if (capacity == rear) {
System.out.println("\nQueue is full\n");
return;
}

// Insert element at the rear

else {
queue[rear] = data;
rear++;
}
return;
}

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 22
 Algorithm for enqueue operation
procedure enqueue(data)

if queue is full
return overflow
endif

rear ← rear + 1
queue[rear] ← data
return true

end procedure

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 23
Dequeue()

Step 1: Check if the queue is empty.

Step 2: If the queue is empty, return the underflow error and exit.
Step 3: If the queue is not empty, access the data where the front is pointing.
Step 4: Increment the front pointer to point to the next available data element.
Step 5: The Return success

void queueDequeue()
{
// If queue is empty
if (front == rear) {
System.out.println("\nQueue is empty\n");
return;
}

else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}

// decrement rear
rear--;
}
return;
}

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 24
 Algorithm for dequeue operation

procedure dequeue

if queue is empty
return underflow
end if

data = queue[front]
front ← front + 1
return true

end procedure

Task 2
Implement the above scenario using the selected data structure
Practice the higher scenario using the chosen data framework and its essential functions for the
initial setup mentioned in mission one—Using a genuine error to take care of when necessary
Investigate the program's use of the necessary experiments to depict the structure. Provide
evidence of the effectiveness of the analysis as well as the experiments. As was stated in Task 1,
As we have seen what operations and functions are included in the Queue data structure, we can
apply those concepts to our scenario and see whether it's the proper data structure to follow. To
check on the vitality of the data structure, I would use all the functions that are to be done in the
scenario and compare them with the functions and operations in the queue data structure.
Register Car details
The scenario's initial operation is this. Six more cars will soon be added to the line-up. A regular
array or a linked list array can be used for this. Because it sticks to a particular manner known as
FIFO, if we use this, we won't be able to use the same array to take the positions of the cars. As a
result, this array would function independently, and the data would be transferred to another
display via cloning or another mechanism.
Delete a car
A search algorithm method could be used to delete a car with ease. The program will locate the
entire array for the number and then delete it appropriately if a distinctive component of the
vehicle, such as its number, is added.
Insert three rounds of the car
We must reverse the queue method's functionality because the queue data structure employs the
FIFO approach. Because the last individual will be the first to go, the ranking for the car race
works. Thus, the algorithm will have to function since the last person standing will be the first to
perish. Insert three rounds of the car. The add (Enqueue) operation will function the same way as

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 25
 adding entries to an array. This will include
each of the array's six elements. The final
element placed into the array must then be removed using the delete method. Simple solutions
like inserting the items in decreasing order can be used to accomplish this. By doing this, we
could quickly push out the last entry in the list (Dequeue). Each time an element is entered last
and gets put out, this will happen three times. The final three will be declared the winners.
Find out the winners.
The results of the preceding array made it simple to determine who won the race. As a result, the
algorithm will only be able to display the final array of effects. The first, second, and third places
of the race might also be displayed using the peak operation.

Search for a particular car

To find a specific car the customer wants to see, we might use the starting array (the array we
used to register the car) in this function. There are other ways to carry out this search, including
linear search, binary search, etc. The finished product will display the car, the index, and the
required data.

Overall, this is how we could use a queue structure to implement the data structure in the
situation. This is one method of making this data structure. The explanation above provides a
critical analysis of the roles played by queue operations and illustrates how they would perform
in the given circumstance.
Implementation of the scenario in Java programming
As we can see from the job above, we talked about several data structures and the application's
architectural structure in relation to the situation. I had to research several Java array-related
topics and functions in order to build this application.
After giving it some thought, I began to create the application that ABC PVT LTD needed for
their special race. This is the code I
package Assignment1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Scanner;

public class Car_Race {

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 26
 public static void main(String[] args) {
Scanner S = new Scanner(System.in);
Scanner S1 = new Scanner(System.in);
int ch ;
Info[] CA =new Info [6];
String[] win = new String[6];

boolean empty = true;

List <Info> c = new ArrayList<Info>();

do {
System.out.println("car Race");
System.out.println("*****************");
System.out.println("1.Register car ");
System.out.println("2.Display all car ");
System.out.println("3.Search car ");
System.out.println("4.Delete Car");
System.out.println("5.Update Car");
System.out.println("6.Enter Results of 3 rounds ");
System.out.println("7. Find the Winners");
System.out.println("*****************");

System.out.println("Enter Your Choice:");

ch = S.nextInt();

switch(ch) {
case 1:
System.out.println("Enter Car ID : ");
int carId = S.nextInt();
System.out.println("Enter Brand : ");
String brand = S1.nextLine();
System.out.println("Enter sponcer : ");
String sponser = S1.nextLine();
System.out.println("Enter drivername : ");
String drivername = S1.nextLine();

c.add (new Info (carId,brand,sponser,drivername));

break;
case 2:
System.out.println("_________________");
Iterator<Info> i = c.iterator();
while(i.hasNext()) {
Info e = i.next();

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 27
 System.out.println(e);
}
System.out.println("_________________");
break;
case 3:
boolean found = false;
System.out.println("Enter Car ID To Search :");
carId = S.nextInt();
i = c.iterator();
while(i.hasNext()) {
Info e = i.next();
if (e.getCarid()== carId)
System.out.println(e);
found = true;
}

if (!found ) {
System.out.println("Record not Found ");

}
System.out.println("_________________");
break;

case 4:
found = false;
System.out.println("Enter Car Id To Delete :");
carId = S.nextInt();
System.out.println("_________________");
i = c.iterator();
while(i.hasNext()) {
Info e = i.next();
if (e.getCarid()== carId)
i.remove();
found = true;
}

if (!found ) {
System.out.println("Record not Found ");

}else {
System.out.println("Record is Deleted ");
}
System.out.println("_________________");
break;

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 28
 case 5:
found = false;
System.out.println("Enter Car ID To Update :");
carId = S.nextInt();
System.out.println("_________________");
ListIterator<Info>li = c.listIterator();
while(li.hasNext()) {
Info e = li.next();
if (e.getCarid()== carId)
System.out.println("Enter New Brand : ");
brand = S1.nextLine();

System.out.println("Enter New Sponcer : ");

sponser = S1.nextLine();

System.out.println("Enter New Drivername : ");

drivername = S1.nextLine();

li.set(new Info(carId,brand,sponser,drivername) );

found = true;
}

if (!found ) {
System.out.println("Record not Found ");

}else {
System.out.println("Record is Updated ");
}
System.out.println("_________________");
break;
case 6:
int round =0;
int abc = 6;
while(round<3) {
round = round + 1;
Scanner ab = new Scanner(System.in);
System.out.println("Enter Results Of Round" + round);

int places = 0;
int element = 0;

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 29
 while(places <
abc && element < abc) {
places=places+1;
Scanner sc = new Scanner(System.in);
System.out.println(places + "place");
String pos = sc.nextLine();
win[element]=pos;
element = element + 1;

}
int reduce = win.length - round;
win[reduce]= null;
System.out.println(Arrays.toString(win));
abc = abc + 1;
}

System.out.println("_________________");
break;
case 7:
for (String Car: win) {
if(Car != null) {
empty = false;
break;

}
if (empty) {
System.out.println("Enter Three Rounds Results");

}
else {
System.out.println("First Place goes to Competitor
number:" + win[0]);
System.out.println("Second Place goes to Competitor
number:" + win[1]);
System.out.println("Third Place goes to Competitor
number:" + win[2]);

}
}

}while(ch != 0);}}

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 30
 For better comprehension and clarification, I
would like to divide my program into smaller
functions as indicated in the scenario.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 31
 Register Car details
This is the developer's very first obstacle to
overcome. I was able to research various array types and choose the one that was best
appropriate for this operation. There were other options, including linked lists, regular arrays
with basic data types, etc.
I made the decision to enter the car's information into an array of objects for clarity and
preference. In an array of objects, the array is initially introduced with the object name rather
than a data type. This enables us to save the data in several object names rather than storing it all
in a single array index.

I made an array of objects to enter the information about the cars in our scenario. This is how it
will be kept in the array. I've kept the car information in the array at index [0]. On the following
few indexes, 5 more vehicles of this type are present.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 32
The Following code And Output show the menu of our application.

This is the code for the main menu for the application
The application's main menu is contained within a while loop. It will continue to run until the
user closes the software.

When the application is launched, the user is presented with this UI for the very first time. The
user will then need to register the vehicles.
Users enter their selections using numbers. Therefore, the user must enter number 1 in the menu
if they want to register an automobile.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 33
How the author generated an object of array to store the car details is demonstrated in the figure
above.
I was able to insert user data into the array object by doing this. This is basically how I set up my
register information operation in this application. The user input interface for autos is depicte.
The code for adding data to the array may be seen in the image up top. Here, I've used a
straightforward if statement to determine whether the input is a one . Then, after using the
scanner to collect user input, I used the print command to provide some instructions.
Also I make a Collection to collect input user given.

This allowed user to insert user data into the object of the array.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 34
Overall, I created my register Car details operation for this application in the manner described
above. The interface for user input in Cars is depicted in the graphic below.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 35
 Display Car Information
I provide the users with this extra function in
case they need to double-check the information they have entered into the array. The code and
output for the ensuing operation are given below.

I have used Iterator function for make Details more visible

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 36
 Search Car
In order to identify the anticipated car and its
details based on a single value of the object, I iterated through every item in the array using
linear search in this function. The user can find the desired car and its information with the aid of
this procedure.
The menu-driven search operation's output as well as the code are shown in the following
images.

This illustration demonstrates how a user can search for a car's details by typing the driver's
name.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 37
 Delete Car
An element cannot be properly removed from
an array. This rule also applies to an object array. As a result, I was able to apply a different
technique to empty the components of a certain index based on user input. The output of the
following code demonstrates that the user-entered car has been removed from the array.

This is the code for the delete Function

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 38
 Car Update
I created Function to update the Details if user
Want Changes the Detail of they given User can use this Function to Update new Details.
This is the code I use for do that

I Used List Iterator for this Function

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 39
 This is an interface for Update Function

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 40
 Enter Results Of 3 Rounds
One of the most significant operations in the
application is this one. In this case, I developed an algorithm to remove or push the last
individual from the array after adding unique car numbers to the array. While loops and if
statements are used to write this program. The final race winners will be displayed using this
array in the future.
This is the code I used

This is Interface,

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 41
Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 42
The aforementioned graphics demonstrate how a user might enter data into an application. Here,
the user must enter the car number in the appropriate places throughout the race. The program is
designed to identify the final competitor in the race and then push that vehicle outside of the
array. We will therefore have the final three winners after three rounds.
Find the Winners Of Race
The user must be given the final standings of the top three finishers in this section. I utilized the
same array that we did earlier for this, and I accessed it to show the outcomes. As a result, the
user will see the final outcomes of the three rounds as follows.

Here, we could see that, similar to the earlier in Winner of 3 rd round I had supplied,
automobiles 1, 2, and 3 were in first, second, and third places, respectively. With some

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 43
 appropriate explanation, the same outcomes
were attained in this operation.
This is the code I used for find winners.

Introduction to error handle

An error is a significant problem that prevents the software from functioning correctly.
Programming languages have many different types of flaws, according to the concepts. In Java,
an error is a subclass of Offers a competitive that denotes a severe problem and instructs a Java
application not to try to catch it. Generally speaking, it has been found that most errors are
brought on by unusual variables and are unfixable in common situations. Since they show
exceptional circumstances that shouldn't exist, these errors are called Unchecked Exceptions. In
Java, both the idea of errors and the idea of exceptions are present. As a result, an exception and
an error differ in a number of ways.
In a Java program, there are typically three different types of problems that could appear:
1. Syntax error
2. Runtime errors
3. Logic errors
Syntax error
The compiler discovers bugs when the program is run, some of which are categorized as syntax
errors or compiler faults. Hackers might introduce syntax errors by typing a word incorrectly,
leaving out any necessary commas, or using an opening brace without a corresponding closing
brace typing a word incorrectly, leaving out any necessary commas, or using an opening brace

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 44
 without a corresponding closing brace, hackers
might introduce syntax errors.
These errors are sometimes simple to identify because the compiler may give programmers
placement or root problem warnings.

Runtime errors
Runtime errors are mistakes that abruptly end a program. When the environment recognizes an
operation that cannot be performed, they happen when a program is operating. Input errors are a
common source of runtime issues. An input error occurs when a user inputs a value that the
software cannot process while unable to process while it is waiting for the user to submit a value.

Logic errors
When the program is executed, the compiler detects errors that can alternatively be categorized
as syntax issues or compiler faults. Mistyping a keyword, leaving out any necessary punctuation,
or inserting an opening brace without a corresponding closing brace are all examples of syntax
errors that hackers can create.
These errors can occasionally be identified quickly because to compiler warnings about
placement or underlying issues.
Java has methods for dealing with these exceptions. Five keywords have been specifically
created by Java to handle exceptions.
like as
• try – Used to specify where the exception code is
• catch – This is preceded by try and handles the exception
• finally – This is used to execute the code of the program whether the exception was
handled or not.
• throw – used to throw an exception
• throws – used to declare exceptions

Suitable error handling for the system

Developers should think about the tools they'll use before getting started on the programming so
that everything runs smoothly. Developers must therefore be aware of the program's goals and
intended applications.
The application used exception handling ("try-catch") to make it simple to implement exceptions
like array index out of bounds and method handling exceptions.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 45
 I used a try catch block in the CarRacing
application to track down any exceptions the
program may have thrown. In this case, I used the try block at the start of the main method to
ensure that the try block would cover the entire main method. Any exception that the program
throws is caught in the catch block, which is entered at the end of the program.
The codes below show exactly how I implemented error handling in the vehicle race event.

The aforementioned photos demonstrate how I used try-catch blocks in my software. The catch
method contains a generic exception handler that can handle all types of exceptions, and they are
typically placed at the conclusion of the program. The try block covers all of the primary method
requirements in the program.
Overall, I would say that Java exception handler is a great tool for developers to employ in order
to detect runtime or compile-time issues and display them in a useful manner. It is evident from
the images above that the ABC racing event makes use of error handlers to detect mistakes and
display them at the conclusion.

Test Cases of ABC Car race event Application

Test No :01
Test Method :White Box testing
Test Case: Register Car Details

Expected Output:
Input each detail of the car into the Collection as an object

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 46
 Test Status:pass

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 47
 Test No :02
Test Method :White Box testing
Test Case: Display all Details

Expected Output:
Display all Details that enter in Register Car

Test Status:pass

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 48
 Test No :03
Test Method :White Box testing
Test Case: Search for car

Expected Output:
Display the Expected car detail

Test Status:pass

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 49
 Test No :04
Test Method :White Box testing
Test Case: Delete a car from collection

Expected Output:
Delete all Details that enter in Register Car

Test Status:pass

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 50
 Test No :05
Test Method :White Box testing
Test Case: Update the data of Collection

Expected Output:
Display Updated data

Test Status:pass

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 51
 Test No :06
Test Method :White Box testing
Test Case: Enter 3 round results

Expected Output:
Enter 3 results of 3 rounds

Test Status:pass

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 52
 Test No :07
Test Method :White Box testing
Test Case: View the Winners

Expected Output:
Display Final 3 winners

Test Status:pass

The following test cases prove that the car racing application performs as the business
requires evidence that the car racing application performs as required by the business and
effectively counters user inputs. The race car event has no problems in the program's most
fundamental processes, as seen above. These test cases are important in understanding the
program's concerns and errors.
This question's overall criterion covers the successful implementation of error management in the
racing car event application and the program's test cases successful implementation of error
management in the racing car event application and the program's test cases is covered by this
question's overall criterion.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 53
 Task 3
Registered Car details are stored from oldest to newest

The information of all registered cars, in order of newest to oldest, have been requested by ABC
PVT LTD. Below is the Display detail function of the application. The automobile has been
preserved in order of age by the current array.

I reversed the data in the array using the Java collections. reverse Using below code to
complete this Task. This was completed successfully.

And this was completed successfully. Below is result of This .

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 54
Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 55
 complexity for queue algorithms

The length of the input determines how long it takes an algorithm to run, which is known as
temporal complexity. It determines how long it takes for each algorithmic code statement to run.
An element that is added first is accessed, deleted, or processed first according to the First-In-
First-Out principle, which is the foundation of the queue Abstract Data Type (ADT). A line has
two ends, the front and the back. At the back end, an element is inserted. At the front end, an
element is deleted. A queue can be implemented using Arrays or Linked Lists. An element that is
inserted first is accessed, removed, or processed first in a queue, which is an Abstract Data Type
(ADT) based on this notion. The front and back of a line are its two ends. The insertion of an
element takes place at the back. An element is deleted at the front end. The term "dequeue
operation" refers to the removal of an entry from a queue. The element at the front of the queue
can frequently be inspected using the peek technique supported by implementations.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 56
 Introduction to ADT
An object's behavior can be described by a
collection of values and a collection of actions, and this behavior is known as an abstract data
type (ADT). The definition of ADT merely specifies the actions that must be taken, not how they
must be carried out. It is unclear what algorithms will be utilized to carry out the operations and
how the data will be structured in memory. Because it provides an implementation-independent
view, it is dubbed "abstract."

Implementation of a data type is not necessary for the user to understand. Therefore, a user needs
to know aware of what a data type is capable of, not how it will be used.
There is Three ADTs they are,
 List ADT
 Stack ADT
 Queue ADT

List ADT
A list with a head structure made up of a count, pointers, and the address of the comparison code
needed to compare the information in the list typically stores the data in key sequence.
The data node has a self-referential pointer that links to the next node in the list as well as a
pointer to a data structure.
Stack ADT
Instead of storing data in each node, the Stack ADT Implementation stores a pointer to the data.
The address is provided to the stack ADT and the software allots memory for the data.
The ADT contains both the head node and the data nodes. The only thing the calling function can
see is the stack pointer. A pointer to the top and a count of the number of entries currently in the
stack are also included in the stack head structure.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 57
 Queue ADT
The stack abstract data type's basic design is
followed by the queue abstract data type (ADT).
Each node has a link pointer to the subsequent element in the queue and a void pointer to the
data. It is the duty of the software to allot memory for storing the data.
 Enqueue() Function Add an element to the queue's end.
 If the queue is not empty, use the dequeue() function to remove and return the first
member.
 If the queue is not empty, the peek() function will return the element without removing it.
 size() Function Provides the queue's element count.
 isEmpty() Function If the queue is empty, return true; otherwise, return false.
 isFull() Function If the queue is full, return true; otherwise, return false.

Benefits of ADT:
Abstraction: The user is not required to understand how the data structure is implemented.
Better Conceptualization: The real world is better understood for us thanks to ADT.
Resilient: The program is capable of detecting errors and is robust.

We can tell from these definitions that they are vague about how these ADTs will be written and
how the actions will be performed out. An ADT can be utilized in a variety of ways, for as
utilizing arrays, singly linked lists, or doubly linked lists for the List ADT. Similar to how linked
lists or arrays can be used to implement queue ADT and stack ADT.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 58
 Encapsulation
The definition of encapsulation is the grouping
of data into a single unit. It is the mechanism that connects the data the code manipulates with
the code itself. Encapsulation can also be viewed as a barrier that stops code from the outside of
the barrier from accessing the data.
Another way to think of encapsulation is as a barrier that prevents programs from accessing
information outside of its boundaries. In encapsulation, variables or data are theoretically hidden
from other classes and are only accessible by member functions of the class in which they are
declared. It is also referred to as a combination of data-hiding and abstraction because, similar to
encapsulation, the data in a class is protected from other classes by making its members or
methods private, and the class is made available to the public or end-users without revealing any
implementation-specific information.
By designating all class variables as private and creating public methods to set and retrieve
variable values, encapsulation is achieved. It is further defined with the aid of the setter and
getter methods.
Encapsulation benefits include:
Data Hiding is a method of limiting our data members' access by concealing the implementation
specifics. Data concealing is also possible using encapsulation. The user won't be aware of how
the class is internally implemented. The user won't be able to see how the class is keeping
variables' values in order. The user will only be aware that variables are initialized with the given
value and that we are giving the values to a setter method.
Greater Flexibility: Depending on our needs, we can make the class's variables read-only or
write-only. We must remove the setter functions like setName(), setAge(), etc. from the
aforementioned application if we want to make the variables read-only.
Reusability: Encapsulation enhances reusability and is simple to modify in response to new
requirements.
Code testing is simple: For unit testing, encapsulated code is simple to test.

Use of Encapsulation for the scenario

For this system, encapsulation is essential. This approach makes guarantee that external
functions (methods) do not unintentionally change the contents of the object. This can be used by
the coder to prevent the user from getting data. Private access users are not allowed. In this
programming, encapsulation shields other objects from seeing the automobile class's
implementation specifics. This method, known in this programming as "information concealing"
or "data hiding," is utilized to protect automobile node data from external exploitation. It uses the
access modifier "private" to shield data from any outside scrutiny. The car Id, car brand, car
sponsor, and car driver characteristics cannot be changed by other objects thanks to the Info
class. A change attempt will result in an error notification being displayed. because the private
designation for the class name.
Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 59
It provides so-called getter functions with names like getcarId(). As a result, the program adds
four getters to the Info class. The other elements can't directly access the data. They must instead
employ the getters that were created to protect the data from unauthorized changes.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 60
Task 4:
shortest path algorithms

Finding the shortest path is one of the functions of shortest path algorithms. The shortest phrase
in computer science Path problems can take many different shapes, making it necessary to apply
a variety of techniques to solve them all. For simplicity and generality, shortest path algorithms
typically operate on an input graph, abbreviated . Vertices and edges , which link them, make up
this graph. A graph that has weighted edges is called a weighted graph. The graph is referred to
as undirected when these edges are bidirectional. The graph may occasionally even contain
cycles. For a certain sort of graph, each of these minute variations enables one method to
perform better than another.
Shortest path algorithms come in a huge variety. The shortest path between points A and B may
need to be found, but you may also need to know the shortest route between point A and every
other point in the graph.
The shortest path methods have a wide range of uses. As already mentioned, shortest path
algorithms are used by mapping applications like Google Maps and Apple Maps. They are also
necessary for research into the logistics, operations, and road network. Additionally essential for

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 61
 computer networks like the Internet are shorter
path algorithms.
Examples for shortest path algorithms
• Bellman Ford’s Algorithm
• Kruskal's Algorithm
• Dijkstra’s Algorithm
• Floyd Warshall’s Algorithm

First of all lets see what is Graph

An example of a non-linear data structure is a graph, which consists of vertices and edges. Edges
are the lines or arcs that connect any two nodes in the network, whereas vertices are also referred
to as nodes. Graphs are used to tackle many difficulties in the real world. Graphs are used to
represent networks. Networks include things like telephone lines, circuit networks, and city
paths. Graphs are frequently used in social networking websites like Facebook and LinkedIn. For
instance, each person on Facebook is represented by a vertex (or node). Each node is a structure
that contains data about a person, such as their name, gender, location, and ID.

Nature of a graph

Vertices are the fundamental building blocks of a graph. Nodes or vertices are other names for
vertices. Each node/vertex has the choice of having a label or not.
Edges To connect two graph nodes, edges are either drawn or used. It might be an ordered pair
of nodes in a directed graph. Any two nodes can be connected by edges in any manner
imaginable.
There aren't any rules. Sometimes edges are referred to as arcs. You can mark or leave unlabeled
any edges.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 62
Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 63
 shortest path algorithms chosen for
scenario's
The quickest technique must be used if the ABC Company must visit all required to see of its
participants within a day. The two shortest path methods that are most suitable for determining
the shortest route are:
 The Dijkstra Algorithm
 The Kruskal Algorithm

The Dijkstra Algorithm

A graph's shortest path between two nodes can be found using Dijkstra's Algorithm.
By determining the shortest route between a node (referred to as the "source node") and every
other node in the network, you may construct a shortest-path tree. This technique is used by GPS
devices to determine the quickest route between the starting point and the destination.
The algorithm records the shortest paths that are currently known to exist between every node
and the source node, and it updates these values whenever a shorter path is found.

"node" refers to the locations. Here, we particularly look for the route that will connect a given
node to every other node in the graph. We will receive the shortest path tree as a result. To
determine the shortest route between the present location and several locations, GPS devices
employ this algorithm. I would use an illustration to view the participants in the event in order to
go forward. This will all be predicated on my opinion.
The distance between a number of nodes, which stand in for each participant in the race, is
shown in the graph above. The starting point of the company's journey is shown by the source
node (0). The numbers along each edge indicate how far apart each node is from the other.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 64
Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 65
 Finding the shortest distance
The distance between each node and the source
node must first be entered into a database. In a loop, this table would ultimately change. The set
we make to list the unvisited nodes works similarly.
Unvisited Nodes: {0,1,2,3,4,5,6}
We start from 0
As the First step
we should find the shortest path between the two adjacent edges which connect the source node.
Second step
Select the edge that has the smallest distance value and is not already present.
And continue this until you have done,

0 1 2 3 4 5 6
0 ∞ ∞ ∞ ∞ ∞ ∞
5 ∞ ∞ 3 ∞ ∞
5 8 6 5 ∞
∞ 8 6 8
∞ 8 8
5 8

0 – 1 =5
0–2=8
0–3=6
0–4=3
0 – 5 =5
0– 6=8
Thus, we have shown and defined the quickest route that corporate executives can use to reach
each vehicle event participant. I have provided examples and visuals to clarify the shortest path
algorithm in this explanation.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 66
 Algorithm Kruskal
Sorting edges by weight is the core idea behind
the Kruskal algorithm. Then, starting with the less important weight, we start removing edges
one by one. We might use a disjointed set data structure to achieve this. The disjoint set data
structure makes combining two nodes into a single component simple to combine two nodes into
a single component. We can quickly ascertain whether two nodes have already been combined
with its assistance.
Here are some commonalities among algorithms.
1. To store the collections of vertices, create an array.
2. Make an array to hold the edges and weights of the graph.
3. Use an empty array to start the spanning tree.
4. Divide the vertices of the graph into various groups.
5. Arrange the edges in ascending weight order.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 67
 Introduction to sorting algorithms
Describe the sorting algorithm.
An algorithm for sorting is a method for arranging a lot of items in a specific order, such as
alphabetically, from highest to lowest value, or from shortest to longest distance. algorithms for
sorting
lists of items are used as input data, which are then subjected to various processes to produce
ordered arrays. Applications for sorting algorithms include arranging products according to price
on a shopping website and deciding which pages to display first on a search engine results page
(SERP)
 The bubble sort algorithm goes through the list repeatedly, comparing items that are close
to each other and trading places with them if they are out of order. This procedure is
carried out over and over until the entire list has been sorted.

 The insertion sort algorithm starts by sorting the very first two items, then compares the
third item to the second one, moving it if necessary, then repeats the procedure with the
first item. Most of the time, subsequent items going through the same process don't need
to move very far in the sorted items.

 The interval size gets smaller with each iteration of the list as the Shell sort algorithm
compares and sorts items at intervals. Due to the pieces being closer to their targeted
positions, bubble sorts, which are the final passes, are significantly quicker.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 68
Selection sort
The selection sort technique sorts an array by continually selecting and inserting the smallest
element (in ascending order) from the unsorted segment and continually selecting and inserting
the minor mostmost minor detail (in ascending order) from the unsorted part; the selection sort
technique sorts an array. The function maintains two subarrays in the provided collection.
1) A subarray that has already undergone sorting.
2) The last subarray lacked sorting.
In each iteration of the selection algorithm, the inner most minor element (regarding ascending
order) from the unordered subarray is transferred to the sorted subarray.
class Info{

static void Selection_Sort(int arr[], int n)

{
for(int i = 0; i < n - 1; ++i)
{
int min_index = i;
for(int j = i + 1; j < n; ++j)
{
if(arr[j] < arr[min_index])
min_index = j;
}
int temp = arr[i];
arr[i] = arr[min_index];
arr[min_index] = temp;
}
}
public static void main(String[] args)
{
int n = 7;
int arr[] = {2, 0, 1, 4, 3,5,6};
Selection_Sort(arr, n);
System.out.print("The Sorted numbers : ");
for(int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
}
}

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 69
 A simple sorting algorithm is a selection sort.
The list is split in half, with the sorted portion
on the left end and the unsorted portion on the right, using this technique for sorting which uses
in-place comparisons. The unsorted portion contains the entire list at first, but the sorted section
is initially empty. The leftmost element is swapped with the middle element from the unsorted
array, and that element is then added to the sorted array. Repeating the process, the unsorted
array boundary pushes one element to the right unsorted array boundary is pushed one element to
the right by repeating this process.
The initial stage of the blue filter uses an unsorted array. The sorted elements are represented by
the blue elements and the sorted ones by the orange blocks.

Bubble sort algorithm

When two adjacent elements are compared and found to not be in the correct order, the bubble
sort algorithm swaps them. The first index is used as a starting point, and the first and second
elements are then compared. The component verifies They are switched if the first element is
greater than the second. The second and third elements are then compared. If they are not in
order, swap them.
class Info{

static void Bubble_Sort(int arr[], int n)

{
for(int i = 1; i < n; ++i)
{
for(int j = 0; j <= (n - i - 1); ++j)
{
if (arr[j] > arr[j + 1])
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args)
{
int n = 7;
int arr[] = {2, 0, 1, 4, 3,5,6};

Bubble_Sort(arr, n);

System.out.print("The Sorted numbers: ");

for(int i = 0; i < n; ++i)

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 70
 System.out.print(arr[i]+" ");
}
}

Comparison the performance of two sorting algorithms.

Selection Sort Bubble Sort

With the selection sorting algorithm, the In the bubble sorting algorithm, two elements
minimum element in the array is chosen and are checked and then switched to their proper
positioned correctly. positions.

In the best case scenario, its time complexity is In the best situation, it has an O time
O(N2). complexity (N)

The worst-case time complexity is O(N2) In the worst scenario, it has an O(N2) time
complexity.

It is a sorting method that works well. Not efficiency

The effectiveness of an algorithm

Due to their scarcity, computer resources should be utilized wisely. Simply put, efficiency is
getting the most out of the least amount of resources. The algorithm is also simplified in the
same way. The computational resources an algorithm uses are used to evaluate its efficacy.
Utilizing a minimum amount of resources is crucial for achieving the highest algorithm
efficiency. Since it is impossible to directly compare significant resources like space and time
complexity, time and space difficulty could be taken into account when evaluating algorithmic
efficiency.

The effectiveness of an algorithm can be evaluated in two ways:

• Space complexity - space efficiency / memory required

• Time complexity, efficiency, and required time

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 71
 Space complexity
The amount of memory a certain algorithm uses
overall, including the space of input parameters for use. In order to determine the algorithm's
space complexity, it needs to determine how much space the program's variables take up. The
formula the following in terms of space complexity:
Space complexity = auxiliary space + space use by input values
A program's space complexity should always be measured because it has a significant impact on
the algorithm's effectiveness. Although a lengthy algorithm will still execute and produce the
intended results with some delay, a large amount of memory space will prevent the compiler
from operating, making it a major problem.
We must be aware of the various data kinds and the amount of memory each one requires in
order to compute the space complexity. Depending on the operating system and compiler, this
memory amount varies. 
Time complexity
The length of time it will take to execute or run a program or algorithm is referred to as its
temporal complexity. Big O notation is typically used to express this entire runtime. The
assignment above covered the asymptotic notation used to indicate temporal complexity. Loops
and duration typically result in a rise in temporal complexity. The worst-case time complexity,
often known as the Big O notation, is used to determine the greatest time required for any input
size because the method performance depends on the input supplied.

Task 5:
Algorithms are developed to address a certain issue. The primary goal of algorithms is to create
a well-functioning system with an organized set of codes. However, a functional algorithm
wouldn't be sufficient to finish the job entirely. Let's say there is a problem with a solution, but
it will take hours to find it. Is it regarded as an algorithm with good performance and efficiency?
Consequently, a number of factors, including user usability, security, modularity, and others,
affect the system's performance. A solution that performs well can help in all the criteria listed
above and more. An algorithm needs to be performance-driven, and there are a few ways to
determine this.

Asymptotic analysis is what?

Asymptotic analysis is input-bound, which implies that it assumes that the algorithm will run
for a fixed amount of time, even in the absence of any input. All other components are involved
in being constants aside from the "input."
Asymptotic analysis is the process of calculating any operation's execution time in mathematical
calculation units. For instance, one operation's running time might be calculated as f(n), but
another operation's running time might be calculated as g. (n2).

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 72
 As n rises, the running time of the first
operation will grow linearly whereas the
running time of the second operation will grow exponentially. The running times of both
operations will be almost identical if n is really tiny.

 Three categories of time are frequently used to categorize the time needed by
algorithms
 In the best-case scenario, the time needed for program execution is minimal.
 The typical amount of time needed to run a program.
Asymptotic Notations
We'll be looking at many criteria for how asymptotic analysis occurs because time is the most
crucial element in this theory. Mathematical tools and techniques are used to show how time-
consuming asymptotic analysis algorithms are. The time complexity is demonstrated by the
examples below, each illustrating a different situation.
• Best case
• Worst Case
• Average Case

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 73
Big-O Notation

The term "Big O Notation" is frequently used in the programming field. It stands for the
maximum possible running time for an algorithm. It conveys the maximum amount of time
required to execute an algorithm. As a result, the Big-O notation in the asymptotic notation
represents the worst-case time.
The graph of the large O notation is shown in the image below. Here, it just serves to illustrate
the worst-case situation.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 74
 Omega notation

Big O notation is a type of mathematical notation that expresses how a function limits itself
when the argument tends to zero or infinity. Big O is a member of the asymptotic notation
family, often known as the Bachmann-Landau notation family, which was created by Paul
Bachmann, Edmund Landau, and others. The German word Ordnung, which means "order of
approximation," was chosen by Bachmann as the symbol. In computer science, the Big O
notation is used to categorize algorithms according to how much space or run time they use as
the size of the input increases. The difference between an arithmetic function and a better
understood approximation, which is a well-known example of such a difference, is usually
represented as a bound in analytic number theory using the big O notation.

Theta notation
Big theta is an illustration of the function from above and below. This gives the results of an
average case scenario and indicates the upper and lower bounds of an algorithm's execution time.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 75
 a brief introduction to trade-offs
The decision to reduce or eliminate one quantity, quality, or feature of a set or design in
exchange for advantages in other areas is known as a trade-off (or tradeoff). A tradeoff happens
when one thing improves while another must decline, to put it simply. A full container must
remove some items in order to take any more, and vessels can carry a few large goods or several
small items. Tradeoffs result from a variety of constraints, including simple physics - for
instance, only a specific volume of objects can fit into a given space, so a full container must
remove some items in order to take any more
Tradeoffs are frequently used to refer to alternative options and varied configurations of a single
object, such as tuning guitar strings to play various well as varied configurations of a single
object, such as tuning guitar strings to play a variety of notes.
The best algorithm is one that uses the least amount of memory and produces the output as
quickly as possible. However, it's not always possible to have both of these qualities at once. A
lookup table algorithm is the most basic requirement. This implies that the responses to specific
questions may be recorded for every conceivable case. To acquire answers quickly, one method
would be to write down the entire lookup table, but this would take a large amount of space.

Types of trade off for ADT implement in programming

Recalculation vs. Lookup Tables
An algorithm's implementation that uses a lookup table can compute table entries as needed,
which shortens computation time but requires more memory, or it can include the full table,
which shortens computation time but requires more memory.
Compressed Vs Un compressed data
Algorithms that make trade-offs between space and time can also be used to manage data
storage. Data that has not been compressed takes up more space but can be accessed more
quickly than data that has (because data compression saves space but requires time to conduct
the decompression procedure). Any viable remedy is reliant on the specifics of the issue.
Working directly with compressed data, such as compressed bitmap indices, can occasionally be
quicker than working without compression.
Loop unrolling vs. smaller code
The computation time needed to return to the beginning of the loop at the conclusion of each
iteration is saved by using this method, which is frequently used to lengthen the code for each
iteration of a loop. Using loop unrolling, larger code can be traded for faster program speed.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 76
 Introduction to the Independent data
structure
Independent Data Structure:
What Is It?
We go into these data structures in more detail. They can be put into use with a variety of
supporting structures. For instance, a linked list or an array could be used to implement the
stack and queue.
What does employing independent data structures mean?
The development of effective algorithms requires the use of data structures. It permits
abstraction and reusability. When performing activities like data storage, retrieval, or
processing, using the right data structures can help programmers work more quickly. Large data
sets are simpler to manipulate
What are advantages of using Independent data structure?
Data structures facilitate effective data storage in storage devices.
Utilizing a data structure makes it easier to retrieve data from a storage source.
Effective and efficient processing of both little and big amounts of data is provided by data
structures.
When performing tasks like data storage, retrieval, or processing, a programmer might speed
up the process by using the right data structure.
With the use of an effective data structure technique, massive amounts of data can be
conveniently manipulated.
Utilizing data structures can only promote reusability over time.
Data structures like arrays, linked lists, trees, graphs, stacks, etc. have been thoroughly verified
and proven so anyone may use them without having to conduct more research or
development. If you choose to design your own data structure, you may need to do some
study, but the goal would be to tackle a problem that is more sophisticated than what these can
offer.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 77
 Benefits of independent data structure for using
and implementing in program
This provides an implementation-independent data view. Implementation independent allows
the programmer to modify the specifics of the implement without changing how the data user
interacts with it because there are typically several ways to implement an abstract data type.
The storing of information on hard drives is made possible by the data structures. It enables the
administration of big data sets, such as databases and Internet indexing services. They
necessitate the creation of effective algorithms. It makes it possible to save data securely on a
computer. The information is stored for future use and accessible through a number of
mechanisms. Additionally, the information is protected and cannot be lost (especially if stored
on magnetic tapes). It allows for the use and processing of data within a software system. It
facilitates data processing. Any device that is connected to the internet, such as a laptop,
phone, etc., can be used to view the data at any time.

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 78
 References
Anon., 2022. www.google.com. (n.d.). what d test plan - Google Search. [online] Available at.
[Online]
Available at: https://www.google.com/search?
q=what+d+test+plan&rlz=1C1CHBD_enBD1009BD1009&oq=what+d+test+plan&aqs=chrome.
.69i57j0i22i30j0i390l4.6979j0j15&sourceid=chrome&ie=UTF-
Anon., 2022. softwaretestinghelp.. [Online]
Available at: https://www.softwaretestinghelp.com/how-to-write-test-plan-document-software-
testing-training-day3/
Anon., n.d. afteracademy. [Online]
Available at: https://afteracademy.com/blog/stack-and-its-basic-operations/
Anon., n.d. algorithm&rlz. [Online]
Available at: https://www.google.com/search?q=floyd-
warshall+algorithm&rlz=1C1CHBD_enBD1009BD1009&sxsrf=ALiCzsbLJBfU0MwRnTTnH1
GhUg8zvrGZ5g:1667005053881&so
Anon., n.d. Bellman–Ford Algorithm. [Online]
Available at: https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
Anon., n.d. stackoverflow.com/questions. [Online]
Available at: https://stackoverflow.com/questions/7294634/what-are-the-time-complexities-of-
various-data-structures
Anon., n.d. towardsdatascience. [Online]
Available at: https://towardsdatascience.com/8-common-data-structures-every-programmer-
must-know-171acf6a1a42

Thimira Maneth
Col 00078123
Data Structures and Algorithms
pg. 79