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
Assignment title for a sample scenario

Student’s name

List which assessment Pass Merit Distinction

criteria 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 Y/N
comments on the student work?

1
Has the work been assessed
accurately? Y/N

Is the feedback to the student:

Give details:
• Constructive?
• Linked to relevant assessment
criteria? Y/
• Identifying opportunities for N
improved performance? Y/
• Agreeing actions? N
Y/
N
Y/
N

Does the assessment decision need

amending? Y/N

Assessor signature Date

Internal Verifier signature Date

Programme Leader signature (if

required) Date

2
 Confirm action completed

Remedial action
taken

Give details:

Assessor signature Date

Internal
Verifier Date
signature

Programme
Leader signature Date
(if required)

Higher Nationals - Summative Assignment Feedback Form

Student Name/ID

Unit Title Unit 19: Data Structures and Algorithms

Assignment Number 1 Assessor

Date Received 1st

Submission Date submission

Date Received 2nd

Re-submission Date submission

Assessor Feedback:

3
LO1 Examine abstract Data types, concrete data structures and algorithms
Pass, Merit & P1 P2 M1 M2 D1
Distinction
Descripts

LO2 Specify abstract data types and algorithms in a formal notation

Pass, Merit & P3 M3 D2

Distinction
Descripts

LO3 Implement complex data structures and algorithm.

Pass, Merit & P4 P5 M4 D3
Distinction
Descripts

LO4 Assess the effectiveness of data structures and algorithms.

Pass, Merit & P6 P7 M5 D4
Distinction
Descripts

Grade: Assessor Signature: Date:

Resubmission Feedback:

Grade: Assessor Signature: Date:

Internal Verifier’s Comments:

Signature & Date:

4
 * 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
5
signature

Student Date
signature

6
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.
7
 • 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.

8
 • 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 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.

9
 • I understand the plagiarism and copying policy of Edexcel UK.
• I know what the consequences will be if I plagiarize 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:
(Provide E-mail ID)
Date:
(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 2023/24
Unit Tutor
Assignment Title Specification, Implementation, and Assessment of
Data Structures for a sample scenario
Issue Date
Submission Date

10
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

A rapid increase in the number of buses has resulted in intense competition in the
Transportation industry.
In today’s environment, if you have a credit card and the Internet, you can book
tickets.
Busses of any size should look for a solution that helps them to meet these dynamic
requirements and generate an impressive return on investments as well.

A bus reservation system is a software solution designed to provide customers with a

11
personalized easy-to-utilize user experience for booking and purchasing tickets
online.
It stores customers’ personal data records, and other information. A transport booking
eliminates human factor risks and improves conversion rates for your business.

Imagine you are a software developer at XYZ Pvt Ltd, and your company has
requested a bus seat reservation system with the following requirements.

[Link] Registration (Customer name, Mobile number, Email ID, City, Age)
[Link] Registration (Bus number, Total seat, starting point, ending point, Starting
time, Fare)
[Link] can search for buses
4. Customer can reserve seat. As soon as a reservation is made, the respective
customer should be notified through a message. All the customers' reservations should
be saved for future use.
[Link] can cancel reservation at any time. As soon as a cancellation is done, the
respective customer should be notified through a message. Next customer for the
above seat should notified through a message.
[Link] customers can request a new seat. During this time, the respective
customer should wait in queue.
[Link] reservations should be displayed.

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

XYZ Pvt Ltd plans to visit all these customers through the shortest path within a day.
Analyse the above operation by using illustrations, of two shortest path algorithms,

12
 specify how it operates using a sample graph diagram. Sort the customers based on
age with two different sorting algorithms and critically review the performances of
those two algorithms by comparing them.

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.
“Imperative ADTs are basis for object orientation.” Discuss the above view stating
whether you agree or not. Justify your answer.

Task 3: Registered Customer details are stored from oldest to newest. The
management of XYZ Pvt Ltd should be able to find from the newest to oldest
registered customer details. Using an imperative definition, specify the abstract data
type for the above scenario and implement specified ADT using java programming
and critically analyse the complexity of chosen ADT algorithm. Examine the
advantages of Encapsulation and Information hiding when using an ADT selected for
the above scenario.

Task 4: Evaluate how Asymptotic analysis can be used to assess the effectiveness of
an algorithm and discuss at least two ways in which the efficiency of an algorithm can
be measured with relevant examples.

Explain the sort of trade-offs exists when you use an ADT for implementing
programs by supporting your answer with specific examples. You also need to
evaluate the benefits of using independent data structures for implementing programs.

Grading Rubric

13
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.
14
 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

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

15
 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.

Task 1

16
Classes, main method and valid operations

Customer class

The Customer class represents an individual who uses the bus reservation system. Each
customer is defined by their personal information: name, email, phone number, city, and

17
age. The class provides encapsulation by making these attributes private and exposing
them through getter methods, ensuring the data cannot be altered once a Customer object
is created. Additionally, the toString() method provides a string representation of a
customer, making it easier to display their details in a user-friendly format. For instance,
calling toString() on a customer object returns their name and email, which is useful for
identifying customers in various scenarios like reservations or seat change requests. This
class plays a foundational role in the system as customers are central to all operations,
including making reservations, canceling bookings, and requesting seat changes. By
focusing on immutability through final attributes, this design ensures the integrity of
customer information throughout the application's lifecycle. The Customer class is
straightforward but essential for tracking individuals in the system.

Bus class

18
The Bus class models the bus entities in the reservation system. Each bus is characterized
by attributes like bus number, total seats, reserved seats, starting point, ending point,
starting time, and fare. The class ensures data integrity by keeping attributes private and
providing getter methods for controlled access. It also maintains a dynamic count of

19
reserved seats, which is updated through the reserveSeat and cancelSeat methods. These
methods include checks to prevent overbooking or canceling seats when no reservations
exist, throwing exceptions in such cases. The toString() method offers a detailed
description of the bus, including its availability and route, facilitating easy display of bus
details during operations like search and reservation. The Bus class acts as the backbone
of the system, connecting users to transportation options. Its design balances functionality
with safety, ensuring seamless interactions while preventing misuse, such as reserving
seats beyond capacity.

Reservation class

The Reservation class links a customer with a bus, representing a booking in the system.
It encapsulates the customer and bus objects, creating a relationship between the two. By
storing these objects directly, the class simplifies operations like retrieving customer
details for a reservation or accessing bus information. The toString() method in this class
concisely describes the reservation, showing which customer has reserved a seat on which
bus. This class is crucial for managing and tracking bookings, as it binds the primary
entities of the system—customers and buses. It serves as a record of transactions,
20
ensuring that each booking is uniquely identified and managed efficiently. With its
focused design, the Reservation class supports core system functionalities, such as
adding, canceling, and listing reservations.

WaitList class

The WaitList class manages a queue of reservations waiting for availability. Implemented
using a Queue, this class leverages the First-In-First-Out (FIFO) principle, ensuring that
customers are served in the order they joined the waitlist. It provides methods to add and
remove reservations, check if the waitlist is empty, and retrieve the next reservation for
processing. This class is vital for managing scenarios where all seats are reserved,
offering customers an opportunity to queue for cancellations. By decoupling waitlist
management from other system functionalities, the WaitList class promotes modularity
and simplifies the overall design.

SeatChangeStack class

21
The SeatChangeStack class handles seat change requests using a Stack, adhering to the
Last-In-First-Out (LIFO) principle. Customers can add requests to this stack when they
wish to change their seats. The class provides methods to add, remove, and peek at the
most recent seat change request. This design ensures that the most recent request is
processed first, accommodating scenarios where priority might be given to newer
requests. The SeatChangeStack class adds flexibility to the system, addressing customer
preferences dynamically while maintaining simplicity through its stack-based
implementation.

BusReservationSystem class

22
23
24
25
The BusReservationSystem class integrates all the components and acts as the
application's control center. It manages customer and bus registration, bus searches,
reservations, cancellations, waitlists, and seat change requests. This class maintains lists
of customers, buses, reservations, a waitlist, and a seat change stack, ensuring
comprehensive tracking of all system operations. The login method simulates user
authentication, while the main menu-driven interface allows users to interact with the
system. Helper methods streamline operations like finding customers by email or buses
by number. Exception handling throughout ensures robust error management, providing
users with clear feedback during invalid operations. By centralizing functionality, this
class orchestrates interactions between components, delivering a cohesive user
experience.

Main method

26
27
The main method in the BusReservationSystem class serves as the entry point for the
application and is responsible for initializing and managing the system's core
functionalities. This method creates an instance of the BusReservationSystem class and
triggers its primary operation through the start() method, which launches the system's
menu-driven interface. The main method adheres to Java's standard signature public static
void main(String[] args), allowing it to be executed directly by the Java Virtual Machine
(JVM). Its role is to set the stage for all subsequent interactions, providing the first
invocation that leads to the seamless integration of the system's components, including
customers, buses, reservations, the waitlist, and the seat change stack. By centralizing the
initialization logic within the main method, the code ensures modularity and scalability.
For instance, future enhancements or pre-configuration tasks, such as loading default
buses or setting system parameters, can easily be incorporated here. Moreover, this
method decouples the application's bootstrapping process from its business logic,
adhering to clean coding practices. Through its simplicity, the main method emphasizes
clarity and maintainability, acting as the anchor point that ties the system together,
allowing users to interact with the reservation system effortlessly and intuitively.

Customer registration

The addCustomer operation in the BusReservationSystem allows the registration of a new

customer within the system. The operation begins by prompting the user to input various
details such as the customer's name, email, phone number, city, and age. After collecting
this information, the system checks whether the provided email address already exists in
the customer list to avoid duplication. If a duplicate email is found, an exception is
thrown with a message indicating the customer already exists. If the email is unique, the
customer is added to the customers list. The customer is stored as an instance of the
Customer class, ensuring that all their details are preserved. This operation is crucial for
managing the user base, ensuring only valid, non-duplicate customer records are created,
and facilitates future interactions, including reservations, cancellations, or seat change
28
requests. By managing the registration process, it also allows for customized customer
services based on individual data like age and city, which might be useful for offering
promotions or targeted information. This operation, therefore, contributes to the system’s
foundation by enabling user-specific interactions with the bus reservation system.

Bus registration

The registerBus operation allows the addition of a new bus into the reservation system.
When executed, the user is prompted to enter the bus details, including the bus number,
total number of seats, starting point, ending point, starting time, and fare. These inputs are
collected and used to instantiate a new Bus object. The newly created bus is then added to
the buses list, ensuring that it becomes available for future reservations. This operation
plays a critical role in expanding the system's transportation options by allowing
administrators to register new buses with specific routes and seating capacities. It
facilitates the management of available buses for passengers to select from based on their
travel needs. The bus registration ensures that the system dynamically reflects the
availability of new routes and buses in real time. This feature is particularly essential for
maintaining an up-to-date catalog of transport options that are linked with reservations,
ensuring customers can view accurate bus details during their search for available
services. Additionally, by entering bus-specific details such as the fare, starting time, and
route information, the system can easily track and manage individual buses and their
operational parameters.

Bus search

The searchBuses operation enables users to search for buses based on their starting and
ending points. Upon activation, the user is prompted to input the desired starting and
ending locations for the bus journey. The system then filters through the registered buses
in the buses list, comparing each bus’s starting and ending points with the user’s inputs. If
29
a match is found, the details of the bus, including the bus number, available seats, route,
starting time, and fare, are displayed. If no buses match the criteria, a message is shown
indicating that no buses are available for the given route. This operation is essential for
enabling customers to plan their travels by easily finding available buses between desired
destinations. The bus search operation improves the user experience by providing real-
time availability information and making it easy to compare different buses for a given
route. This feature enhances the efficiency of the system by allowing customers to focus
on specific routes and travel details. The search function also allows the system to handle
various dynamic bus schedules and provide travelers with a convenient, streamlined way
to book their tickets based on their travel preferences.

Seat reservation

The reserveSeat operation allows customers to book a seat on a bus. When a customer
attempts to reserve a seat, they must first provide their email address. The system uses
this to locate the corresponding customer in the customers list. Once the customer is
identified, they are prompted to enter the bus number for the desired bus. The system then
searches the buses list for a matching bus. If the bus is found and it has available seats,
the reserveSeat method of the Bus class is called, incrementing the reserved seat count. A
new Reservation object is created, linking the customer and the bus, and is added to the
reservations list. The customer is then notified that the reservation was successful. This
operation is essential for managing seat availability and maintaining the integrity of
reservations. It ensures that the bus's reserved seat count is updated and prevents
overbooking. The reservation system is the core of this application, allowing customers to
secure their travel arrangements with a few simple inputs. Moreover, by maintaining a list
of reservations, the system ensures it tracks all bookings, making it easier to handle
cancellations and modifications, should they arise.

Reservation cancellation
30
The cancelReservation operation allows customers to cancel their existing reservations.
When this operation is invoked, the customer is prompted to enter their email address,
which the system uses to locate their reservation. The system searches the reservations list
for a matching reservation and, if found, proceeds to cancel it. The cancellation process
involves decrementing the reserved seat count of the corresponding bus and removing the
reservation from the reservations list. If there are any passengers on the waitlist, the next
customer is notified and their reservation is confirmed. This ensures that the seat
previously reserved by the canceled reservation is filled by the next customer,
maintaining full seat utilization. This operation is essential for freeing up seats on buses
and for efficiently managing the bus’s seat availability. Additionally, the waitlist
functionality ensures that customers who were unable to secure a seat can still benefit
from canceled reservations. The cancelation process reflects the dynamic nature of the
bus reservation system, allowing for flexibility and real-time seat reallocation. Overall,
the cancellation operation helps maintain accurate booking data, avoid overbooking, and
provide a smooth customer experience for users who need to change their plans.

Seat change request

The requestSeatChange operation enables customers to request a change to their current

reserved seat. When a customer wishes to modify their reservation, they are prompted to
provide their email address, which the system uses to locate their reservation in the
reservations list. Once found, the reservation is added to the SeatChangeStack, a stack
data structure that stores seat change requests in a last-in-first-out (LIFO) order. This
operation allows customers the flexibility to request modifications to their bookings,
though it doesn’t directly execute the change immediately. Instead, seat changes are
handled in the order they are requested, allowing for prioritization of more recent
changes. This feature is particularly useful in scenarios where customers may want to
switch to different seats on the same bus or request a transfer to a different bus entirely.
31
The stack structure ensures that the most recent requests are given priority and handled
first. This operation is a key feature for enhancing customer satisfaction, as it allows users
to adapt their bookings according to changing preferences. While it doesn’t immediately
affect the seat availability, the operation ensures that customers’ requests are tracked and
processed efficiently within the system.

Display reservations

The displayReservations operation allows users to view all current reservations made in
the system. When triggered, the system iterates through the reservations list and displays
the details of each reservation, including the customer's name and the bus they are
reserved on. If no reservations have been made, the system will notify the user that there
are no current reservations. This operation is useful for administrators or users who want
to review the entire reservation landscape, providing a transparent view of the bus
bookings. It is also beneficial for customers who may want to check their own reservation
status, as it helps them verify their booking details. The operation ensures that all active
reservations are displayed, allowing for efficient tracking and management of the
reservations in the system. By providing a consolidated view of reservations, this
operation helps avoid conflicts and ensures that all users have access to up-to-date
reservation data. This operation contributes to the overall functionality of the reservation
system by giving both users and administrators the ability to monitor and verify active
bookings in a user-friendly format. The operation ensures that the bus reservation system
operates with clarity and real-time data visibility. (Sumaiya Simran, 2023)

Explanation to stack

A stack is a fundamental data structure used in computer science that operates on a "Last
In, First Out" (LIFO) principle. This means that the most recently added element is the
first one to be removed, akin to a stack of plates where the last plate placed on top is the
32
first one to be taken off. A stack typically supports two primary operations: push and pop.
The push operation adds an element to the top of the stack, while the pop operation
removes the top element. Additionally, many stacks support the peek operation, which
allows users to view the top element without removing it. Stacks are particularly useful in
scenarios where the order of operations needs to be reversed or when operations are
dependent on a sequence. For example, they are used in depth-first search algorithms,
expression evaluation (such as for parentheses balancing), and function call management
in programming languages (i.e., the call stack). A stack can be implemented using arrays
or linked lists, and it is often employed in situations requiring temporary storage where
elements need to be processed in reverse order. The simplicity and efficiency of stacks
make them a key component in numerous computer algorithms and applications.

The operations of a stack

push operation

The push operation in a stack adds an element to the top of the stack. This operation
ensures that the newly added item becomes the most accessible or the first to be removed
when the stack is popped. In most implementations, the push operation checks if there is
sufficient space in the stack before adding the element, especially in cases of fixed-size
stacks. If there is space, the operation increments the stack's top pointer (or index) and
places the new element at the top. In dynamic stack implementations, resizing may occur
if the stack is full, allowing for unlimited growth within memory constraints. The push
operation is crucial in various applications, such as maintaining a history of operations,
managing function calls, and implementing backtracking algorithms. For instance, during
the execution of a program, the call stack uses the push operation to save the state of
function calls and their local variables. Despite its simplicity, push is an efficient
operation, typically running in constant time O(1) in most cases. However, if resizing is
required in dynamic stacks, the time complexity may temporarily increase due to the
33
copying of elements to a larger stack. Overall, the push operation is integral to the utility
and versatility of stacks.

pop operation

The pop operation in a stack removes and returns the topmost element. It follows the Last
In, First Out (LIFO) principle, where the most recently added item is the first to be
removed. When performing a pop operation, the stack typically checks whether it
contains any elements to avoid underflow errors (attempting to remove an item from an
empty stack). If the stack is not empty, the pop operation retrieves the current top
element, decrements the stack's top pointer (or index), and effectively removes the
element. This operation is widely used in algorithms and real-world applications. For
example, when parsing expressions, the pop operation helps manage matching
parentheses by removing elements that have already been paired. It is also vital in
reversing sequences, such as reversing a string or traversing graph nodes in a depth-first
manner. The pop operation is efficient, usually operating in constant time O(1), provided
the stack is not empty. However, it requires careful handling to prevent errors in stack
management. Proper use of the pop operation ensures a well-organized and predictable
behavior in software systems that rely on stack structures.

Peek operation

The peek operation allows access to the topmost element of the stack without removing it.
This is particularly useful when there is a need to inspect the element at the top to make
decisions without altering the stack's state. For instance, in parsing algorithms, the peek
operation can verify the current top element to ensure compatibility with incoming data,
such as matching symbols in syntax validation. Unlike the pop operation, peek does not
modify the stack; it simply reads the value at the top. Before performing a peek, the stack
typically checks if it is empty to avoid errors or exceptions. In programming, peek is
34
commonly employed in undo systems, function call tracing, and game logic where
temporary inspection of the latest action is necessary. This operation is highly efficient,
operating in constant time O(1) in most implementations. Peek is a non-destructive
operation, preserving the integrity of the stack while providing vital insights into its
contents. Its simplicity and efficiency make it an essential feature of stack-based
algorithms and systems, enabling better control and decision-making during execution.

isEmpty operation

The isEmpty operation checks whether a stack contains any elements. It returns a boolean
value: true if the stack is empty and false otherwise. This operation is essential for
ensuring safe and predictable stack management. Before performing operations like pop
or peek, it is common practice to invoke isEmpty to prevent errors such as underflow,
which occur when trying to remove or access elements in an empty stack. The isEmpty
operation is straightforward; it simply examines whether the top pointer (or equivalent
indicator) in the stack points to a valid element. In applications, isEmpty is frequently
used in control flows to determine if further operations are possible. For example, during
a depth-first traversal of a graph, the algorithm continues as long as the stack is not
empty, ensuring all nodes are visited. The operation is extremely efficient, running in
constant time O(1), as it involves a simple check. Its reliability and simplicity make
isEmpty a critical safeguard in stack implementations, ensuring robustness and preventing
runtime errors in software applications.

isFull operation

The isFull operation determines whether a stack has reached its maximum capacity. It
returns a boolean value: true if the stack is full and false otherwise. This operation is
particularly relevant in fixed-size stack implementations, where the total number of
elements is limited by a predefined size. When isFull returns true, it indicates that no
35
more elements can be added to the stack until some are removed. The operation checks
the top pointer or index against the stack's capacity to ascertain if the stack has reached its
limit. In scenarios involving resource constraints, such as embedded systems or memory-
limited environments, isFull is essential for managing stack operations efficiently. It helps
prevent overflow errors, which occur when attempting to push elements into a full stack.
In dynamic stacks, while isFull may not always apply due to automatic resizing, its
concept can still be relevant when there are system-imposed limits. Like other stack
operations, isFull runs in constant time O(1), as it involves a straightforward comparison.
Its role in ensuring safe stack operations highlights its importance in both static and
dynamic stack implementations.

Stack implementation in the scenario

36
37
Critical review of how a stack used to implement different operations based on
above implementation

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle,
making it useful for scenarios requiring elements to be processed in reverse order of their
addition. In the provided implementation, the stack class encapsulates core stack
functionalities, including push, pop, peek, isEmpty, isFull, and a display method. The
class leverages an integer array to store stack elements, and the top variable tracks the
index of the current top element. This code serves as a comprehensive foundation for
understanding stack operations, covering critical aspects such as overflow and underflow
38
conditions. It includes robust error handling to ensure operations like pushing and
popping remain safe within the constraints of the stack's capacity.

The push operation adds an element to the top of the stack. In this implementation, it
checks if the stack is full before incrementing the top index and placing the new value at
the updated index. This validation prevents stack overflow, a scenario where elements
exceed the allocated memory. The simplicity and clarity of the push method demonstrate
how stacks handle dynamic additions while maintaining LIFO order. The method also
outputs a message for both successful additions and overflow errors, enhancing its
usability. This operation exemplifies how stacks are used in various scenarios, such as
parsing expressions, where elements are pushed onto the stack as they appear.

The pop method removes and returns the top element of the stack. It checks if the stack is
empty before decrementing the top index, thereby ensuring no invalid memory access
occurs. If the stack is empty, it returns -1 and prints an underflow error message. This
operation highlights how stacks support removal in reverse order of insertion, which is
crucial in applications like undo mechanisms in software, where the most recent action is
reversed first. The pop operation in this implementation is efficient and maintains the
integrity of the stack by adhering to boundary checks, reflecting real-world scenarios.

The peek method allows viewing the top element without removing it, giving insight into
the stack's current state. By checking if the stack is empty, it prevents access to undefined
memory and provides appropriate feedback. This method is particularly useful in
algorithms requiring conditional processing based on the stack's top element, such as
evaluating expressions or managing nested structures. The implementation ensures
efficient retrieval and aligns with the principle of minimal data movement in stacks,
reinforcing the stack's role in maintaining order without unnecessary modifications.

39
The isEmpty and isFull methods are utility functions that determine the stack's status. The
former checks if the top index equals -1, indicating no elements in the stack, while the
latter compares the top index to the maximum capacity minus one. These methods are
foundational for stack operations, ensuring actions like push and pop are executed only
when valid. Their implementation prevents errors such as stack overflow and underflow,
demonstrating their importance in maintaining stack integrity. In practical applications,
these checks are indispensable, enabling safe and predictable behavior.

The display method iterates through the stack array from the bottom to the top, printing
all elements. This provides a visual representation of the stack's contents, which is useful
for debugging and understanding the current state. The method also checks if the stack is
empty before printing, ensuring clarity in its output. This feature is vital for real-time
monitoring of stack operations, especially in educational or testing scenarios where
understanding intermediate states is crucial. The display method enhances the stack's
usability by offering insights into its behavior during execution.

Stacks are widely used in various applications, such as expression evaluation, recursion
handling, and function call management. In this implementation, the stack's operations
demonstrate how these scenarios are supported. For example, the push and pop methods
are fundamental in parsing algorithms, where operators and operands are managed using
stacks. Similarly, the peek method is essential in decision-making processes within these
algorithms. The robustness of this implementation highlights how stacks simplify
complex tasks by offering a structured approach to managing data.

While the implementation effectively demonstrates stack operations, some areas could
benefit from improvement. For instance, the pop and peek methods could throw
exceptions instead of returning default values like -1 to align with best practices in error
handling. Additionally, the use of a fixed-size array limits the stack's scalability;
implementing a dynamic resizing mechanism would make it more versatile. Despite these
40
limitations, the code's clarity and adherence to fundamental stack principles make it an
excellent resource for learning and applying stack operations. This implementation
effectively bridges theoretical concepts with practical applications. (StudySmarter UK,
2019)

Task 2

Implementation of the above scenario using the selected data structure and its valid
operations

41
42
43
44
45
46
47
48
49
Error handling

Error handling is an essential part of any software application to manage runtime

exceptions effectively and ensure seamless user experiences. In the provided bus
reservation system, error handling mechanisms are implemented using try-catch blocks
and exception propagation. This ensures that the program can gracefully handle
unexpected scenarios, such as invalid input or resource unavailability, without abruptly
terminating. Java's checked and unchecked exceptions allow developers to predict
potential errors and address them through structured error-handling logic.

The addCustomer method illustrates the use of custom exception handling for duplicate
registrations. Before adding a customer to the system, the program checks if the entered
email already exists in the customer list. If a duplicate is found, an Exception is thrown
with a meaningful error message. This proactive validation prevents data inconsistency

50
and provides clear feedback to users. This approach demonstrates defensive
programming, reducing the likelihood of logical errors and ensuring data integrity.

In the reserveSeat method, error handling is used to prevent overbooking buses. The
reserveSeat method of the Bus class throws an exception if the reserved seats exceed the
bus's total capacity. This exception is caught and displayed to the user, ensuring that the
system does not process invalid reservations. By encapsulating this logic within the Bus
class, the program adheres to the principle of modularity and promotes reusable,
maintainable code.

The cancelSeat method in the Bus class incorporates error handling to prevent underflow
scenarios when there are no reservations to cancel. If a user attempts to cancel a seat on
an empty bus, an exception is raised. This ensures that the system does not perform
invalid operations or compromise the bus's state. The combination of exception throwing
and clear error messages contributes to robust and user-friendly functionality.

The main menu and choice selection employ error handling to manage invalid user input.
If a user provides non-numeric input for menu selection, the program captures the
resulting NumberFormatException and prevents crashes. Additionally, clear prompts and
error messages guide users to correct their mistakes. This demonstrates how error
handling can improve the usability and reliability of the system by accommodating
human errors.

The cancelReservation method highlights an innovative use of error handling in

conjunction with business logic. When a reservation is canceled, and the waitlist is not
empty, the system automatically allocates the freed seat to the next customer in the queue.
51
This seamless transition, combined with appropriate exception handling for overflows,
ensures optimal utilization of resources while providing fairness to users.

The SeatChangeStack class uses a stack data structure to manage seat change requests.
The removeSeatChangeRequest method handles the scenario where a request is attempted
to be removed from an empty stack. Instead of causing a runtime error, it returns null,
ensuring safe operations. By combining error handling with conditional logic, the system
minimizes disruptions and gracefully handles edge cases.

The systematic use of exception handling across different functionalities in the bus
reservation system highlights its importance in developing reliable software. From
preventing overbooking to managing waitlists and ensuring data integrity, error handling
enhances user satisfaction and operational efficiency. Developers can further improve the
system by introducing specific exception types, such as DuplicateCustomerException or
OverbookingException, for more descriptive error management. Overall, error handling
transforms potential failures into manageable events, ensuring the program's stability.

Test plan

Aim

The aim of this project is to develop a bus reservation system that automates the process
of booking and managing bus tickets, ensuring efficiency and convenience for both
customers and operators. The system provides essential functionalities such as user
registration, bus registration, seat reservation, and cancellation, along with waitlist and

52
seat change management. Designed for ease of use, it minimizes manual errors, enhances
operational efficiency, and provides a seamless experience. By incorporating robust
validation, error handling, and scalability, the system ensures reliability and
accommodates future enhancements, such as integration with payment gateways and
mobile platforms.

Scope

The bus reservation system is designed to meet the needs of customers and bus operators,
focusing on usability and efficiency. Customers can register, search for buses by route,
and manage reservations effortlessly, while bus operators can add and manage buses. The
system supports features like waitlists for full buses and seat change requests, enhancing
flexibility. With secure login, robust validation, and real-time seat availability updates, it
ensures accuracy and reliability. The system can scale to support larger operations and
integrates potential future enhancements such as payment systems and analytics tools. It
is designed to be user-friendly, efficient, and robust for everyday use.

Objectives

Verify login functionality with valid username and password

Validate error messages for invalid login credentials

Test successful registration and prevention of duplicate entries

Verify the bus registration process with complete input validation

Ensure correct buses are displayed based on route criteria

53
Test seat reservation for available buses

Validate cancellation of existing reservations

Verify appropriate error handling for non-existent reservations

Ensure requests are added and managed correctly in the stack

Test accurate and detailed display of all current reservations

Evaluation of test plan

The test plan for the Bus Reservation System outlines a detailed strategy for validating all
core functionalities of the system, ensuring it meets the expected standards and provides a
seamless user experience. This plan covers various types of testing, including functional,
security, and usability testing, to verify each module's performance and efficiency. Each
feature, from login and registration to seat reservation and cancellation, will be
thoroughly tested for both expected and unexpected behaviors. The primary objective is
to guarantee that the system operates flawlessly in real-world scenarios, providing reliable
functionality for customers and bus operators alike. Additionally, the test plan will also
cover edge cases and error-handling situations to ensure the system is robust under all
circumstances. The systematic evaluation of the system’s core functionalities will help
identify any gaps and fine-tune the system to ensure its readiness for deployment.

Login functionality is a critical aspect of any reservation system, as it provides secure

access to the platform for both customers and bus operators. The first step in testing login
functionality will be to verify that the system correctly allows access with valid
credentials. The correct login process will be tested by providing the registered username
and password and ensuring access is granted. On the other hand, invalid credentials

54
should trigger appropriate error messages, such as “Invalid username or password,”
ensuring that the system does not allow unauthorized users to enter the platform. Security
measures, such as rate limiting and brute force protection, will also be tested to prevent
unauthorized access attempts. Additionally, the system should offer password recovery
options, which will be verified to ensure customers can regain access if they forget their
credentials. The login functionality needs to be both secure and user-friendly, ensuring an
intuitive experience while safeguarding customer data.

Customer registration is an essential feature that enables users to create accounts and
access personalized services. The first step in testing the registration process is ensuring
that the system collects all required customer information, including name, email, phone
number, city, and age. Input validation is crucial here, as the system should reject
incomplete or invalid entries, such as invalid email addresses or missing required fields.
The system must also check for duplicate customer records to prevent multiple accounts
with the same email address. This will be verified by attempting to register a new
customer with an email that already exists in the database, ensuring the system returns an
appropriate error message. Additionally, edge cases such as customers with unusual
names or special characters in the email address should be handled correctly. Finally,
successful registration should provide a confirmation message, allowing customers to
proceed with reservations or other system features.

Bus registration is a core feature of the system, allowing bus operators to input and
manage bus details for passengers to view. During testing, each bus registration should
collect necessary details, including bus number, total seats, route information (starting
point, ending point), starting time, and fare. The system should also ensure that bus
numbers are unique and not duplicated, which will be tested by attempting to register the
same bus number more than once. Each input field must be thoroughly validated to
ensure data accuracy. For example, the total seats field should only accept valid integers,
55
while the fare field should only accept numeric values. The system should also verify that
the route and starting time fields contain reasonable values, such as valid locations and a
correctly formatted time. Once registered, the system must display the bus details
correctly when customers search for available buses. Testing should confirm that the
registered bus details are accurate and accessible.

Seat reservation is the primary function for customers in the system. Testing this
functionality will involve verifying that customers can reserve seats on available buses
and that the system accurately reflects real-time seat availability. First, testing will ensure
that customers can view a list of available buses for their selected route and make a
reservation. When a customer attempts to reserve a seat, the system should check the
availability of seats on the selected bus. If there are available seats, the reservation should
proceed, and the bus’s reserved seat count should increase. Conversely, if there are no
seats available, the system should display an error message indicating that the bus is full.
Additionally, the system should handle edge cases such as attempting to reserve a seat on
a bus with a waitlist, adding the customer to the waitlist and notifying them when a seat
becomes available. Finally, seat reservation data should be correctly saved and updated in
the system database.

Reservation cancellation is a crucial feature that allows customers to free up seats for
others or change their plans. This functionality will be tested by verifying that customers
can cancel their existing reservations successfully. When a reservation is canceled, the
system should update the corresponding bus’s reserved seat count and ensure that the seat
is now available for new reservations. In cases where the bus has a waitlist, the system
should automatically offer the next customer in line the reserved seat. The system will be
tested by attempting to cancel a reservation for a customer who has a valid booking,
ensuring that the cancellation is processed smoothly. Error handling will also be verified
by testing the cancellation of non-existent or expired reservations. The system should
56
prevent cancellation if the reservation does not exist or has already been canceled,
providing the user with an appropriate error message.

Seat change requests are an important feature for customers who may want to change
their assigned seat due to personal preferences or other reasons. The seat change request
functionality will be tested to ensure that it works as expected. Customers will be allowed
to request a seat change after making a reservation, and their request should be added to a
dedicated queue or stack for processing. The system should validate that the seat change
request is possible, such as ensuring that there are available seats on the bus and that the
request is within the allowable time frame. The system will be tested by submitting a seat
change request and verifying that it is added to the request stack. Additionally, testing
will ensure that seat changes are processed in a fair and logical order. The system must
handle scenarios where no available seats exist for a change, providing proper feedback to
customers who cannot change seats.

The final step in this test plan involves ensuring the system accurately manages and
displays all reservations. This functionality is essential for both customers and bus
operators to track and manage their bookings. The system should display a
comprehensive list of all reservations, showing the customer’s name, bus number, and
seat details. Testing will verify that all reservations are listed accurately, and customers
can easily identify their bookings. Additionally, the system should allow customers to
filter or search for their reservations by various criteria, such as bus number or date of
reservation. Error handling will also be tested to ensure that the system can handle any
discrepancies, such as failed database connections or missing reservation data. Finally,
the reservation management system should allow bus operators to view and modify
reservations, cancel or update customer details as necessary, and provide real-time seat
availability information to customers. ([Link], 2022)

57
Test cases

Test 1 - Verify login functionality with valid username and password

Tes Pre- Test steps Test data Expecte Post- Actua Status
t conditio d conditio l
case n result n result
ID
T01 Need the Run the Valid Main Main Main Succes
system system login menu menu can menu s
credential be seen
Enter s
valid
login
credential
s

58
Test 2 - Validate error messages for invalid login credentials

Tes Pre- Test steps Test data Expecte Post- Actua Status
t conditio d conditio l
case n result n result
ID
T02 Need the Run the Invalid Access Error Acces Succes
system system login will be message s is s
credential denied denied
Enter s
invalid
login
credential
s

Test 3 - Test successful registration and prevention of duplicate entries

Test Pre- Test Test Expected Post- Actual Status

case condition steps data result condition result
ID
T03 Need the Login Name, Customer Registration Customer Success

59
 system to the Email, will message is
system Phone register registered
, City,
Enter Age
1

Enter
test
data

Test 4 - Verify the bus registration process with complete input validation

Tes Pre- Test Test Expecte Post- Actual Status

t conditio steps data d condition result
case n result
ID
T04 Need the Login Bus Bus will Registratio Bus is Succes

60
 system to the number register n message registere s
syste , Total d
m seats,
Starting
Enter point,
2 Ending
point,
Enter Starting
test time,
data Fare

Test 5 - Ensure correct buses are displayed based on route criteria

Test Pre- Test Test Expected Post- Actual Status

case conditio steps data result condition result
ID n
T05 Need the Login Starting Matching Matching Matching Success
61
 system to the point, buses bus buses are
system Ending will be information seen
point shown
Enter
3

Enter
test
data

Test 6 - Test seat reservation for available buses

Tes Pre- Test Test Expected Post- Actual Status

t conditio steps data result condition result
cas n
e
ID
T06 Need the Login Email, Reservatio Reservatio Reservatio Succes
system to the Bus n will be
62
 syste numbe added n message n is added s
m r

Enter
4

Enter
test
data

Test 7 - Validate cancellation of existing reservations

Tes Pre- Test Test Expected Post- Actual Status

t conditio steps data result condition result
cas n
e
ID
T07 Need the Login Emai Reservatio Reservatio Reservatio Succes
system to the l n will be n n is s

63
 syste cancelled cancellatio cancelled
m n message

Enter
5

Enter
test
data

Test 8 - Verify appropriate error handling for non-existent reservations

Test Pre- Test Test Expected Post- Actual Status

case conditio steps data result conditio result
ID n n
T08 Need the Login Email Error Error Error Success
system to the message message message
system will be is seen
seen
Enter
64
 5

Enter
test
data

Test 9 - Ensure requests are added and managed correctly in the stack

Test Pre- Test Test Expecte Post- Actual Status

case condition steps data d condition result
ID result
T09 Need the Login Email Seat Seat Seat Success
system to the change change change
system request request require
will be message is
Enter added added
6

Enter
test
65
 data

Test 10 - Test accurate and detailed display of all current reservations

Test Pre- Test Test Expected Post- Actual Status

case condit steps data result conditio result
ID ion n
T10 Need Run the None Available Main Available Succes
the system reservatio menu reservatio s
system ns will be ns are
Enter 7 visible visible

66
Evaluation of the test cases

The login functionality is the gateway to the system, making its evaluation crucial for
both security and user experience. A well-functioning login system ensures that only
authorized users can access the platform, while also protecting sensitive data from
unauthorized access. This test case addresses the core validation of user credentials,
including proper error handling for invalid logins. By testing the login with both correct
and incorrect credentials, the system can demonstrate its ability to reject unauthorized
access attempts while granting valid users permission. It is essential to ensure that login
credentials are correctly validated against the database to prevent unauthorized access. A
user-friendly approach to error messages is important, as users should not be confused
when entering incorrect credentials. Additionally, testing should extend to security
features like brute force protection and password recovery. Without these, the login
process could be vulnerable to attacks or user frustration. A critical aspect of login
functionality is ensuring that the system is both intuitive and secure. Effective validation
and error handling help in safeguarding the system, while a smooth and fast login
experience fosters customer satisfaction and retention. Finally, the login functionality
must perform well under stress to handle high volumes of user login attempts.

67
Customer registration is fundamental to the operation of any reservation system,
providing users with personalized access. Evaluating this test case ensures that the
registration process is smooth, secure, and error-free. The system must correctly handle
all required fields, including name, email, and contact details, and perform rigorous
validation to prevent incorrect or incomplete data entries. By checking for duplicate
entries and invalid inputs, the system can guarantee that only valid and unique customer
accounts are created, which is vital for data integrity and security. The test case also
ensures that customers are given feedback if their registration fails due to these errors,
making the registration process user-friendly. Another important aspect is the prevention
of malicious or spam registrations, which requires the system to verify the correctness of
user inputs, particularly email addresses and phone numbers. The registration system
should also handle edge cases, such as customers with special characters in their names or
email addresses. After a successful registration, the system must confirm the account
creation with a clear confirmation message, enabling users to proceed with booking
tickets. Ultimately, the registration system needs to be both robust and intuitive to foster a
positive customer experience and seamless interactions with the reservation platform.

Bus registration is a cornerstone of the reservation system, as it provides the infrastructure

for users to search for and book their travel options. This test case is designed to validate
the correctness of bus data, ensuring that every bus registered in the system adheres to
predefined rules. When bus operators register a bus, they should be able to enter all
necessary details, such as bus number, total seats, routes, and schedules. The system must
verify that bus numbers are unique to avoid conflicts in the database. Furthermore, the
bus data must be validated for accuracy, such as ensuring that the total seats value is a
valid integer, and the route information is consistent with the available locations. A
critical component of this test is ensuring that the system is flexible enough to handle
multiple bus routes, different schedules, and various seat configurations. The accuracy of
the bus information directly impacts the reservation process, so rigorous testing is

68
necessary to prevent errors. Additionally, the system must display bus details clearly and
correctly to users, as any discrepancies can confuse or frustrate customers. The bus
registration test ensures that the system maintains an organized and consistent database,
supporting future scalability and a smooth user experience.

Seat reservation is one of the most important functionalities of the bus reservation system,
directly impacting customer satisfaction. This test case evaluates how the system handles
seat bookings, ensuring that available seats are reserved correctly and that the system
updates availability in real-time. One key aspect of testing this functionality is verifying
that the system correctly identifies available buses for a customer’s preferred route and
that it accurately reflects real-time seat availability. The test ensures that a customer can
only reserve a seat if one is available, preventing overbooking. Furthermore, it is essential
that the system manages seat reservations efficiently, updating the database and reflecting
the changes instantly across all customer interfaces. It is also important to test the
system’s response to edge cases, such as attempting to book a seat on a fully booked bus
or reserving a seat from a waitlist. These edge cases should be handled with clear error
messages or notifications. The seat reservation system should also allow customers to
modify or cancel their reservations if necessary. A seamless reservation process reduces
the risk of errors, improves user satisfaction, and boosts system reliability. This test case
is critical for ensuring the smooth and effective operation of the booking system.

Testing reservation cancellation is vital to the functionality of the system, as it directly

impacts users' ability to modify their travel plans. This feature allows customers to cancel
their reservations when their plans change, making it a crucial part of the user experience.
The cancellation process must be tested to ensure that seat availability is updated
promptly and accurately when a reservation is canceled. After cancellation, the seat
should become available for other customers, and any associated fees or policies should
be clearly enforced. The system must also handle scenarios where the user tries to cancel
69
a non-existing or already canceled reservation, providing appropriate error messages to
avoid confusion. A successful reservation cancellation will involve verifying that all
related records are properly removed from the database and that the system accurately
reflects the change in seat availability. Another key factor in this test case is ensuring that
waitlist functionality works effectively. When a reservation is canceled, the system
should automatically move the next person in line to the newly available seat. Finally,
testing should ensure that cancellation processes are secure and not vulnerable to abuse or
mistakes. Overall, the cancellation functionality needs to be seamless and intuitive to
support customer satisfaction.

Seat change requests are a valuable feature that enhances the flexibility of the reservation
system. This test case is designed to ensure that customers can easily request changes to
their reserved seats if necessary, and that the system manages these requests effectively.
The first step in evaluating seat change requests is ensuring that the system allows
customers to submit their requests through a straightforward interface. Once submitted,
the system must validate the request by checking seat availability and confirming that the
requested seat is unoccupied. The system should also ensure that seat change requests are
processed in a fair and orderly manner, particularly when there are multiple requests or
limited seats. Another important aspect of testing is ensuring that the system can handle
scenarios where no available seats are left for changes, providing appropriate feedback to
customers. Furthermore, testing should validate that any approved seat changes are
reflected in the database in real-time, with correct updates to the seat availability for all
users. The seat change process must also be tested for security to prevent unauthorized
modifications. The feature should be flexible and intuitive, offering users the option to
change seats without complicating the reservation process. Overall, seat change
functionality adds a layer of convenience for customers, improving the overall booking
experience.

70
The reservation management system is a critical component of both customer and
operator experience, as it ensures that users can track, modify, and view their reservations
with ease. The test case for displaying and managing reservations ensures that all
reservations are shown accurately, with all relevant details clearly presented, such as bus
number, customer name, and seat number. This test case also includes verifying the
functionality that allows users to search and filter through their reservations, which is
essential for customers who may have numerous bookings. The system should allow
users to view their active, canceled, or pending reservations, providing them with the
flexibility to manage their bookings as needed. Error handling is also a key factor,
particularly in situations where the reservation data is incomplete or corrupted. In such
cases, the system should display a clear error message and guide the user on how to
resolve the issue. For operators, the ability to manage reservations is just as important, as
it allows them to handle customer requests and updates in real-time. The test case also
ensures that all updates, such as cancellations or seat changes, are reflected immediately
across the platform, providing up-to-date reservation information for both customers and
operators. This comprehensive reservation management ensures the system is user-
friendly and efficient.

The overall evaluation of the bus reservation system’s test cases demonstrates the
robustness and efficiency of the system in handling key functionalities such as login,
registration, bus management, seat reservations, and cancellations. Each of the test cases
aims to address specific aspects of the system, ensuring that the platform is secure, user-
friendly, and scalable. The login and registration tests ensure that only valid users can
access the system and create accounts, while the bus and seat reservation tests ensure that
customers can easily book and manage their travel plans. Reservation cancellation and
seat change tests ensure flexibility, allowing customers to modify their bookings as
needed. Furthermore, the display and management of reservations test ensures that both
customers and operators can access real-time, accurate data. Collectively, these test cases

71
provide a comprehensive framework for validating the system’s functionality, ensuring
that it meets the needs of both customers and operators. The success of each test case
indicates that the system is well-equipped to handle the real-world demands of a bus
reservation platform, providing a reliable and convenient service. (Dominik Szahidewicz,
2024)

Task 3

Introduction to imperative definition

An imperative definition is a way of describing or defining something by explicitly

stating the actions, steps, or commands needed to achieve a particular outcome. In the
context of programming, it refers to a paradigm where instructions are given to the
computer to perform tasks sequentially, focusing on how a result is achieved. Unlike
declarative definitions, which state what the desired result is, imperative definitions
emphasize the procedure or the exact operations required to reach that result. For
example, in an imperative approach to solving a problem, you might specify a series of
operations like initializing variables, iterating through loops, and modifying data. This
concept extends beyond programming to include situations where step-by-step
instructions are crucial, such as in algorithms, procedures, or workflows. The imperative
style is practical when precise control over the process is needed, making it foundational
in areas requiring detailed execution instructions.

Specification of the abstract data type based on an imperative definition

For instance, in an organization like XYZ Pvt Ltd, there are customer registration records.
These are stored sequentially but occasionally management wants them in reverse order,
new to old. We can define such an ADT by following an imperative approach:. This

72
'CustomerRegistry' ADT will manage customer information so that the operations of
either natural or reverse order can be performed efficiently. This is done on sound ground
with the ADT, providing clear-cut methods for adding, accessing, and managing the data.

One possible basic data structure for implementing the CustomerRegistry ADT is a
dynamic array or doubly linked list. These are very good structures for sequential data
storage and, at the same time, flexible enough to accommodate the needs of efficient
reverse traversal. In the case of registration of a new customer, its details would be added
in the array at the bottom so as to maintain the natural ordering of dates of registration. In
the cases of lists required by the administration in reverse order, auxiliary structures are
used with temporary reverse of sequence so that newer records become the first to top.

The main operations supported by this ADT include the following:

AddCustomer(customer)-it adds a new customer record at the end of this dynamic array;
it starts with memory allocation of the record and then positions at the next available
location of the array. Any metadata or indices are updated as may be necessary to
maintain the integrity of the dataset, hence making the adding process efficient and
according to the natural sequence of registration.

Other important operation would be the GetNewestToOldest(), that would return, in

reverse order, a list with all customer records. In order to implement the
GetNewestToOldest(), first take an empty stack and then range from the last to the first
element of the array, pushing each record onto the stack. Afterwards, pop each record one
at a time off of that stack, inserting them in order into a result list for returning in reverse
order. This, in turn, flips the list of results back to management, showing records in the
correct order from newest to oldest.

Operations that require record order to be natural, in the order of arrival or entry, are
supported by the ADT using GetOldestToNewest(). It does this by iterating through the
73
array from the first to the last element, moving (and copying) each record as-is into a
resulting list. This is because in this approach, the inherent sequential nature remains
undisturbed with some extra computation, and therefore when queries are made following
the original storage sequence, their records can be fetched very fast and effectively.

This will ensure a number of benefits in this imperative definition of this ADT. Since
explicit data structures and step-by-step procedures were specified for the system, the
latter is understandable and hence implementable. Auxiliary structures like stacks can
also enable efficient transformation of data in a temporary fashion without actually
changing a dataset, so integrity can be maintained while fulfilling a range of operational
needs.

The design of CustomerRegistry ADT is also scalable and extensible. It can be easily
extended to handle record filtering depending on dates or update customer information.
This kind of adaptability will mean that the ADT remains up to date and valid when
requirements within an organization change.

Therefore, this imperative definition of the CustomerRegistry ADT satisfies these two
needs: one for maintaining the natural order of registration and another for the possibility
of retrieving in reverse order. An abstract data type could help by exploiting an
appropriate internal data structure with well-defined operations so that practical and
reliable maintenance of customer records is assured flexibly and in order. In this way,
efficiency improvements in the operations ensure scalability of the system for any number
of future use cases. (Definition Guru, 2024)

Task 4

Explanation to asymptotic analysis

74
Asymptotic analysis is a mathematical approach used to evaluate the performance of
algorithms by analyzing their behavior as the size of the input data grows indefinitely. It
focuses on understanding how the runtime or space requirements of an algorithm scale
relative to the size of the input, typically denoted as n. Rather than providing exact
metrics, asymptotic analysis describes the growth trends using notations such as Big-O
(O), Omega (Ω), and Theta (Θ). Big-O represents the upper bound or worst-case scenario,
ensuring the algorithm will not exceed a certain runtime. Omega describes the lower
bound or best-case scenario, and Theta gives the exact growth rate when both bounds
coincide. By abstracting away machine-specific details and constant factors, asymptotic
analysis offers a high-level understanding of an algorithm’s efficiency, enabling
comparisons between different algorithms regardless of hardware or implementation
specifics. It is a fundamental concept in computer science for designing and selecting
optimal algorithms for large-scale data

Evaluation of how Asymptotic analysis can be used to assess the effectiveness of an

algorithm

The most common way to describe an algorithm's performance is the analysis of

asymptotic. This provides a good mathematical model and gives measures of the
performance against the size of the input. Hence, it is pretty important because it can
guarantee that the provisions for means an algorithm could behave with an extended size
of the input does come into cognizance with whoever one may work with, hard machine
configuration. In efficiency analysis, the correct real running time is considered but very
often ways it can manage larger and larger sizes of input end. Asymptotic notation at least
provides Big O, Omega, and Theta for measures of an upper bound or worst case, a lower
bound or best case, and an exact runtime or a tight bound, respectively. These notations
provide a way of abstraction by removing all the extra details about constant factors and
lower-order terms such that one gets a clean look at the performance of the algorithm in a
more generalized perspective. Probably for that reason, asymptotic analysis is such a
75
fundamental tool in the design and optimization of algorithms. It helps in essentially
deducing some of the most scalable and efficient algorithms that achieve certain tasks.

Asymptotic analysis makes it useful for predicting how the algorithm would perform once
the size of the input goes up-which is quite an important consideration nowadays, since
most applications have to process huge volumes of information. It could be a sorting
algorithm with a time complexity of O(n2), which will work just fine if the dataset is
small, but cannot bear practicability in case there is a dataset size in extreme amounts.
This could be so because, by nature, with augmented size, input increases quadratically.
On the contrary, the same algorithm, when running on linear time complexity O(n), can
be even done on an increase of such sizes. Asymptotic analysis per se does not involve
testing methodologies for trial-and-error performance since asymptotic analysis
guarantees theoretically the efficiency of an algorithm in the long run. This might be vital
in applications or real-time systems where performance is strict. It can also be used to
support the comparison of algorithms. Such is the case in comparing, say, a sorting
algorithm with O(n log n) against another with O(n2) in choosing between those for some
problem.

Another place where asymptotic analysis comes in handy is in optimizations that have to
be carried out; it shows where an algorithm can be improved for further efficiency. It also
allows the developers to eliminate redundant calculations or to use other data structures,
perhaps with better performance assurances. That could be understood to say of loops an
algorithm has a time O(n2) likely with room for improvements either through reductions
in a number of iterations or because of some much better technique can sort or find items
at a lesser cost. That is to say, such insight into the complexity of this algorithm and the
improvement with the increase of input will detect bottlenecks to be mitigated in
enhancing overall performance. Asymptotic analysis is consequently not only an issue
about present efficiency assessment but is also one seeking pathways leading to the
algorithm's possible improvement when the scalability question arises.
76
That's why asymptotic analysis gives the background on which one can be able to tell if
an algorithm will be viable for mega or giga scale operations. Consider a database
management system that ought to query millions of records. While an O(n2) algorithm
might just do okay with a few thousand records, the same algorithm can run unbearably
slow when dealing with several thousands or more records. Contrarily, a program of
either O(n log n) or O(n) displays reasonable execution time upon every increase in
dataset size. Asymptotic analysis, hence, allows one to predict the scalability of an
algorithm but also verify a solution practical for the problem at hand.

Another application can be done through doing asymptotic analysis for decision-making
in terms of when a number of algorithms may be proposed to choose. Consider having
two different types of algorithm solutions given for the present problem and possibly
compare their complexities with the use of asymptotic notation. That is, one will be of
O(n2) time complexity while the other one will be of O(n log n). Admittedly, in those
cases, the latter does come out very good but would have been from insights via
asymptotic analysis. This can enable the developer to choose such that, in essence, an
increase of size within an input would retain very good performance. That is quite useful
in such areas as machine learning since the performance and speed depend on the
algorithm chosen too.

The best that one could say about asymptotic analysis is that it provides a uniform and
reliable way of comparing performances across many varied platforms, languages, and
environments. That, however is abstraction which analysis lets them be able to compare
efficiency in the theoretical sense of algorithms. Whatever real hardware a program
happens to run on, whatever kind of system such homogeneity may be in, it will, for
example, enable the programmer to ground his decisions in deep properties of an
algorithm rather than in the whims of some particular system or hardware. This is
attributed to the fact that such uniformity makes asymptotic analysis a tool of top priority
77
in design and development, especially for systems that are envisioned to be deployed into
differing environments or upscaled with different sizes.

Finally, asymptotic analysis allows precognition of certain impending problems well in

advance of actual deployment. That is to say, a developer will be at an instant where one
can foresee such cases. Worst-case limits taken theoretically for algorithms, promising to
behave well under the normal conditions, come to be impossible to use only at just the
moment the size of the input stars growing. Thus, a foresight will be highly important in
laying a framework for developing robust systems with big data handling, not forgetting
doing well over growing demands during the running years ahead. For example,
asymptotic analysis will enable developers to create systems that are not only efficient
today but also will be for a long time to come-means their efficiency is not compromised
in the nearest future when the scales of both data and usage grow. The significant
asymptotic analysis gives based on the fact that in making any decision concerning the
optimality of the system, decisions concerning algorithms to be made should be from the
short-term perspective. (Agrawal, 2024)

Time complexity

Time complexity refers to the computational efficiency of an algorithm, specifically how

its execution time grows relative to the size of the input. It is a crucial concept in
algorithm design and performance analysis, as it helps predict how an algorithm will
perform as the input increases. Time complexity is typically expressed using Big-O
notation, which provides an upper bound on the algorithm's growth rate. This notation
abstracts away constant factors and lower-order terms to focus on the dominant term,
offering a high-level understanding of how the algorithm scales. For example, an
algorithm with a time complexity of O(n) will take time proportional to the input size,
while one with O(n2) will take time proportional to the square of the input size.
Understanding time complexity helps in selecting the most efficient algorithm for a
78
problem, especially as the size of the data grows. It enables developers to make informed
choices to optimize performance and avoid bottlenecks in large-scale applications.

How to measure the efficiency of an algorithm using time complexity

In this example, we use a simple linear search algorithm to find a target element in an
array. The algorithm iterates through the array sequentially, comparing each element to
the target. If it finds a match, it returns the index; otherwise, it completes the loop and
returns -1. The linear search algorithm is straightforward and serves as an excellent
example for understanding time complexity due to its predictable behavior.

79
The time complexity of the linear search algorithm is O(n), where n is the size of the
input array. This means that in the worst-case scenario, the algorithm will examine all n
elements to find the target. If the target is not present in the array, the algorithm will
traverse the entire array before concluding. This linear growth rate demonstrates how
execution time increases proportionally to the input size.

The [Link]() function is used to measure the execution time of the algorithm.
This provides a precise time measurement, allowing us to assess the algorithm's real-time
performance. While time complexity gives a theoretical growth rate, execution time gives
a practical perspective influenced by factors like hardware and implementation details.

If the array contains 7 elements (as in the example), the algorithm may perform up to 7
iterations in the worst case. For larger arrays, such as 1,000 or 10,000 elements, the
number of iterations and the execution time would increase proportionally. This
scalability demonstrates the linear relationship between input size and execution time,
which aligns with the O(n) time complexity.

Time complexity abstracts away specific hardware and environmental factors, focusing
on the growth rate of an algorithm. This allows developers to compare algorithms in a
standardized way. For example, if a binary search algorithm with O(log n) is used instead
of linear search, the performance difference becomes evident, particularly with larger data
sets.

Understanding time complexity is essential when selecting algorithms for applications

that handle large data. In scenarios where speed is critical, an algorithm with a lower time
complexity, like binary search, is preferred over linear search. However, simplicity and
implementation requirements might make O(n) algorithms acceptable for smaller data
sets. This balance between theoretical efficiency and practical usability underscores the

80
importance of analyzing time complexity in software development. (SitePoint Sponsors,
2024)

Space complexity

Space complexity refers to the amount of memory an algorithm uses during its execution,
relative to the size of its input. It includes both the fixed part, which is constant and does
not depend on input size (e.g., memory for variables, program code, and constants), and
the variable part, which depends on the input size (e.g., dynamic allocations, function
calls, and auxiliary data structures). Understanding space complexity helps in evaluating
how efficiently an algorithm uses memory resources, which is critical for applications
with limited memory or large-scale data processing. For example, a sorting algorithm like
Merge Sort has a space complexity of O(n) because it requires additional memory to store
temporary arrays during the sorting process, whereas Quick Sort has O(log n) due to its
in-place sorting and memory usage for recursive calls. Analyzing space complexity is
crucial for designing algorithms that balance memory usage with execution speed,
especially in systems with constrained resources like embedded devices or real-time
applications.

How to measure the efficiency of an algorithm using space complexity

81
The space complexity counts the total amount of memory that the algorithm may use,
which could be divided into fixed parts and variable parts. In the example above, the
fixed part is to store variables like sum and result that don't change however big the size
of the input array. Variable memory depends on the size of the input. Space utilized by
the input array-say, numbers-will be O(n), where n represents the total number of
elements in an array.

This function calculateSum uses a single variable sum for accumulating the total. Hence,
this will contribute to O(1) space. The input array numbers is passed to this function, and
no other data structure is used in this function. Thus, this function doesn't add any more

82
extra variable memory. Hence, the overall space complexity of the function calculateSum
is O(1). The overall program space complexity is O(n) due to the input array.

Here, the input size is a factor that decides how much memory is being used. Let there be
an array with 5 elements; the memory allocated to that array would be O(5). Now, when
the size of the input would scale up to 'n', then the quantity of memory used by that array
scales linearly:. It, therefore, portrays the contribution of variable input size to the overall
space complexity and how important it is to design the algorithm such that memory usage
is at a minimum in case large datasets arise.

Effective algorithms strive to minimize runtime usage of memory. Note here that, in the
above example, there were no new arrays used, neither any structure. So, very minor
space complexity. Of course, other algorithms-which would have to create and hold data
temporarily, think of Merge Sort-have space complexity scaling with the number of input
size O(n), though often an in-place variation will be worked out, for example, Quick Sort,
and generally with a space complex of O(log n).

Sometimes, it is the other way around-that when improving time, space complexity is
reduced. This code could process an element at a time-a streaming approach-thereby
reducing space to O(1), most likely at the cost of processing time. Given example does a
balance, it maintains the least possible space complexity without losing in its speed of
execution.

Space complexity is very important to understand in applications needing either to cope

with memory-constrained devices or handle a lot of data. Though most of them run on
almost negligible memory requirements, great amounts of memory are consumed in
83
practical scenarios dealing with image processing, AI/ML models, or operations over
databases. Therefore, analysis and optimization of space complexity ensure that resources
are used effectively for better throughput when the limitations are going to be very strict.
(TutorialKart, 2024)

84
References

Sumaiya Simran (2023). What is Bus Reservation System? Basic Guidebook. [online]

Available at:

[Link]

[Accessed 06 Jun. 2025].

‌StudySmarter UK. (2019). Stack in Data Structure: Python & Java | StudySmarter.
[online]

Available at:

[Link]
data-structure

[Accessed 06 Jun. 2025].

‌[Link]. (2022). TicketingHub. [online]

Available at:

[Link]
transportation

[Accessed 06 Jun. 2025].

85
‌Dominik Szahidewicz (2024). How to Create Test Cases for Login Page? [online]
[Link].

Available at:

[Link]

[Accessed 06 Jun. 2025].

‌Definition Guru (2024). Understanding the Imperative Definition: Concepts and

Applications - [Link]. [online] [Link].

Available at:

[Link]
applications

[Accessed 06 Jun. 2025].

‌Agrawal, T. (2024). Asymptotic analysis. [online] DEV Community.

Available at:

[Link]

[Accessed 06 Jun. 2025].

‌SitePoint Sponsors (2024). Time Complexity of Algorithms — SitePoint. [online]

[Link].

Available at:

[Link]

86
[Accessed 06 Jun. 2025].

‌TutorialKart. (2024). Space Complexity of an Algorithm - Types, Graph, Examples.

[online]

Available at:

[Link]

[Accessed 06 Jun. 2025].

87