Internal verification of assessment decisions – BTEC Higher Nationals (RQF)

INTERNAL VERIFICATION – ASSESSMENT DECISIONS (Single Student)

Programme Title: Pearson HND in Computing

Unit Number and Title: Unit 19: Data Structures & Algorithms

Assessor Name: Mr. Earnest Bosco Internal Verifier Name:

Assignment title: Colombo Shoe Fair

Name of student Submission Grade the List the learning outcomes State why the assessment decision is
Type Assessor has Assessment and grading criteria where inaccurate.
(First, awarded. Decision inaccurate decisions have
Resubmission, Accurate been made *If an inaccurate decision is recorded the
Retake) (Y/N) Internal Verifier must recommend actions
(Resubmissio detailing the issues to be addressed. The
n and retake Assessor and the Internal Verifier must then
must be confirm that the action has been undertaken
capped at a before assessment decisions are issued to the
Pass) student.

BTEC Internal Verification of Assessment Decisions Template (Single student)

Issue Date: Jan 2024
INTERNAL VERIFIER CHECKLIST Y/N

Has the student and the Assessor confirmed the authenticity of the evidence?

Is there evidence of collusion or plagiarism? The work submitted for assessment has been carried out without assistance
other than that which is acceptable according to the rules of the specification. The evidence submitted for this assignment is
student’s own. The student has clearly referenced any sources and any artificial intelligence (AI) tools used in the work.

Is the assessor feedback to the student appropriate and constructive to each student? Provide comments below.
● Points out strengths and areas for improvement.
● Linked to relevant learning outcomes and assessment criteria.
● Clear as to why the student did not achieve higher grades.
● Identify opportunities for improved performance in future assignments.

GENERAL COMMENTS

2
Any actions required must be reviewed across the whole cohort.

Target Date for

Action Required Date Action Completed
Completion

I confirm that the assessment decisions are accurate, there is no evidence of assessment malpractice and any action points have been addressed and
completed in respect of the whole cohort. I declare the work submitted for assessment has been carried out without assistance other than that which is
acceptable according to the rules of the specification. The evidence submitted for this assignment is student’s own. The student has clearly referenced
any sources and any artificial intelligence (AI) tools used in the work.

Internal Verifier signature Date

Assessor signature Date

3
Higher Nationals - Summative Assignment Feedback Form

Student Name/ID
Unit Title Unit 19: Data Structures & Algorithms

Assignment Number 01 Assessor Mr. Earnest Bosco

06-October-2025 Date Received 1st
Submission Date submission
Date Received 2nd
Re-submission Date submission
Assessor Feedback:

*Please note that constructive and useful feedback should allow students to understand:

a) Strengths of performance
b) Limitations of performance
c) Any improvements needed in future assessments

Feedback should be against the learning outcomes and assessment criteria to help students
I certify that to the best of my knowledge the evidence submitted for this assignment is the
student’s own. The student has clearly referenced any sources and any artificial intelligence
(AI) tools used in the work. I have not solely used AI to grade the student’s work.

Resubmission Feedback:
*Please note resubmission feedback is focussed only on the resubmitted work

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.
STUDENT ASSESSMENT SUBMISSION AND DECLARATION
When submitting evidence for assessment, each student must sign a declaration confirming that the
work is their own.
Student name: Assessor name: Mr. Earnest Bosco

Issue date: 16-July- Submission date: 06-October- Submitted on:

2025 2025

Programme: HND in Computing

Unit: Unit 19: Data Structures & Algorithms
Assignment number and title: Assignment 01 Colombo Shoe Fair

Plagiarism

Plagiarism is a particular form of cheating. Plagiarism must be avoided at all costs and students who
break the rules, however innocently, may be penalised. It is your responsibility to ensure that you
understand correct referencing practices. As a university level student, you are expected to use
appropriate references throughout and keep carefully detailed notes of all your sources of materials
for material you have used in your work, including any material downloaded from the Internet. Please
consult the relevant unit lecturer or your course tutor if you need any further advice.

Student Declaration

Student declaration
I certify that the assignment submission is entirely my own work and I fully understand the
consequences of plagiarism. I declare that the work submitted for assessment has been
carried out without assistance other than that which is acceptable according to the rules of
the specification. I certify I have clearly referenced any sources and any artificial

5
intelligence (AI) tools used in the work. I understand that making a false declaration is a
form of malpractice.

Student signature: Date:

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

1. The font size should be 12 point, and should be in the style of Times New
Roman.
2. Use 1.5 line spacing. Left justify all paragraphs.
3. Ensure that all the headings are consistent in terms of the font size and font
style.

6
 4. 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.
5. Use word processing application spell check and grammar check function to
help editing your assignment.

Important Points

1. It is strictly prohibited to use text boxes 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.
2. Avoid using page borders in your assignment body.
3. Carefully check the hand in date and the instructions given in the assignment.
Late submissions will not be accepted.
4. Ensure that you give yourself enough time to complete the assignment by the due
date.
5. Excuses of any nature will not be accepted for failure to hand in the work on
time.
6. You must take responsibility for managing your own time effectively.
7. 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.
8. Failure to achieve at least PASS criteria will result in a REFERRAL grade.
9. Non-submission of work without valid reasons will lead to an automatic RE
FERRAL. You will then be asked to complete an alternative assignment.
10. 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.
11. 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

7
 the course.

Submission Guidelines
 Start your answers from the end of the assignment brief. Do not use a new Word
document.
 You must submit only two documents:
1. Completed assignment in Word format.
2. Turnitin similarity report in PDF format.
 File Renaming Format:
For the Assignment Word document:
 Format: Unit No_Unit Name_Assignment_Student ID_Student Name
 Example: Unit 19_Data Structures_Assignment_02002000_M K C Perera
For the Turnitin PDF report:
 Format: Unit No_Unit Name_Turnitin Report_Student ID_Student Name
 Example: Unit 19_Data Structures_Turnitin Report_02002000_M K C Perera
 Do not submit ZIP files.
 Late submissions will not be accepted for any reason.
 Submission deadlines will not be extended under any circumstances.
 Only LMS submissions are accepted. Submissions via WhatsApp, Email, or any other
channel will not be accepted.
Please check your LMS access in advance.
 If you face any issues with the submission link or LMS, you must inform the Academic
Admin Department at least 3 working days before the submission deadline.

8
Unit 19: Data Structures & Algorithms

Assignment Brief

Programme Title HND in Computing

Student Name/ID Number

Unit Number and Title Unit 19: Data Structures & Algorithms

Academic Year 2025

Unit Tutor Mr. Earnest Bosco

Assignment Title Colombo Shoe Fair

16-July-2025
Issue Date

Submission Date 06-October-2025

Submission Format

Submission Guidelines

1. Use the cover page provided in the previous page as your cover sheet for the
assignment you will be submitting and ensure that all the details are accurately filled.
All assignments should have the submitted with the above cover page which is
properly filled.
2. Attach the assignment brief as the first section of your assignment (Including the
assignment criteria, summative feedback from and grading rubric).
3. Use an appropriate word processing software to develop your assignment.
4. Use A4 size pages for your assignments.
5. Use font size 11 if you are using Open Sans or Arial font and font size 12 if you are
using Times New Roman font for the body of your assignment.
6. Use font size 13 (bold) if you are using Open Sans or Arial font and font size 14
(bold) if you are using Times New Roman font for Main headings. For Sub-
Headings use font size 12 (bold) if you are using Open Sans or Arial font and font

9
 size 12 (bold) if you are using Times New Roman.
7. Use black text on a white background. Avoid coloured backgrounds or text in a
colour other than black, unless you have special permission to use them.
8. Use 1.5 line spacing and 2.53 cm (1”) wide margins on all sides.
9. Justify your work (Ctrl+J).
10. Insert a footer on each page (except the title page) using font size 10 if you are using
Times New Roman and font size 8 if you are using Open Sans or Arial font. Include
the following details in the footer, Full Name, Student ID, Unit and the Page Number.
11. Avoid using page borders in your assignment body.

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.

Transferable skills and competencies developed

Computing-related cognitive skills

● Computational thinking (including its relevance to everyday life)

● Understanding of the scientific method and its applications to problem-solving

● Demonstrate knowledge and understanding of essential facts, concepts, principles,

and theories relating to computing and computer applications.

● Use such knowledge and understanding in the modelling and design of computer-
based systems for the purposes of comprehension, communication, prediction, and

10
 the understanding of trade-offs.

● Recognise and analyse criteria and specifications appropriate to specific problems,

and plan strategies for their solution.

● Analyse the extent to which a computer-based system meets the criteria defined for
its current use and future development.

● Deploy appropriate theory, practices and tools for the design, implementation, and
evaluation of computer-based systems.

Computing-related practical skills

● The ability to specify, design and construct reliable, secure and usable computer-
based systems.

● The ability to evaluate systems in terms of quality attributes and possible trade-offs
presented within the given problem.

● The ability to deploy effectively the tools used for the construction and
documentation of computer applications, with particular emphasis on understanding
the whole process involved in the effective deployment of computers to solve
practical problems.

● The ability to critically evaluate and analyse complex problems, including those
with incomplete information, and devise appropriate solutions, within the
constraints of a budget.

Generic skills for employability

● Critical thinking; making a case; numeracy and literacy.

● Self-awareness and reflection; goal setting and action-planning; independence and

adaptability; acting on initiative; innovation and creativity.

● Interaction: reflection and communication

Contextual awareness e.g. the ability to understand and meet the needs of individuals,
business and the community, and to understand how workplaces and organisations
are governed

11
Vocational scenario

“Colombo Shoe Fair” is an annual event held in Sri Lanka, attracting thousands of shoe
lovers each year. Due to the growing demand and high visitor turnout, managing the crowd
efficiently has become a challenge. To address this, the management team of the Colombo
Shoe Fair has proposed an online booking system for visitors. Through this system,
customers can browse and book footwear items before visiting the fair.

All available items are displayed as a menu to the user, and each user can reserve any
number of items from the table below. Once the booking is completed, the system will
generate a unique order number for each booking, along with the total bill for the order.

For payments, the management has introduced two options:

1. Online Payment – A 3% processing fee will be added to the total bill.

2. On-site Payment – Visitors can pay in person upon arrival.

If a user chooses to pay on-site, they are allowed to add more items to the same order
number during their visit. It needs to have the facility to search any order with detailed
information via the given order number in the system. Once all items are finalized, the total
bill will be updated accordingly and payment can be made.

At the end of the Shoe Fair, the system should be able to calculate the total revenue
generated from all bookings and purchases.

Below is the list of items available at the Shoe Fair:

Item Code Item Unit Price (LKR)

S001 Men’s Leather 5,500.00

12
 Shoes
S002 Women’s Heels 4,000.00
S003 Casual Sneakers 3,200.00
S004 Children’s Sandals 2,000.00
S005 Running Shoes 4,800.00
S006 Flip-Flops 1,200.00
Note: Assume only these items are available for the purpose of this implementation. If
needed you could hypothetically increase the use case but the core ideas need to remain
same.

Assignment activity and guidance

- Report -

You will produce a report that will explain the purpose, operation, and performance of a
range of specified data structures and algorithms. You should make extensive use of
concrete examples to support your report.

Your report should include a discussion of standard data types and algorithms including:

1.1. A design specification for a range of data structures, created in the software of your
choice, that explains the valid operations that can carried out on the structures. The
data structures should reflect those that you intend to use in the Colombo Shoe
Fair solution.

1.2. An explanation of the operations of a memory stack and how it is used to

implement function calls in a computer.

1.3. An illustration, with examples, of a concrete data structure for a ‘first in first out’
(FIFO) queue

1.4. A comparison of the performance of any two sorting algorithms

1.5. An analysis of the operation of two network shortest-path algorithms with an

13
 example of each. You must use illustrations to show how these algorithms operate.

Your report will go on to discuss the principles, design and implementation of abstract
data types (ADTs), including:

1.6. A specification of the ADT used for a software stack using an imperative
declaration.

1.7. An examination of the advantages of encapsulation and information-hiding when

using an ADT

1.8. A discussion of the view that imperative ADTs are the basis for object orientation.
You must include a justification of your view.

Your report should then assess the effectiveness of the data structures and algorithms you
selected, including:

1.9. A discussion of how asymptotic analysis can be used to assess the effectiveness of
an algorithm.

1.10. A determination of two ways which the efficiency of an algorithm can be measured.
You must illustrate your answer with an example.

1.11. An interpretation what a ‘trade-off’ is when specifying an ADT. You must use an
example to support your answer.

1.12. An evaluation of three benefits of using implementation independent data

structures.

You are to design and implement a programmed solution for the requirements of the
Colombo Shoe Fair scenario. You are to use a range of complex in-memory data
structures and algorithms and the choice of these is up to you; however, you must ensure
that the client requirements are met. There should not be any data storage in either files
or databases.

You should produce a written programming report that implements the data structure and
algorithms to be used in the solution Colombo Shoe Fair. Your programming report
should further include:

1.13 Algorithms designed in the design format (pseudocode, flowcharts) of your choice.

14
1.14 The implemented program (final working version) should in format suitable to be
executed and assessed for functionality. Here no need to develop separate user
interfaces and command line/terminal execution (program could run via command
line) is enough.

This could be as project/solution files or final compiled executable. If this is not

possible, then a video demonstration of the working program or detailed screen
captures demonstrating all working functionality should be provided.

1.15 Annotated/commented source produced in the format created by the programming

language selected (for example, .py, .cs, .vb, .txt, .java files)

1.16 An implementation of error-handling and a report of test results, with evidence

1.17 A demonstration of how the implementation of the ADT/algorithm solves the

problem defined by the Colombo Shoe Fair scenario.

1.18 A critical evaluation of the complexity of the implemented ADT/algorithms.

You should support any points you make in the programming report with well-chosen
examples from the existing scenario and any associated documentation.

Make sure you have satisfied all relevant criteria in LOs, if exists, other than above, in
your report.

Recommended Resources

Websites

www.codingninjas.com Coding Ninjas “Types of algorithms and their uses” (Article)

www.geeksforgeeks.org GeeksforGeeks “Most important type of algorithms”
(General reference)

15
 www.naukri.com Naukri Learning “Tree data structure: types, properties, and
applications” (Article)

object-oriented-python.github.io Object-orientedProgramming in Python for

Mathematicians “Abstract data types” (Training)

www.overturetool.org Overture Tool “The VDM specification language” (General

reference)

sourcemaking.com SourceMaking “Design patterns” (General reference)

www.tutorialspoint.com Tutorials Point “Data structures – asymptotic analysis”
(Training)

Journals and articles

Adadi, A. (2021) 'A survey on data‐efficient algorithms in big data era', Journal of
Big Data, 8 (24). Available at: https://doi.org/10.1186/s40537-021-00419-9.

Dourish, P. (2016) 'Algorithms and their others: Algorithmic culture in context', Big
Data & Society, pp. 1–11. Available at: https://doi.org/10.1177/2053951716665128.

Fahmi, H., Zarlis, M., Nababan, E.B. and Sihombing, P. (2020) 'Implementation of
the Greedy Algorithm to determine the nearest route search in distributing food
production', The 6th International Conference on Software Engineering & Computer
Systems, 769. Available at: https://doi.org/10.1088/1757-899X/769/1/012005.

Guttag, J. (1977) 'Abstract data types and the development of data structures',
Communications of the Association for Computing Machinery, 20 (6), pp. 396–404.
Available at: https://doi.org/10.1145/359605.359618.

Mala, F.A. and Ali, R. (2022) 'The Big-O of mathematics and computer science',
Journal of Applied Mathematics and Computation, 6 (1), pp. 1–3. Available at:
https://doi.org/10.26855/jamc.2022.03.001.

Tripathy, B.K. and Gantayat, S.S. (2012) 'On the implementation of data structures
through theory of lists', International Journal of Information Technology
Convergence and Services, 2 (4). Available at:
https://doi.org/10.5121/ijitcs.2012.2404.

Wang, Y., Tan, X., Ngolah, C.F. and Sheu, P. (2010) 'The formal design models of a

16
 set of abstract data types (ADTs)', International Journal of Software Science and
Computational Intelligence, 2 (4), pp. 72–100. Available at:
https://doi.org/10.4018/jssci.2010100106.

Textbooks

Aho, A.V., Hopcroft, J.E. and Ullman, J.D. (1982) Data Structures and Algorithms
(Addison-Wesley Series in Computer Science and Information). London: Pearson.

Brass, P. (2008) Advanced Data Structures. Cambridge: Cambridge University Press.

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2009) Introduction to
Algorithms. 3rd Ed. Cambridge, Massachusetts: MIT Press.

Karumanchi, N. (2011) Data Structures and Algorithms Made Easy: Data Structures
and Algorithmic Puzzles. 2nd Ed. Bombay: CareerMonk Publications.
Sedgewick, R. and Wayne, K. (2011) Algorithms. 4th Ed. London: Addison Wesley.

Learning Outcomes and Assessment Criteria

Pass Merit Distinction

LO1 Examine abstract data types, concrete data structures
and algorithms
P1 Create a design M1 Illustrate, with an D1 Analyse the operation,
specification for data example, a concrete data using illustrations, of two
structures, explaining the structure for a First in First network shortest path
valid operations that can out (FIFO) queue. algorithms, providing an

17
be carried out on the M2 Compare the example of each.
structures. performance of two
P2 Determine the sorting algorithms.
operations of a memory
stack and how it is used to
implement function calls in
a computer.
LO2 Specify abstract data types and algorithms in a
formal notation
P3 Specify the abstract M3 Examine the D2 Discuss the view that
data type for a software advantages of imperative ADTs are a basis
stack using an imperative encapsulation and for object orientation offering
definition. information hiding when a justification for the view.
using an ADT.
LO3 Implement complex data structures and algorithms
P4 Implement a complex M4 Demonstrate how the
ADT and algorithm in an implementation of an D3 Critically evaluate the
executable programming ADT/algorithm solves a complexity of an implemented
language to solve a well- well-defined problem. ADT/algorithm.
defined problem.
P5 Implement error
handling and report test
results.
LO4 Assess the effectiveness of data structures and
algorithms
P6 Discuss how asymptotic M5 Interpret what a trade- D4 Evaluate three benefits of
analysis can be used to off is when specifying an using implementation
assess the effectiveness of ADT, using an example to independent data structures.
an algorithm. support your answer.

P7 Determine two ways in

which the efficiency of an
algorithm can be measured,

18
illustrating your answer
with an example.

19
Contents
Plagiarism.........................................................................................................................................4

Unit 19: Data Structures & Algorithms.............................................................................................7

Sedgewick, R. and Wayne, K. (2011) Algorithms. 4th Ed. London: Addison Wesley...................13

Activity 1.........................................................................................................................................16

Introduction to Data Structures....................................................................................................16

Arrays........................................................................................................................................17

Linked Lists..............................................................................................................................22

Stacks........................................................................................................................................29

Queues.......................................................................................................................................33

Summary of chosen data structures for implementation...........................................................37

Concept of memory stack in computing.......................................................................................39

Function call mechanism..............................................................................................................41

Push operation for parameters and return addresses.................................................................41

Pop operation for returning control...........................................................................................42

Example of Nested Function Calls Using a Stack........................................................................42

Relevance of stack operations in program execution...................................................................43

Activity 2.........................................................................................................................................44

Specification of Abstract Data Type (ADT) for a Stack..............................................................44

Definition of an ADT................................................................................................................44

Imperative specification for stack.............................................................................................46

20
 Example of ADT stack in pseudo-code....................................................................................49

Application of stack ADT in Colombo Shoe Fair.....................................................................51

Activity 3.........................................................................................................................................51

System requirements from scenario.............................................................................................51

Algorithm design..........................................................................................................................52

Pseudocode for booking process...............................................................................................52

Flowchart of customer booking....................................................................................................57

Algorithm for order search by order number...............................................................................57

Algorithm for revenue calculation...............................................................................................58

A) Batch computation at end of event (simple and robust)......................................................59

B) Incremental (running) revenue update (efficient during operations)...................................59

C) Reconciliation helper (optional safety)................................................................................60

Program implementation..............................................................................................................61

Programming language chosen.................................................................................................61

Demonstration of functions..........................................................................................................72

System Launch and Main Menu...............................................................................................72

Displaying the Catalog..............................................................................................................73

Creating a New Order...............................................................................................................73

Adding Items to an Order (Step 1)............................................................................................73

Adding Items to an Order (Step 2)............................................................................................74

Searching for an Existing Order................................................................................................74

Checking Out an Order.............................................................................................................75

Calculating Total Revenue........................................................................................................75

Invalid Order Search.................................................................................................................75

Adding Items After Checkout...................................................................................................76

Invalid Quantity Input...............................................................................................................76

Adding Items to Non-ONSITE Orders.....................................................................................77

21
 Re-checkout of Already Paid Orders........................................................................................77

Error Handling and Test Results..................................................................................................77

Error handling methods in program..........................................................................................77

Handling duplicate orders.........................................................................................................78

Preventing empty input submissions.........................................................................................80

Testing approach..........................................................................................................................80

Test case design (black-box / white-box).................................................................................80

Evidence of testing....................................................................................................................81

Expected vs Actual Output.......................................................................................................81

Screenshots of execution...........................................................................................................82

Console output logs...................................................................................................................87

Summary of system reliability.....................................................................................................88

Activity 4.........................................................................................................................................88

Introduction to asymptotic analysis..............................................................................................88

Big-O notation explained.............................................................................................................89

Best Case, Worst Case, and Average Case...............................................................................89

Example: searching order in list (O(n))....................................................................................90

Example: adding item to booking (O(1))..................................................................................91

Relevance to Colombo Shoe Fair algorithms...............................................................................92

Introduction to algorithm efficiency.............................................................................................94

Time complexity as efficiency measure....................................................................................94

Bubble sort vs binary search........................................................................................................94

Space complexity as efficiency measure..................................................................................95

Trade-offs between time and space...........................................................................................96

Summary of efficiency analysis...................................................................................................97

References........................................................................................................................................98

22
Activity 1

Introduction to Data Structures

Data structures form the backbone of computer science and software development, as they
determine how data is logically organised and physically stored in memory. They provide a
systematic way of accessing, managing, and modifying data, enabling efficient algorithm
execution and problem solving (Aho, Hopcroft and Ullman, 1982). At their core, data structures
act as a bridge between raw data and the algorithms that operate on them, ensuring that
computational tasks can be performed effectively even on large datasets.
One of the primary reasons for studying data structures is their direct influence on the efficiency
of algorithms. A poorly chosen data structure can lead to excessive time consumption and wasted
memory resources. For instance, searching for an item in an unsorted array requires a linear scan
with a time complexity of O(n), whereas using a binary search tree can reduce the same operation
to O(log n) (Cormen et al., 2009). Similarly, queues are designed to manage processes in a first-in,
first-out (FIFO) manner, making them ideal for systems such as CPU scheduling and network
packet handling (Sedgewick and Wayne, 2011).
Data structures are broadly classified into two types: abstract data types (ADTs) and concrete data
structures. Abstract data types describe the behaviour of a structure what operations it supports
without specifying the internal implementation. For example, a stack ADT defines the operations
push, pop, and peek, but it can be implemented using either an array or a linked list. Concrete data
structures, on the other hand, are the actual implementations that define how these operations are
executed in memory (Guttag, 1977). This separation allows developers to focus on problem-
solving while leaving flexibility for implementation choices.
The importance of data structures also extends beyond efficiency to software quality and
reliability. Well-designed data structures improve readability, maintainability, and scalability of
software systems. Encapsulation, which hides internal implementation details of a data structure,
ensures that users interact only with defined operations, reducing errors and enhancing modularity
(Wang et al., 2010). In addition, the use of reusable data structures supports code reusability
across different applications, which is especially important in large-scale system development.
From a real-world perspective, data structures are essential in nearly every modern computing
application. Search engines like Google use advanced tree and graph structures to index billions of

23
web pages. Social media platforms rely on hash tables and graphs to model
user interactions and recommend connections. Even simple mobile applications
use stacks to manage function calls and queues for handling background tasks (Mala and Ali,
2022). This highlights the universality and necessity of mastering data structures for professional
computing practice.
In the context of the Colombo Shoe Fair scenario, the correct use of data structures will determine
the success of the booking and billing system. For example:
 An array can be used to store the static shoe catalogue with item codes and prices.
 A queue can represent booking requests as they arrive, ensuring fair order processing.
 A stack can manage temporary system tasks such as function calls during order updates.
 A linked list can store dynamic customer orders, allowing insertion of additional items
when on-site payments are chosen.
By aligning the system requirements with suitable data structures, the solution will not only meet
functional needs but also ensure scalability, accuracy, and speed of operations. Thus, data
structures are not simply a theoretical subject but a practical necessity that underpins the reliability
and effectiveness of computing systems (Brass, 2008).

Introduction to Colombo Shoe Fair

The Colombo Shoe Fair is one of Sri Lanka’s most popular annual events, attracting thousands of
visitors who come to explore and purchase a wide range of footwear. With the growing number of
participants and the demand for efficient customer service, the organisers face a major challenge
in managing bookings, payments, and overall crowd flow. Traditional manual systems are no
longer sufficient because they struggle with delays, errors, and difficulty in tracking orders at
scale. To overcome these issues, the management has proposed an online booking and order
management system that makes use of appropriate data structures and algorithms to handle
customer interactions smoothly and reliably. In this system, customers can browse a fixed
catalogue of shoes, reserve any number of items, and choose their preferred payment option:
either online with a 3% processing fee or on-site during the event. For on-site payments, the
system must also allow customers to add additional items to the same order, and staff should be
able to search orders quickly using a unique order number. At the end of the fair, the organisers
need to calculate the total revenue generated from all confirmed bookings and purchases. To meet
these requirements, the correct choice of data structures and algorithms plays a vital role. Arrays

24
can manage the fixed product catalogue, while linked lists can dynamically
store customer orders with flexibility for modifications. Stacks and queues can
manage temporary selections and booking sequences, ensuring efficiency and fairness. Hash maps
provide constant-time search for order details, while sorting and searching algorithms ensure
scalability when the system handles many transactions. By combining these structures effectively,
the solution ensures fast access, reliable updates, and accurate reporting.

Arrays

Characteristics of Arrays
An array is one of the most fundamental linear data structures in computer science. It is defined as
a finite, ordered collection of homogeneous elements stored in contiguous memory locations
(Cormen et al., 2009). The fixed structure of arrays makes them predictable and efficient for direct
data access, but less flexible when compared to dynamic structures such as linked lists.

The key characteristics of arrays are as follows:

1. Fixed Size
The size of an array must usually be declared at the time of creation. Once defined, this
size cannot be altered during program execution. This makes arrays efficient in memory
allocation but limits their flexibility when the number of elements is not known in advance
(Karumanchi, 2011).

2. Homogeneous Data Type

All elements in an array must belong to the same data type, such as integers, characters, or

25
 floating-point values. This ensures uniformity in memory allocation
and operations, reducing complexity during access and manipulation
(Brass, 2008).

3. Contiguous Memory Allocation

Arrays store elements in sequential memory locations. This contiguous storage allows the
computer to calculate the address of any element directly using the formula:

Address of element i=Base Address+(i× ¿ Element )

This property provides arrays with constant-time access, i.e., O(1) for reading or updating any
element (Mala and Ali, 2022).

4. Index-Based Access
Each element in an array is associated with a unique index, usually starting from zero in
most programming languages. This indexing allows fast random access, where elements
can be retrieved or updated directly without traversal (Sedgewick and Wayne, 2011).

5. Static Nature
Since arrays are static in size, they are less suitable for situations where data grows or
shrinks frequently. In such cases, dynamic structures like linked lists or dynamic arrays
(e.g., Python lists, Java ArrayLists) are more effective.

6. Efficient Traversal but Costly Insertion/Deletion

Arrays allow efficient traversal of elements in O(n) time. However, insertion or deletion at
arbitrary positions requires shifting of elements, which increases the time complexity to
O(n) for those operations. This trade-off highlights the need to use arrays in contexts
where frequent insertions or deletions are not required (Aho, Hopcroft and Ullman, 1982).

In summary, arrays are best suited for scenarios where the number of elements is known in
advance, and fast, direct access to data is required. However, they are not ideal for applications
requiring frequent dynamic changes in data size.

Operations on Arrays
Arrays allow several fundamental operations. These operations are crucial for data manipulation
and form the building blocks of more complex algorithms.

26
(a) Insertion
Insertion refers to adding a new element at a specific index in the array.

 If the insertion is at the end, it is efficient (O(1)).

 If it is at the beginning or middle, all subsequent elements must be shifted, making the
complexity O(n).

(b) Deletion
Definition: Deletion removes an element from a specific index in the array.

 After deletion, all subsequent elements are shifted one position to the left.

 The time complexity is O(n) in the worst case.

27
(c) Update
Definition: Updating replaces the value at a specific index with a new one.

 Since arrays allow direct access using indices, this operation is highly efficient with O(1)
complexity.

(d) Traversal
Definition: Traversal means accessing each element of the array sequentially, usually to display
or process them.

 Since every element is visited once, the time complexity is O(n).

28
Use Case in Colombo Shoe Fair
In the Colombo Shoe Fair scenario, an array is particularly suitable for managing the fixed
catalogue of footwear items. Since the list of items is predetermined and does not change
frequently, arrays provide an efficient way to store and access the product details such as item
code, item name, and price.

Why is an Array suitable in this scenario,

1. Fixed Number of Items – The catalogue contains only six products (S001–S006). Arrays
are ideal because the size is small and constant, eliminating the need for dynamic
structures such as linked lists (Karumanchi, 2011).

2. Fast Lookup – Customers browsing the catalogue can instantly retrieve details of an item
by its index in the array. This direct access (O(1)) is important for a fast-booking system
(Cormen et al., 2009).

3. Traversal for Display – When the system displays the full list of shoes to customers,
traversal through the array (O(n)) ensures that all items are presented efficiently.

4. Static Storage – Since product data like name and price does not change during the fair,
the static nature of arrays aligns with the system’s requirements (Brass, 2008).

29
This allows the system to:

 Display the catalogue to users.

 Retrieve price and item name directly using the index.

 Calculate order totals by accessing prices through their array positions.

Inde Item Code Item Name Price (Rs.)

x

0 S001 Men’s Leather 5,500

Shoes

1 S002 Women’s Heels 4,000

2 S003 Casual Sneakers 3,200

3 S004 Children’s Sandals 2,000

4 S005 Running Shoes 4,800

5 S006 Flip-Flops 1,200

This will visually reinforce the explanation by showing how each product is mapped to an index.

30
Linked Lists

Singly Linked List

A singly linked list is a linear data structure where elements, called nodes, are connected
sequentially through pointers. Each node contains a data field for storing information and a
pointer that references the next node in the sequence (Brass, 2008). Unlike arrays, which depend
on contiguous memory allocation, linked lists use non-contiguous memory, allowing nodes to be
created dynamically as needed. The final node points to null, marking the end of the list (Cormen
et al., 2009).

This structure is highly flexible because it can grow or shrink at runtime, making it useful when
the number of elements is uncertain. Traversing a singly linked list requires moving step by step
from the head node until the end, unlike arrays that allow direct indexing. While insertion and
deletion are efficient, particularly at the start, random access is slower compared to arrays
(Karumanchi, 2011). In practical systems such as the Colombo Shoe Fair booking system, a singly
linked list can manage dynamic customer orders efficiently, allowing items to be added or
removed without the overhead of shifting elements.

Characteristics of a Singly Linked List

 Dynamic size: Nodes can be inserted or deleted at runtime without reallocating or shifting
elements, unlike arrays.

 Sequential access: Elements must be traversed in order from the head node; random access
is not possible (Karumanchi, 2011).

 Efficient insertions and deletions: Adding or removing nodes, especially at the beginning,
is more efficient (O(1)) compared to arrays where shifting is required.

31
  Memory overhead: Each node requires extra memory for the pointer
field, making it less space-efficient than arrays (Aho, Hopcroft and
Ullman, 1982).

Basic Operations

1. Insertion – At the beginning, end, or a specific position.

2. Deletion – Remove a node by value or position.

3. Traversal – Visit each node sequentially starting from the head.

32
Doubly Linked List

33
A doubly linked list is a linear data structure where each node contains three fields: a data
element, a pointer to the next node, and a pointer to the previous node (Brass, 2008). Unlike a
singly linked list, which only allows traversal in one direction, a doubly linked list supports
movement both forwards and backwards, offering greater flexibility. Nodes are not stored in
contiguous memory, and the list begins with a head node and ends with a tail node pointing to null
(Cormen et al., 2009).

The main advantage of a doubly linked list is that insertion and deletion operations are more
efficient in both directions, as there is no need to traverse from the start to reach a previous
element. However, it consumes more memory than a singly linked list due to the additional
pointer field (Aho, Hopcroft and Ullman, 1982). In the context of the Colombo Shoe Fair booking
system, a doubly linked list could be applied for order management where both forward and
backward traversal of items is useful, for example when reviewing or modifying customer
bookings in sequence.

Operations on Linked Lists

Linked lists allow dynamic manipulation of data through operations such as insertion, deletion,
and searching. These operations are fundamental to their flexibility and efficiency compared to
arrays. Unlike arrays, linked lists do not require contiguous memory, making insertions and
deletions less costly in terms of shifting elements, though traversal is required to access nodes
sequentially (Cormen et al., 2009).

34
Insertion
Insertion in the linked list refers to creating a new node and placing it at a
specific position.

 At the beginning, insertion is O(1) because the new node is linked directly to the head.

 At the end or a specific index, traversal is required, making it O(n) (Karumanchi, 2011).

Deletion

Deletion removes a node either from the beginning, end, or a given position.

 Deleting the first node is O(1), as the head pointer simply shifts.

 Deleting a node elsewhere requires traversal to find the preceding node, resulting in O(n)
complexity (Brass, 2008).

35
Search

Searching in a linked list involves traversing nodes sequentially until the desired element is found
or the list ends.

 Time complexity is O(n) since, in the worst case, every node must be visited (Aho,
Hopcroft and Ullman, 1982).

36
Insertion, deletion, and searching are core linked list operations. They demonstrate the trade-off
between flexibility and performance. While insertion and deletion are more efficient than arrays
due to the absence of shifting, searching requires sequential traversal, making it slower for
random access. In the context of the Colombo Shoe Fair, linked lists are ideal for handling
dynamic customer orders, where items may be frequently added or removed.

Example for Orders in the Fair

In the Colombo Shoe Fair booking system, a singly linked list can be used to represent a
customer’s order where the number of items is not fixed in advance. Each item in the order can be
stored as a node, containing the item code, name, price, and a pointer to the next item in the list.
This structure allows the system to dynamically add new items if a customer selects more

37
products later, especially when paying on-site, without needing to shift existing
elements as would be required in an array (Cormen et al., 2009).

For instance, when a customer initially books a pair of Casual Sneakers (S003), a node is created
with the details of this item. If the same customer later adds Running Shoes (S005) and Flip-Flops
(S006), new nodes are created and appended to the linked list, maintaining the sequence of
purchases. Traversing this list would allow the system to calculate the total bill and display all
items in the order. The dynamic nature of linked lists makes them especially suitable in this
scenario, as it mirrors the flexible behaviour of real customer shopping patterns (Karumanchi,
2011).

38
Output

39
This example demonstrates how linked lists can dynamically manage customer
bookings. If new items are purchased, additional nodes are created and linked to
the existing order. Similarly, if an order is modified or cancelled, nodes can be removed without
re-structuring the entire system. This makes linked lists more adaptable than arrays for handling
variable-length customer orders in the fair.

Stacks

Definition and Structure

A stack is a linear data structure that follows the principle of Last-In, First-Out (LIFO), meaning
that the most recently added element is the first one to be removed. It is often compared to a stack
of plates, where the plate placed on the top is the first to be taken off. This structure is widely used
in computing for tasks such as function call management, expression evaluation, and undo
operations in software applications (Cormen et al., 2009).

The structure of a stack consists of a collection of elements with two primary operations. The push
operation inserts an element onto the top of the stack, while the pop operation removes the top
element. An additional operation, known as peek or top, allows the retrieval of the current top
element without removing it (Karumanchi, 2011). The LIFO principle ensures that operations are
restricted to one end of the structure, making it highly predictable and simple to implement.

40
Stacks can be implemented using either arrays or linked lists. An array-based
stack provides constant-time (O(1)) access to elements but has a fixed size,
which can limit flexibility. A linked list implementation, on the other hand, allows the stack to
grow dynamically without a predefined size, though it requires additional memory for storing
pointers (Brass, 2008). In both cases, the stack is logically represented as a vertical structure, with
the “top” serving as the access point for all operations.

One of the key advantages of stacks lies in their use in function call execution within
programming languages. When a function is called, its return address and local variables are
pushed onto the call stack. Once the function completes, these values are popped, and control is
returned to the calling function. This mechanism demonstrates the importance of stacks in
managing program flow efficiently (Aho, Hopcroft and Ullman, 1982).

Operations
Stacks support a restricted set of operations that follow the Last-In, First-Out (LIFO) principle.
The three fundamental operations are push, pop, and peek, all of which operate on the top element
of the stack (Cormen et al., 2009).

Push refers to the insertion of a new element onto the top of the stack. When a push operation
occurs, the stack pointer is moved upwards, and the new element becomes the topmost item. This
operation runs in constant time, O(1), provided the stack is not full.

Pop is the removal of the top element from the stack. Once an item is popped, the stack pointer
moves downwards, exposing the previous element as the new top. Like push, this operation is also
O(1), though it requires an underflow check to ensure the stack is not empty before removal
(Brass, 2008).

Peek, sometimes called top, allows inspection of the top element without altering the stack’s
contents. This is useful for checking the most recent element added to the stack without disturbing
the overall structure. Like push and pop, peek also operates in O(1) time (Karumanchi, 2011).

These operations collectively make stacks simple yet powerful, providing essential support for
tasks such as managing function calls, backtracking, and evaluating arithmetic expressions. Their
efficiency arises from the restriction that operations are confined to only one end of the structure,
eliminating the overhead of complex traversal (Aho, Hopcroft and Ullman, 1982).

41
Push Operation
The push operation inserts an element at the top of the stack. Imagine a stack
as a vertical collection, like plates stacked on top of each other. When you push a plate, you place
it on top of the others. In computing, this means adding new data at the end where the stack
pointer is currently pointing. Push is efficient because it only involves moving the pointer and
storing the new value. However, in an array-based implementation, push can fail if the stack is
already full, leading to a condition called overflow (Karumanchi, 2011).

This shows that the first three elements are successfully pushed, but when attempting to push
beyond the maximum capacity, overflow occurs.

Pop Operation
The pop operation removes and returns the element currently at the top of the stack. Following the
same plate analogy, pop removes the plate that was placed last. In computing, pop decreases the

42
stack pointer and retrieves the stored value. If the stack is empty, a stack
underflow condition occurs because there is nothing to remove (Cormen et al.,
2009).

This demonstrates the LIFO principle, where the last inserted element (30) is the first one
removed.

Peek Operation
The peek operation, also called top, retrieves the element at the top of the stack without removing
it. Using the plate analogy, peek allows you to look at the top plate without taking it off the stack.
This is particularly useful when you want to check the most recent addition while keeping the

43
stack intact. If the stack is empty, Peek should handle this by returning a
suitable message or error code (Brass, 2008).

Here, peek confirms which element is on top without altering the structure, showing that push and
pop have not yet been performed.

Use Case for Temporary Order Storage

In the Colombo Shoe Fair booking system, stacks can be used effectively for temporary order
storage. When customers browse the catalogue and select items before confirming their purchase,
the selections may need to be stored in a temporary structure until the order is finalized. A stack is
suitable in this case because it allows quick addition and removal of items at the top without
affecting the rest of the order (Cormen et al., 2009).

For example, if a customer adds Men’s Leather Shoes (S001), followed by Casual Sneakers
(S003), these selections are pushed onto the stack in the order they were made. If the customer

44
changes their mind about the last item, the system can simply pop it from the
stack, restoring the previous state of the temporary order. This reflects the Last-
In, First-Out (LIFO) nature of stacks, where the most recent addition is always the first one
removed (Karumanchi, 2011).

The temporary stack can act as a buffer before the final order is committed to a permanent data
structure such as a linked list or array for billing. This prevents unnecessary updates to the main
order list until the customer confirms their selection. It also mirrors real-world shopping
behaviours, where customers may change or undo their last choice before checkout (Brass, 2008).

This example shows how stacks can temporarily store customer selections and easily reverse the
last action, providing a flexible buffer before the order is finalized.

45
Queues

FIFO Principle
A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle, which
means that the element added first is also the first one to be removed. This behaviour is like a line
of people waiting for service, where the person who arrives earliest is served first, while
newcomers must wait until those ahead of them are attended to (Cormen et al., 2009).

The FIFO model ensures fairness because operations occur strictly in the order they were
requested. In computing, this is particularly important for task scheduling, print job management,
and network packet handling, where processes must be executed in sequence without allowing
later arrivals to bypass earlier ones (Karumanchi, 2011).

Queues are typically implemented with two pointers:

 The front, which points to the element to be removed.

 The rear, which points to the last inserted element.

The two main operations are enqueue, which inserts an element at the rear, and dequeue, which
removes an element from the front (Brass, 2008). Both operations run in constant time, O(1), if
implemented efficiently.

For example, in the Colombo Shoe Fair booking system, customer booking requests can be stored
in a queue to ensure that the first customer making a booking is also the first one served. This
maintains fairness and avoids customer dissatisfaction, as no one can “skip the line.”

46
Operations
Queues operate strictly according to the First-In, First-Out (FIFO) principle, and their
functionality revolves around three fundamental operations: enqueue, dequeue, and peek. These
operations ensure orderly processing of data and are widely applied in computing tasks such as
scheduling, load balancing, and customer request handling (Cormen et al., 2009).

Enqueue
The enqueue operation adds an element to the rear of the queue. When a new request arrives, it is
placed at the back of the line, preserving fairness by ensuring older requests are handled first. The

47
operation is efficient, typically O(1), provided the rear pointer is updated
correctly (Karumanchi, 2011).

Dequeue
The dequeue operation removes the element from the front of the queue. This reflects the FIFO
principle, where the first element to enter is also the first to be processed or removed. If the queue
is empty, this operation results in an underflow condition. Its time complexity is O(1) (Brass,
2008).

Peek
The peek operation allows inspection of the element at the front of the queue without removing it.
This is useful in systems where knowing the next task in line is necessary for preparation, but the
actual task is not yet processed. Peek has O(1) complexity since it only accesses the front element
without modifying the structure (Aho, Hopcroft and Ullman, 1982).

48
Example: Customer Service Line Simulation
In the Colombo Shoe Fair, visitors approach the help desk to confirm bookings, add items to on-
site orders, or make payments. A queue models this flow naturally under the FIFO rule: the first
visitor to arrive is the first to be served. Each arrival is enqueued at the rear; service takes the
visitor from the front via dequeue; staff may peek to see who is next without altering the line. This
preserves fairness, prevents “line-cutting,” and makes throughput predictable. Operationally,
enqueue/dequeue/peek all run in O(1) time in a properly implemented linked or circular-array
queue, so the system scales with bursts of traffic. Below is a small Java simulation that enqueues
customers with a requested service, repeatedly serves the head of the line, and prints the evolving
state of the queue to demonstrate FIFO behavior in practice.

49
Summary of chosen data structures for implementation

To satisfy the Colombo Shoe Fair requirements (fixed product catalogue; create/update orders;
allow on-site additions to the same order; fast search by order number; end-of-day revenue), the
solution uses simple, in-memory structures with predictable performance and clear trade-offs
(Cormen et al., 2009; Karumanchi, 2011; Brass, 2008).

Data structure Where it’s Core Typical Why chosen /

used operations complexity trade-offs

50
 used (avg)

Static Array (or fixed list) Shoe index lookup, lookup O(1), Catalogue
of Item catalogue traverse traverse O(n) size is small
(S001– and fixed →
S006) contiguous
storage and
instant access
(Cormen et
al., 2009).

HashMap<String, Item> Resolve get, O(1) Robust, direct

(itemsByCode) item code containsKey code→item
→ item mapping
quickly when
validating
inputs and
pricing
(Karumanchi,
2011).

Singly Linked List of Line-item addLast, addLast O(1) Orders

OrderItem per order list inside removeByCode, with tail; grow/shrink at
each order iterate remove/search runtime (on-
O(n) site
additions). No
shifts required
as in arrays
(Brass, 2008).

HashMap<String, Order> Search put, get O(1) Meets “search

(ordersById) orders by by order
order number”
number instantly;
avoids linear

51
 scans through
all orders
(Cormen et
al., 2009).

Stack<OrderItem> Temporary push, pop, peek O(1) Easy “undo

(tempSelections) basket/undo last add”
before while the
commit customer is
still deciding;
commit pops
into the order
(Karumanchi,
2011).

Queue<CustomerRequest> Service enqueue, O(1) Fair FIFO

counter line dequeue, peek handling of
customers at
the help
desk/cashier.

ArrayList<Order> End-of-day append, iterate append O(1) Simple pass to

(allOrders) + running total reporting (amort.), compute
iterate O(n) revenue; also
maintain a
running
revenue for
O(1) updates
on payment.

Set<String> (usedOrderIds) Ensure add, contains O(1) Lightweight

order-ID guard against
uniqueness duplicate IDs.

 Catalogue lookups use the array for display and a map for validation/pricing: this keeps UI
traversal simple while ensuring constant-time code resolution.

52
  Each order’s mutable line items live in a singly linked list to support
frequent additions/removals without shifting.

 A stack buffers last-minute changes before committing to the order proper, enabling quick
reversals.

 System-level searchability is guaranteed by the ordersById map, aligning with the brief’s
requirement to “search any order with detailed information via the given order number.”

 Revenue can be computed either incrementally (update a running total when an order is
paid) or by a final ArrayList traversal; both are acceptable for the pass criteria.

5. P2 – Operations of a Memory Stack

Concept of memory stack in computing

The memory stack (often called the call stack) is a region of process memory used to manage the
execution of procedures and functions according to a strict last-in, first-out (LIFO) discipline.
Each time a function is invoked, the runtime creates an activation record (or stack frame) that
captures the state necessary to execute that function and, on completion, to restore control to its
caller. This frame typically contains the return address, a saved frame/base pointer, parameters (if

53
passed on the stack), local variables, and any saved registers required by the
calling convention (Cormen et al., 2009; Aho, Hopcroft and Ullman, 1982).

On most architectures the stack grows toward lower addresses, guided by a stack pointer (SP) that
marks the top of the stack and a frame pointer (FP/BP) that anchors the current frame. A function
call pushes a new frame by adjusting the SP, saving the caller’s context, and establishing a fresh
FP; the corresponding return pops the frame, restores the caller’s context, and jumps to the saved
return address. Because frames are pushed and popped in exact reverse order of calls, the stack
naturally mirrors the nesting of calls, making recursion straightforward: each recursive invocation
receives an independent frame holding its own locals and return path (Sedgewick and Wayne,
2011; Cormen et al., 2009).

Stack storage is automatic: memory for locals exists only for the lifetime of the call and is
reclaimed instantly when the frame is popped, yielding constant-time allocation and deallocation
with excellent cache locality. This contrasts with the heap, where memory is requested explicitly
(e.g., via new/malloc) and must be reclaimed later, often at higher overhead and with fragmented
locality (Aho, Hopcroft and Ullman, 1982).

The call stack also underpins language and platform calling conventions. These conventions
prescribe where arguments and return values live (registers vs. stack), which registers a callee
must preserve, and how prologue/epilogue code shapes frames. Correct adherence enables
separately compiled modules and libraries to interoperate. Violations—such as mismatched
prototypes or corrupt writes beyond local arrays can smash the stack, overwriting return addresses
and destabilizing flow (Cormen et al., 2009).

Because each thread maintains its own stack, multi-threaded programs have multiple, independent
call stacks. Stacks are finite; deep recursion, unbounded automatic arrays, or infinite mutual
recursion can exhaust the stack and trigger a stack overflow. Robust software mitigates this risk
by preferring iteration where appropriate, bounding recursion depth, or moving large objects to
the heap (Sedgewick and Wayne, 2011).

Relating this to the Colombo Shoe Fair implementation, a top-level routine such as processOrder()
may call validateItems(), which in turn calls priceOf(code) and applyProcessingFee(total). Each
call pushes a new frame recording its locals (e.g., running totals, loop indices) and the return
address. When applyProcessingFee finishes, its frame is popped, control returns to validateItems,
and ultimately to processOrder. This disciplined push–pop lifecycle is precisely what makes

54
nested logic, error handling, and recursion reliable and predictable in
conventional languages (Cormen et al., 2009; Aho, Hopcroft and Ullman,
1982).

Function call mechanism

Push operation for parameters and return addresses

When a function is called, the system performs a push operation on the memory stack to prepare
for execution. The key information stored includes the return address (the instruction in the caller
program where execution should resume), the function’s parameters, and sometimes the old frame
pointer and saved registers depending on the calling convention (Cormen et al., 2009).

This mechanism ensures that the called function operates independently while preserving the state
of the caller. Each new call creates a fresh stack frame, which is placed at the top of the stack. For
instance, if the function calculateTotal() calls applyDiscount(price), the system pushes the return
address (the next instruction in calculateTotal()), followed by the argument price, onto the stack.
This encapsulated context means multiple nested or recursive calls can co-exist, with each frame
storing its own local data (Sedgewick and Wayne, 2011).

The push operation is efficient, operating in O(1) time, as it only requires adjusting the stack
pointer and writing values to the top of the stack. However, if too many calls are made without
returning (e.g., deep recursion), the stack may exceed its allocated memory, leading to a stack
overflow (Aho, Hopcroft and Ullman, 1982).

55
Pop operation for returning control

The pop operation is the counterpart to push and occurs when a function completes its execution.
At this stage, the function’s stack frame is removed from the top of the memory stack. This
process restores the state of the caller by retrieving the saved return address, local variables, and
frame pointer. Once the frame is popped, control transfers back to the instruction in the caller
function immediately following the original function call (Cormen et al., 2009).

For example, if applyDiscount(price) finishes, its frame is popped, and execution resumes in
calculateTotal() at the line right after the call. If additional nested calls exist, the system unwinds
the stack step by step, popping one frame at a time until the topmost frame corresponds to the
current executing function. This ensures that execution orders always respect the last-in, first-out
nature of the stack (Sedgewick and Wayne, 2011).

The pop operation, like push, is O(1) since it simply involves moving the stack pointer
downwards and reloading the saved state. This predictability and efficiency are why stacks are
universally adopted for managing function calls in programming languages.

56
Example of Nested Function Calls Using a Stack

Nested function calls are a clear demonstration of how the memory stack manages execution
order. Each time a function is invoked, the system pushes a new stack frame containing the return
address, parameters, and local variables onto the stack. When the function is completed, its frame
is popped, restoring control to the caller. This push–pop cycle allows multiple functions to be
active in memory at different depths of the call hierarchy, while still preserving the order of
execution (Cormen et al., 2009).

Consider the following scenario: a program begins with a main() function that calls
processOrder(). Inside processOrder(), the program calls validateItems(), which in turn calls
getPrice(). Each call pushes a new frame to the stack. Execution proceeds until the innermost
function (getPrice()) finishes. At that point, its frame is popped, and control returns to
validateItems(). Once validateItems() completes, its frame is popped, and control goes back to

57
processOrder(). Finally, when processOrder() completes, the stack frame is
popped, and control resumes in main().

This mechanism guarantees that functions exit in the reverse order of their calls, strictly following
the LIFO principle. It also ensures that each function call has its own isolated memory context,
preventing interference between nested calls (Aho, Hopcroft and Ullman, 1982).

Explanation in Stack Terms

1. main() starts → stack frame for main is pushed.

2. processOrder() is called → new frame is pushed.

3. validateItems() is called → another frame is pushed.

4. getPrice() is called → innermost frame is pushed.

5. getPrice() finishes → its frame is popped, control returns to validateItems().

6. validateItems() finishes → its frame is popped, control returns to processOrder().

7. processOrder() finishes → frame is popped, control returns to main().

8. main() ends → final frame is popped, and the program terminates.

Relevance of stack operations in program execution

Stack operations are central to how modern programs execute because they provide the
mechanism for managing function calls, local variables, and control flow in a predictable and
efficient way. The push and pop operations mirror the natural order of execution: when a function
is called, its activation record is pushed onto the memory stack, and when the function finishes,
the record is popped, and control returns to the caller. This simple but powerful mechanism
guarantees that functions exit in the exact reverse order of their entry, preserving the Last-In,
First-Out (LIFO) discipline that underpins structured execution (Cormen et al., 2009).

One key relevance of stack operations lies in their role in function call management. Without
stacks, it would be extremely difficult to handle nested or recursive calls because the system
would lose track of where to return once a function finishes. By storing return addresses,
parameters, and local variables in stack frames, stacks enable recursion to work seamlessly: each
recursive invocation gets its own isolated memory context (Aho, Hopcroft and Ullman, 1982).

58
Stacks are also vital in expression evaluation and parsing. Compilers and
interpreters often use stacks to evaluate arithmetic expressions (e.g., converting
infix to postfix notation), check balanced parentheses, and process nested structures in
programming languages (Sedgewick and Wayne, 2011). For example, evaluating (a + b) * (c - d)
can be simplified by pushing operators and operands onto stacks to ensure the correct order of
operations.

Another crucial role of stack operations is in exception handling and program flow control. When
an exception occurs, stack unwinding involves popping frames until the runtime locates a suitable
handler. Similarly, stacks allow for “undo” mechanisms in software applications, where the last
action performed by the user can be reversed by popping it from a stack (Karumanchi, 2011).

In the context of the Colombo Shoe Fair system, stack operations could be relevant in handling
temporary orders. For instance, while customers are browsing and adding items, their selections
can be stored in a stack. If they undo the last action, the system simply pops the top element,
reflecting the reversal of their most recent decision. This mimics real-world behaviour, where the
last choice is the first one reconsidered.

Thus, stack operations are not just theoretical constructs but are deeply embedded in every stage
of program execution, from function calls and recursion to expression evaluation, error handling,
and even application-level features like undo. Their efficiency, with push and pop both operating
in constant time O(1), makes them indispensable for predictable and reliable execution.

59
Activity 2

Specification of Abstract Data Type (ADT) for a Stack

Definition of an ADT

An Abstract Data Type (ADT) is a theoretical model for a data structure that defines what
operations can be performed on the data, but not how these operations are implemented. In other
words, an ADT specifies the logical behaviour of a structure while deliberately hiding the details
of its internal representation. This separation between specification and implementation allows
programmers to focus on the conceptual use of the structure, while different physical
implementations (such as arrays or linked lists) can be chosen later without affecting the external
behaviour (Liskov and Zilles, 1974).

For example, when specifying the ADT of a stack, the operations are defined in terms of their
functionality: push adds an element to the top, pop removes the most recently added element, and
peek retrieves the top element without removing it. The user of the stack does not need to know
whether it is implemented with an array, a linked list, or even a dynamic resizing mechanism. This
encapsulation makes ADTs critical in software engineering, promoting modularity, abstraction,
and reusability (Aho, Hopcroft and Ullman, 1982).

Formally, an ADT can be described using a mathematical model. It consists of:

 A domain of values (the data objects).

 A set of operations that can be applied to these values.

 A set of axioms or rules that define the expected outcomes of these operations (Goguen et
al., 1978).

In practice, this means that an ADT is less about data storage and more about the contract that
specifies behaviour. For instance, in the case of a stack ADT:

60
  Domain of values: A finite sequence of elements of type T.

 Operations: push(T element), pop(), peek(), and isEmpty().

 Axioms: Rules such as “if you push an element and immediately pop it, you get back the
same element” (Karumanchi, 2011).

Thus, the ADT concept provides a formal foundation for data structures like stacks, queues, and
linked lists, ensuring that their use remains consistent and reliable across implementations.

61
Imperative specification for stack

Operations (Push, Pop, Top, isEmpty, isFull)

62
63
Output

Pre-conditions and Post-conditions for Stack Operations

In an imperative specification, every operation is associated with pre-conditions (what must hold
before execution) and post-conditions (what must hold after execution). This formalises the
correctness of the Stack ADT (Cormen et al., 2009; Karumanchi, 2011).

Push(x)

 Pre-condition: The stack must not be full (isFull(S) = false).

 Post-condition: Element x is placed on the top of the stack, and the size of the stack
increases by one.

Pop()

 Pre-condition: The stack must not be empty (isEmpty(S) = false).

 Post-condition: The top element is removed, the size of the stack decreases by one, and the
next element (if any) becomes the new top. The value of the removed element is returned.

Top() (Peek)

 Pre-condition: The stack must not be empty (isEmpty(S) = false).

 Post-condition: The value of the current top element is returned, but the state of the stack
remains unchanged.

isEmpty()

 Pre-condition: None (can always be called).

64
  Post-condition: Returns true if the stack contains no elements,
otherwise returns false. The stack is not modified.

isFull()

 Pre-condition: None (can always be called).

 Post-condition: Returns true if the stack has reached its maximum capacity, otherwise
returns false. The stack is not modified.

Why this is important

Specifying pre-conditions and post-conditions ensures safe and predictable execution of stack
operations. For instance, calling Pop() on an empty stack leads to underflow, which violates the
pre-condition. Similarly, calling Push() on a full stack causes overflow, which breaks its valid
state. These formal rules help developers design robust programs and prevent runtime errors (Aho,
Hopcroft and Ullman, 1982).

Example of ADT stack in pseudo-code

Stack ADT Definition

Pseudo-code for Operations

65
Push(x)

Pop()

Top() (Peek)

66
isEmpty()

isFull()

This pseudo-code represents the logical behaviour of a stack ADT. It shows how each operation
modifies or inspects the stack while adhering to its Last-In, First-Out (LIFO) discipline. The
details of how elements are stored (array, linked list, dynamic structure) are hidden, which is the
essence of an ADT (Aho, Hopcroft and Ullman, 1982; Cormen et al., 2009).

Application of stack ADT in Colombo Shoe Fair

In the Colombo Shoe Fair booking system, the Stack ADT plays an important role in managing
temporary operations where the last action must be reversed first. The key feature of a stack — its
Last-In, First-Out (LIFO) behaviour — makes it especially useful in situations where customers or
the system may need to undo or backtrack actions before finalising an order (Cormen et al., 2009).
One direct application is in temporary order storage. When a customer is browsing and selecting
items, each selection can be pushed onto a stack to hold it temporarily. If the customer decides to

67
cancel the last chosen item before confirming the booking, the system simply
performs a pop operation to remove the most recent selection. This mirrors real-
world shopping behaviour, where the last action is the first to be undone.
Stacks can also assist in managing function calls within the system. For example, when the system
executes the booking process, it may call several internal functions such as validateItem(),
calculateTotal(), and applyDiscount(). Each function call generates a new stack frame, pushed
onto the call stack. Once the innermost function finishes, the stack unwinds through pop
operations, ensuring the program returns to the correct point of execution (Aho, Hopcroft and
Ullman, 1982).
Another important use of stacks is in undo/redo functionality for staff at the booking counter. If an
operator mistakenly adds the wrong shoe item or applies the wrong discount, the system can
maintain a stack of recent actions. Performing an undo simply pops the last action from the stack,
restoring the system to its previous state. This improves both efficiency and reliability in handling
customer transactions.
Thus, in the Colombo Shoe Fair system, the Stack ADT ensures that temporary storage, order
management, and program control flow are handled in a logical, structured, and efficient manner,
demonstrating the practical importance of this abstract structure in real-world applications.

Activity 3

System requirements from scenario

Context. The client is the organisers of the Colombo Shoe Fair. They require an online booking
workflow that lets visitors browse a fixed product catalogue, reserve items, and complete payment
either online or on-site. Each booking must generate a unique order number and an initial total
bill. If the visitor chooses on-site payment, they may later add more items to the same order
number at the fair; the system must support searching any order by its order number and updating
the final bill accordingly. At the end of the event, the system must report total revenue across all
bookings and purchases.

68
Product catalogue (given). The catalogue is fixed to six items (codes S001–
S006) with the stated names and LKR unit prices; you may assume only these
items exist for this implementation.

Functional requirements.

 Display the full catalogue to users and allow them to reserve “any number of items” before
visiting. On booking completion, generate a unique order number and compute the total
bill.

 Support two payment modes: Online (apply 3% processing fee to the bill) and On-site (pay
in person).

 If on-site is chosen, permit adding more items to the same order number during the visit;
search for any order-by-order number and show detailed information; when items are
finalised, update the total bill and make payment.

 Provide an end-of-fair revenue calculation over all bookings/purchases.

Non-functional / implementation constraints.

 Solution must be a programmed, in-memory implementation: no files or databases may be

used for storage. A terminal/console program is sufficient for assessment.

 Deliverables include design artefacts (pseudocode/flowcharts), working executable or

equivalent evidence, and annotated source code.

Data entities (from brief).

 Item {code, name, unitPrice } — drawn from the fixed table (S001–S006).

 Order { orderNumber, lineItems[], paymentMode, totals} — supports creation, search by

orderNumber, line-item additions (esp. on-site mode), fee application (3% for online), and
final settlement.

Key behaviours to implement.

1. Catalogue display & selection → reserve any number of items; compute subtotal.

2. Order creation → generate unique order numbers, store initial bill.

3. Payment mode logic → apply 3% fee if online; allow later additions if on-site and then
recompute bill.

69
 4. Order search → retrieve full details by order number.

5. End-of-day reporting → aggregate total revenue.

Proposed solution

To address the requirements of the Colombo Shoe Fair, a structured booking and order
management system has been designed using a combination of suitable data structures and
algorithms. The solution is entirely in-memory, meaning no external databases or files are used,
which keeps the program lightweight and ensures faster execution. The system is executed
through a console-based Java program, making it simple and accessible while still demonstrating
the application of complex data structures.

The key features of the solution are as follows,

Product Catalogue Management
The fixed shoe catalogue (items S001–S006 with their respective names and prices) is stored
using arrays for direct indexing and fast retrieval. This allows efficient display of items and
immediate access when customers make selections.

Order Creation and Booking

Each customer booking generates a unique order number. Customer orders are stored dynamically
using linked lists, enabling the system to handle variable-length orders where items can be added
or removed easily. A hash map structure is used to store and retrieve orders by their unique IDs in
constant time, ensuring quick search and updates.

Payment Processing
Two payment options are supported:
Online Payment: A 3% processing fee is applied to the order total.
On-site Payment: Customers may add more items later to the same order number before settling
the final bill.
This payment logic ensures flexibility while reflecting real-world customer preferences at the fair.

Order Searching and Updates

The system allows staff to retrieve any order using its order number. Detailed information such as

70
items booked, quantities, payment type, and current totals are displayed. For
on-site orders, the linked list structure ensures additional items can be inserted
dynamically and totals recalculated without complex restructuring.

Revenue Calculation
At the end of the event, the system calculates the total revenue generated from all confirmed
orders. This can be done either through a batch calculation across all orders or through an
incremental update as each order is paid. Both methods ensure accurate reporting of final revenue.

Error Handling and Testing

The solution includes error-handling features to manage invalid inputs, duplicate order numbers,
incorrect quantities, and attempts to re-checkout already paid orders. Testing has been carried out
using black-box and white-box approaches to verify correctness and reliability.

Design
Algorithm design

Pseudocode for booking process

Goal: let a visitor browse the fixed catalogue (S001–S006), build a basket, choose Online (add
3% fee) or On-site (pay later, allow later additions to same order number), then create and store
the order so it can be searched by order number.

Data (in-memory, no files/DB)

71
Order structures

Top-level flow

72
Catalogue + selection

73
Order creation + totals

Payment mode choice

74
Persistence + summary

On-site additions (used later at the fair)

75
Settlement & revenue

76
Flowchart of customer booking

Algorithm for order search by order number

The system must allow staff to retrieve full order details using the unique order number. This
aligns with the brief requirement: “The system should allow the staff to search any order with
detailed information via the given order number”

77
Explanation

1. Accept the order number as input.

2. Check if it exists in the in-memory map ORDERS_BY_ID.

o If not, return “Order not found”.

3. If found, fetch the order object and display:

o Metadata → ID, customer, payment mode, status.

o Itemised breakdown with codes, names, quantities, and line totals.

o Subtotal, fee (if online payment), and final total.

4. The complexity of the search is O(1) on average due to the use of a HashMap for
ORDERS_BY_ID.

78
Algorithm for revenue calculation

Goal. At the end of the fair, compute total revenue from all confirmed
purchases. In our design, only paid orders contribute to revenue (online orders marked PAID after
payment; on-site orders marked PAID at settlement)

A) Batch computation at end of event (simple and robust)

Why: This aligns with the brief’s “end-of-fair revenue calculation” and avoids counting
unfinished bookings or on-site baskets that weren’t settled.

Complexity: O(n) over the number of orders.

B) Incremental (running) revenue update (efficient during operations)

Maintain a single variable RUNNING_REVENUE. Update it only when an order is settled (status
changes to PAID).

79
Why: Gives instant totals during the event; eliminates the need to traverse all orders at the end.

Complexity: O(1) per settlement; O(1) per query.

C) Reconciliation helper (optional safety)

If you use both methods, add quick reconciliation to catch any missed updates:

Notes tied to scenario rules

80
  Online payments: include +3% processing fee in order.total; once paid,
that full total counts to revenue.

 On-site payments: may add items later; count revenue only after final settlement when
status becomes PAID.

 Searchability: revenue routines rely on orders kept in-memory maps; no files/DB per brief.

Choose A (batch) if you want simplest marking. Choose B (incremental) if you want instant totals
any time during the fair; you can still run C (reconcile) at the end as a correctness check.

Implementation
Program implementation

Programming language chosen

For the implementation of the Colombo Shoe Fair booking system, the chosen programming
language is Java.

Reasons for choosing Java,

1. Object-Oriented Structure – Java naturally supports encapsulation, inheritance, and

abstraction, which makes it suitable for modelling the system using classes such as Item,
Order, OrderItem, and RevenueService. This aligns well with the scenario requirements
where catalogue items, orders, and customers can be represented as separate objects.

2. Rich Standard Library – Java provides built-in collections (ArrayList, HashMap,

LinkedList, Queue, Stack) which directly map to the abstract data types (ADTs) specified
in the assignment (stacks, queues, linked lists, arrays). This reduces the need to build low-
level structures from scratch while still demonstrating ADT principles.

3. Strong Typing and Reliability – Java’s static typing and compiler checks ensure that errors
like invalid data types are caught early, improving the robustness of the program. This is
especially important in implementing error handling for invalid codes, duplicate orders,
and empty inputs (covered later in P5).

4. Platform Independence – Java runs on the JVM, meaning the program can be executed on
any system (Windows, Linux, macOS) with minimal changes, which is useful in an
academic environment.

81
 5. Console-Friendly for Demonstration – The assignment brief requires a
working program with console input/output examples rather than a
graphical user interface. Java is well suited for this because it provides straightforward
console I/O with Scanner and System.out.println, making testing and demonstration
simple.

6. Industry Relevance – Java is a widely used programming language in enterprise systems

and academic contexts, which makes it a good choice for demonstrating both technical
competence and real-world applicability.

Java provides the right balance between clarity, ADT demonstration, error handling, and
portability. Its use of standard libraries for stacks, queues, and maps directly supports the learning
outcomes, while console-based execution meets the assignment’s demonstration requirements.

Program implementation

Main.java

82
83
Item.java

84
ItemStore.java

Order.java

85
86
OrderService.java

87
OrderStatuse.java

PaymentMOe.java

88
Demonstration of functions

System Launch and Main Menu

Displaying the Catalog

Creating a New Order

89
Adding Items to an Order (Step 1)

Adding Items to an Order (Step 2)

Searching for an Existing Order

90
Checking Out an Order

Calculating Total Revenue

Invalid Order Search

91
Adding Items After Checkout

Invalid Quantity Input

Adding Items to Non-ONSITE Orders

92
Re-checkout of Already Paid Orders

Error Handling and Test Results

Error handling methods in program

Error handling is a crucial part of the Colombo Shoe Fair booking system to ensure that invalid
user inputs or incorrect operations do not crash the program or produce unreliable results. Instead,
the system is designed to provide clear feedback messages and block invalid actions, thereby
maintaining data integrity and system reliability.

Invalid Item Code Handling

When a user attempts to add an item using an invalid item code (e.g., typing S099 instead of a
valid catalogue item like S003), the system checks the input against the catalogue map
(ITEMS_BY_CODE) before processing it.

 Expected Behaviour,

1. Validate whether the entered item code exists in the catalogue.

2. If the code is not found, display an error message such as “Invalid item code.
Please try again”.

3. Prevent the system from adding the invalid item to the order.

 Implementation Principle,

o A HashMap lookup is used for constant-time (O(1)) validation.

93
 o If ITEMS_BY_CODE.containsKey(code) returns false, the
program triggers the error response.

 Relevance:
This error handling prevents corrupted orders and ensures that only valid catalogue items
(S001–S006) are ever added to customer bookings. It also improves user experience by
guiding staff to correct mistakes quickly during data entry.

Handling duplicate orders

In the Colombo Shoe Fair booking system, every order must have a unique order number to
ensure that customer purchases are tracked without conflict. Duplicate orders would cause serious
issues such as incorrect billing, mismatched records, and unreliable revenue calculations. To
prevent this, the system uses a controlled order number generation mechanism.

 System Behaviour,

1. Each new booking automatically generates an order number in the format CSF-
XXXX (e.g., CSF-0001, CSF-0002).

2. The system maintains an incremental counter that is updated every time an order is
created.

3. Because this counter only moves forward, previously generated order numbers
cannot be reused.

 Implementation Logic,

o A static counter variable is used in the program.

94
This ensures O(1) efficiency and guarantees uniqueness.

If another booking is made, the system generates

The earlier ID (CSF-0002) will never be reused, ensuring no duplicates.

This prevents confusion between different customer transactions, strengthens data integrity, and
simplifies future operations like searching orders and revenue tracking. In practical use, it mirrors
how point-of-sales (POS) systems ensure every bill is uniquely identifiable.

Preventing empty input submissions

Empty input submissions are a common source of runtime errors and logical flaws in console-
based applications. In the Colombo Shoe Fair booking system, input validation ensures that the
user cannot proceed if a required field such as order number, item code, or quantity is left blank.
This prevents invalid data from being processed and keeps the system reliable.

95
  System Behaviour,

1. When a user is prompted for input (e.g., entering an item code

or order number), the system checks whether the input is an empty string.

2. If the input is empty, the system immediately returns an error message such as
“Input cannot be empty. Please try again”.

3. The user is forced to re-enter valid data before the system continues.

This type of validation is critical in a sales system because processing an empty order number,
item code, or quantity could corrupt the booking data or generate unexpected exceptions. By
enforcing non-empty input, the program ensures robustness, data integrity, and user
accountability.

Testing approach

Test case design (black-box / white-box)

The Colombo Shoe Fair was tested using a combination of black-box and white-box methods to
ensure both functional correctness and internal reliability.

Black-box testing

96
Black-box testing was carried out by mapping test cases directly to the
functional requirements (FR1–FR8) of the system. Each requirement was
treated as an independent unit and tested using valid and invalid inputs. For example, FR1 (View
Catalog) verified that the catalogue size matched the expected six items, while FR2 (Create
ONSITE Order) ensured that orders could be created and items added correctly. Negative cases
such as invalid item codes (FR6) and invalid quantities (FR6) were also tested, demonstrating that
the system correctly rejected erroneous input. The black-box approach focused on input/output
validation without reference to the internal source code.

White-box testing

White-box testing complemented this by targeting the internal branches and exception paths
within the program. This included verifying that the checkout() method transitioned orders from
OPEN to PAID, ensuring that attempts to add items to already paid orders raised the correct
IllegalStateException, and tested that negative quantities triggered IllegalArgumentException.
Code coverage was enhanced by deliberately exploring all control flow paths, including edge
cases such as duplicate checkout, null lookups, and switching between ONSITE and ONLINE
modes.

Together, these approaches provided comprehensive coverage: black-box testing confirmed that
the system fulfilled its external requirements, while white-box testing validated the robustness of
the underlying implementation, exception handling, and data integrity mechanisms.

o 9.2.2 Sample test data used

o 9.2.3 Expected vs actual output

Evidence of testing

I used automated test cases

Expected vs Actual Output

Test Requirement Expected Output Actual Output Result

ID (FR)

TC- FR1 – View Catalog size = 6 Catalog size = 6 PASS

97
01 Catalog

TC- FR2 – ONSITE Subtotal = 10000, Checkout Subtotal = 10000, Checkout PASS
02 Order Creation total = 10000, Status = PAID total = 10000, Status = PAID
& Checkout

TC- FR3 – Add Items added successfully, Items added successfully, PASS
03 Items to subtotal updated correctly subtotal updated correctly
ONSITE Order

TC- FR4 – ONLINE Subtotal = 4800, Total fee = Subtotal = 4800, Total fee = PASS
04 Order with +3% 4944, Status = PAID 4944, Status = PAID
Fee

TC- FR5 – Guard: Exception → Exception → PASS

05 Add to PAID IllegalStateException IllegalStateException
Order

TC- FR6 – Error: Exception → Exception → PASS

06 Negative IllegalArgumentException IllegalArgumentException
Quantity

TC- FR6 – Error: Exception → Exception → PASS

07 Unknown Item IllegalArgumentException IllegalArgumentException
Code

TC- FR8 – Revenue Revenue = 7344 (sum of two Revenue = 7344 (sum of two PASS
08 Calculation PAID orders only) PAID orders only)

98
Screenshots of execution

99
100
Console output logs

101
Summary of system reliability

The results of the automated testing demonstrate that the Colombo Shoe Fair booking system is
both functionally correct and resilient against invalid operations. A total of eight test cases were
executed, covering all the defined functional requirements (FR1–FR8) as well as critical error-
handling scenarios. Every test passed successfully, with 0 failures recorded, confirming that the
system performs reliably under both normal and exceptional conditions.

From a functional perspective, the system correctly handles catalogue display, order creation, item
addition, checkout processes, and revenue calculation. Both ONSITE and ONLINE booking
modes were validated, including the application of the 3% online fee, ensuring consistency with
the specified business rules.

From a robust perspective, the program effectively prevents invalid actions such as adding items
to an order after checkout, submitting negative quantities, or entering unknown item codes. Each
of these cases was handled gracefully with appropriate exceptions (IllegalStateException and
IllegalArgumentException), thereby maintaining data integrity and preventing runtime crashes.

The integration of black-box testing (requirement coverage) and white-box testing (branch and
exception validation) ensured comprehensive verification of both external behaviour and internal
logic. The use of an automated smoke test runner further increased confidence by providing
repeatable, objective, and reproducible test results.

In summary, the system demonstrates high reliability for its intended use case, with strong
safeguards against invalid input and consistent performance across all tested features. This

102
indicates that the Colombo Shoe Fair system is well-prepared for deployment
in a real-world environment where accuracy, integrity, and robustness are
essential.

Activity 4

Introduction to asymptotic analysis

When designing and evaluating algorithms, it is essential to understand how their performance
changes as the size of the input grows. Asymptotic analysis is the mathematical tool used to
evaluate the efficiency of algorithms in terms of time complexity (execution speed) and space
complexity (memory usage), without depending on specific hardware or programming language
details (Cormen et al., 2009).

The key idea is to focus on the growth rate of an algorithm’s resource requirements as the input
size increases, rather than measuring actual runtime in seconds. This allows computer scientists
and developers to compare algorithms on a fair basis. For example, an algorithm that requires O(n
log n) steps will eventually outperform one that requires O(n²) steps when n becomes large, even
if the latter seems faster on small inputs.

103
In asymptotic analysis, three primary notations are used:

 Big O (O-notation): Describes the upper bound of an algorithm’s

growth rate, representing the worst-case scenario. For instance, linear search in an array
has O(n) time complexity.

 Big Omega (Ω-notation): Describes the lower bound, representing the best-case scenario.
For example, if the first element matches in linear search, the performance is Ω(1).

 Big Theta (Θ-notation): Describes the tight bound, meaning the algorithm’s growth rate is
both upper and lower bounded. For binary search, the time complexity is Θ(log n).

Asymptotic analysis is particularly important because it abstracts away machine-specific details

and focuses only on how algorithms scale. In the context of the Colombo Shoe Fair system,
different data structure operations (e.g., searching for an order in a HashMap vs. iterating through
a LinkedList) can be analysed asymptotically to justify design choices. For example, using a
HashMap for order lookup ensures an average-case time complexity of O(1), which is much more
efficient than a linear O(n) search.

Therefore, asymptotic analysis provides a theoretical foundation to evaluate algorithm

effectiveness and ensures that the system remains efficient as the number of customers, orders,
and items grows.

Big-O notation explained

The most widely used tool in asymptotic analysis is Big-O notation. It provides a way to describe
the upper bound of an algorithm’s running time, focusing on how execution time increases
relative to input size n (Cormen et al., 2009). By abstracting away constant factors and machine-
dependent differences, Big-O allows algorithms to be compared fairly in terms of scalability.

Best Case, Worst Case, and Average Case

When evaluating an algorithm, it is important to consider three different performance scenarios:

1. Best Case (Ω-notation)

 The scenario in which the algorithm performs with the least possible number of steps.

 This represents the lower bound of performance.

104
  Example: In a linear search through an array of size n, the best case
occurs if the target element is the first item.

o Time complexity: Ω(1).

2. Worst Case (O-notation)

 The scenario where the algorithm takes the maximum number of steps, usually when the
input is arranged in the least favourable way.

 This represents the upper bound of performance.

 Example: In linear search, the worst case happens if the element is the last in the array or
not present at all.

o Time complexity: O(n).

3. Average Case (Θ-notation)

 The expected number of steps an algorithm takes for a random input.

 This represents the tight bound, balancing between best and worst cases.

 Example: In linear search, the target element on average will be found in the middle of the
array.

o Time complexity: Θ(n).

Illustrative Example in Colombo Shoe Fair

 Order Search: Since the system uses a HashMap (ORDERS_BY_ID) for order lookups:

o Best case: Ω(1) (order found immediately with no collisions).

o Average case: Θ(1) (constant-time lookup with low collisions).

o Worst case: O(n) (if all orders hash to the same bucket, which is rare but possible).

 Revenue Calculation (Batch): Iterating through all orders at the end of the fair:

o Best case: Ω(n) (must check all orders, no shortcuts).

o Average case: Θ(n).

105
 o Worst case: O(n).

This demonstrates how Big-O, Big-Ω, and Big-Θ help quantify performance
under different circumstances, providing insight into both practical and theoretical efficiency.

Example: searching order in list (O(n))

When analysing algorithms, it is useful to illustrate Big-O notation with a practical example.
Consider the scenario where all orders at the Colombo Shoe Fair are stored in a list (e.g., an
ArrayList or LinkedList), and the staff need to search for an order by its order number.

Analysis

 Best Case (Ω (1)):

The order being searched for is the very first element in the list. Only one comparison is
required.

 Worst Case (O(n):

The order is the last element in the list, or it does not exist at all. The algorithm must check
every element, leading to n comparisons.

 Average Case (Θ(n)):

On average, the order will be somewhere in the middle of the list, requiring about n/2
comparisons. Asymptotically, this still simplifies to Θ(n).

Why O(n)?

106
In the worst case, the search requires checking each of the n elements exactly
once. Thus, the time complexity grows linearly with the number of orders. If
there are 1,000 orders, the algorithm may need up to 1,000 checks in the worst case.

Illustrative Example in Shoe Fair System

If the organisers had decided to store all bookings on a simple list instead of a HashMap,
searching for an order number like CSF20250930143001 would require a sequential scan:

 With 10 orders → up to 10 checks.

 With 10,000 orders → up to 10,000 checks.

This demonstrates why the system design uses HashMap (ORDERS_BY_ID) for order lookups,
since it reduces the average-case search time from O(n) to O(1) (constant time), making the
system more efficient and scalable (Cormen et al., 2009).

Example: adding item to booking (O(1))

Another useful illustration of asymptotic analysis comes from the operation of adding a new item
to a customer’s booking in the Colombo Shoe Fair system. Each order stores its line items in a
linked list (or a dynamic collection like ArrayList). Adding an element at the end of such a
structure can be performed in constant time, i.e., O(1) (Cormen et al., 2009).

107
Analysis

 Best Case (Ω(1)):

The new item is simply linked to the end of the list or appended to the array; this takes
constant time.

 Worst Case (O(1)):

Because the insertion always occurs at the end and no shifting of existing elements is
required (for a linked list or amortised for an array), the cost remains constant.

 Average Case (Θ(1)):

On average, each addition takes constant time regardless of how many items are already in
the order.

Thus, adding an item to a booking is O(1) in time complexity.

Illustrative Example in Shoe Fair System

If a customer with order CSF20250930143001 adds Running Shoes (S005) during an on-site visit,
the system simply appends that item to the linked list of items:

 No need to scan all existing items (unlike searching).

 No need to resize or reallocate (as in fixed arrays).

 Update subtotal and fee instantly.

For example:

 Before: 2 items, subtotal = Rs. 8000

 After adding Running Shoes (Rs. 4800): subtotal = Rs. 12,800, total = Rs. 12,800

The operation took constant time regardless of the size of the booking.

Relevance to Colombo Shoe Fair algorithms

Asymptotic analysis is not just a theoretical exercise; it is directly relevant to how the Colombo
Shoe Fair booking system is designed and implemented. By understanding the growth rates of key

108
operations, organisers can ensure that the system remains efficient, scalable,
and responsive even as the number of customers and orders increases (Cormen
et al., 2009).

Order Search

 Implemented with a HashMap (ORDERS_BY_ID).

 Average case: Θ(1) → instant lookup by order number, even with thousands of orders.

 Worst case: O(n) if many hash collisions occur, though this is rare with good hashing.

 Relevance: Ensures staff can find bookings quickly during the fair without delays, unlike
list-based searching (O(n)).

Adding Items to Orders

 Use a linked list for storing order items.

 Time complexity: O(1) for adding at the end, regardless of how many items are already in
the order.

 Relevance: Supports smooth on-site updates when customers add extra shoes to existing
bookings. Staff don’t face slowdowns as the number of items grows.

Stack for Temporary Selections

 Customers’ trial selections before confirming are pushed/popped on a stack.

 Push/Pop operations: O(1).

 Relevance: Allows fast “undo” of the last added item, enhancing customer experience at
the booking desk.

Queue for Customer Service Line

 Customers at the counter are managed in a queue.

109
  Enqueue/Dequeue operations: O(1).

 Relevance: Guarantees fair FIFO processing of service requests,

preventing line-cutting and ensuring predictable waiting times.

Revenue Calculation

 Batch method: Traverse all n orders → O(n).

 Incremental method: Update running total per settlement → O(1).

 Relevance: Batch calculation is acceptable for end-of-day reports, but incremental tracking
provides real-time insights during the event.

Operation Data Complexity Relevance at Fair

Structure (avg)

Search order by ID HashMap Θ(1) Fast retrieval of bookings

Add item to booking Linked List O(1) Efficient on-site additions

Undo last selection Stack O(1) Smooth customer-facing

undo

Serve next customer Queue O(1) Fair and predictable

service

End-of-day revenue Array/Map O(n) Accurate reports

calculation scan

Incremental revenue update Counter var O(1) Real-time revenue tracking

By applying asymptotic analysis to each operation, the system design makes clear why certain
ADTs were chosen. For example, moving from a list-based search (O(n)) to a HashMap search
(O(1)) directly improves scalability. Similarly, stacks and queues enable constant-time operations
for undue and customer management, ensuring the system can handle large crowds without
bottlenecks.

110
 11. P7 – Measuring Efficiency of Algorithms

Introduction to algorithm efficiency

When building software systems such as the Colombo Shoe Fair booking system, it is not enough
for algorithms to simply produce correct results. They must also do so efficiently, meaning with
acceptable use of time and memory resources. Algorithm efficiency refers to how well an
algorithm utilises computational resources while solving a problem, especially as the input size
grows (Sedgewick and Wayne, 2011).

Efficiency is generally measured in two main dimensions:

1. Time Efficiency (Time Complexity)

o Refers to the amount of time an algorithm takes to complete its execution relative
to the size of the input.

o For example, searching for an order in a list (O(n)) becomes slower as the number
of orders grows, while searching in a hash map (O(1)) remains nearly constant.

2. Space Efficiency (Space Complexity)

o Refers to the amount of memory an algorithm uses during execution.

o For example, a simple iterative revenue calculation uses minimal extra memory,
while recursive algorithms may consume additional stack frames.

Efficiency analysis is essential because it helps determine whether an algorithm is practically

usable under real-world conditions. For small inputs, even inefficient algorithms may perform
acceptably. However, as the scale increases (hundreds or thousands of orders in the Shoe Fair
system), inefficient algorithms can cause delays, system crashes, or poor customer experience.

The role of asymptotic analysis is to provide a theoretical foundation for efficiency, but in
practice, empirical measurement such as recording execution time on actual data or stress-testing
with large input sizes is also necessary (Cormen et al., 2009). Both theoretical and empirical
perspectives are important in judging whether the chosen data structures and algorithms can meet
user requirements in real-world scenarios.

In summary, algorithm efficiency is about balancing correctness, speed, and resource usage. In the
case of the Colombo Shoe Fair, efficient operations like O(1) order lookups and constant-time

111
stack/queue operations ensure that the system scales smoothly during peak
usage, while batch operations like end-of-day revenue (O(n)) are acceptable
since they are only run occasionally.

Time complexity as efficiency measure

One of the most common ways to measure algorithm efficiency is by evaluating its time
complexity. Time complexity describes how the running time of an algorithm increases as the
input size grows. This is expressed using asymptotic notations such as Big-O, Big-Ω, and Big-Θ
(Cormen et al., 2009).

By comparing algorithms through their time complexities, we can determine which approach is
more scalable and practical for real-world systems like the Colombo Shoe Fair booking platform.

Bubble sort vs binary search

Aspect Bubble Sort Binary Search
Purpose Simple sorting algorithm: repeatedly Efficiently finds a target value in a
swaps adjacent elements until sorted sorted array by dividing search
interval
Algorithm 1. Compare each pair of adjacent 1. Start with middle element
Steps elements 2. If target matches → return
2. Swap if in wrong order 3. If smaller → search left half, else
3. Repeat until no swaps are needed → search right half
Best Case Ω(n) (already sorted) Ω(1) (target is middle element)
Average Θ(n²) Θ(log n)
Case
Worst Case O(n²) (reverse order) O(log n)
Implication Inefficient for large datasets; quadratic Highly efficient; logarithmic growth
growth in comparisons and swaps makes it scalable for large datasets

Comparison

Algorithm Best Case Average Case Worst Case Scalability

112
 Bubble Sort Ω(n) Θ(n²) O(n²) Poor

Binary Ω(1) Θ(log n) O(log n) Excellent

Search

 Bubble Sort is suitable only for small datasets where simplicity matters.

 Binary Search, although requiring sorted data, is far more efficient for search operations in
large datasets.

Relevance to Colombo Shoe Fair

 If the system had to sort orders by total value using Bubble Sort, it would become very
slow once the number of orders exceeds a few hundred.

 On the other hand, if the system maintains orders in a sorted list by order number, Binary
Search allows fast retrieval (O(log n)) instead of a linear scan (O(n)).

 This comparison highlights the importance of selecting the right algorithm: choosing a
more efficient one ensures smooth customer experience during peak fair times.

Space complexity as efficiency measure

While time complexity measures the speed of algorithms, space complexity measures the
amount of memory they use during execution. An algorithm may be very fast but consumes a
large amount of memory, which makes it impractical for systems with limited resources
(Brass, 2008).

Space complexity includes,

 Fixed Part: Memory required for program code, constants, and variables.

 Variable Part: Memory required for dynamic structures such as arrays, stacks, and linked
lists, which depends on input size.

Example: Memory Used by Stack vs Array

Aspect Stack Array

113
 Structure Dynamic data structure that Static data structure with fixed size
grows and shrinks as defined at creation.
elements are pushed and
popped.

Memory Uses dynamic allocation; Uses contiguous memory block of

Allocation requires extra memory for predefined size.
pointers or object overhead.

Flexibility Flexible – can expand until Inflexible – size cannot be changed

system memory is after allocation.
exhausted.

Memory May consume slightly more Efficient in terms of memory per

Efficiency memory due to overhead element but may waste space if
managing nodes or object underused.
wrappers.

Example in A stack is used for An array is used for the fixed product
Shoe Fair temporary order selections catalogue (S001–S006) → pre-
→ grows only when allocated and always occupies
customers add trial items. memory, even if not fully used.

Illustrative Explanation

 In the Colombo Shoe Fair system, the product catalogue is stored in an array because the
items (S001–S006) are fixed and small. This is memory efficient because the array is
known in advance.

 For temporary selections, a stack is used because customers may add or undo items
dynamically. Although each push/pop uses a little extra memory overhead, it avoids
wasting large, fixed blocks of memory.

Thus, the trade-off is clear: arrays are space-efficient but rigid, while stacks are slightly
heavier but flexible, making them ideal for dynamic operations during the fair.

114
Trade-offs between time and space

In algorithm design, there is often a trade-off between time complexity and

space complexity. A faster algorithm may require more memory, while a memory-efficient
algorithm may take longer to execute. Choosing the right balance depends on the system
requirements, hardware limitations, and expected input sizes (Sedgewick and Wayne, 2011).

Example in Order Search System

In the Colombo Shoe Fair booking system, staff need to search for orders by their unique order
number. Two possible approaches illustrate the time–space trade-off:

Approach Time Space Explanation

Complexity Complexity

Linear O(n) O(1) Orders stored sequentially in an

Search in a array or linked list; uses little
List memory but require scanning of
all elements in the worst case.

HashMap O(1) average, O(n) Orders stored in a HashMap

Lookup O(n) worst keyed by order number require
extra memory for hash table but
retrieves results almost instantly
on average.

Illustration

 If the system stored 10,000 orders in a simple list, a search might require scanning all
10,000 entries in the worst case. This is slow but memory usage is minimal.

 With a HashMap, the system needs extra space for keys, hash codes, and buckets.
However, the order can usually be found in a single lookup (O(1)), which is much faster.

 This shows a clear trade-off: the HashMap consumes more memory but provides a
dramatic improvement in time efficiency, which is crucial during peak fair times when
staff must quickly assist customers.

115
Summary of efficiency analysis

The efficiency analysis of the Colombo Shoe Fair booking system

highlights how algorithm design choices directly influence both performance and resource
usage. By applying asymptotic analysis and measuring efficiency through time and space
complexity, the system ensures that it can scale effectively during peak usage without
sacrificing reliability.

 Time Complexity Findings:

o Using a HashMap for order search provides O(1) average-case lookup time, which
is a major improvement over a linear list search with O(n).

o Adding items to bookings with a linked list is O(1), ensuring fast updates even as
orders grow.

o Stacks and queues used for undo operations and customer service are also O(1),
supporting smooth real-time interactions.

o Revenue calculation is O(n) in batch mode but can be tracked incrementally in

O(1) per transaction for real-time insights.

 Space Complexity Findings:

o Arrays (e.g., fixed product catalogue) are space-efficient but rigid.

o Stacks and queues provide flexibility but require slightly more memory overhead.

o The HashMap for order searches trades extra memory usage for significantly faster
time performance, which is a justified design choice.

 Trade-offs:

o Linear search (less memory, more time) vs. HashMap lookup (more memory, less
time) demonstrates the classic time–space trade-off.

o For a busy event like the Shoe Fair, prioritising faster time performance is more
critical than saving a small amount of memory.

 Overall Efficiency:
The chosen data structures (arrays, linked lists, stacks, queues, and hash maps) collectively
provide an optimal balance of time efficiency and practical memory use. This ensures the

116
 system remains responsive for customer orders, quick searches, and
revenue reporting, even under heavy load.

In conclusion, the efficiency analysis confirms that the implemented algorithms are both
effective and scalable, making the system well-suited to handle real-world fair operations.

Conclusion
The Colombo Shoe Fair booking system successfully demonstrates how appropriate data
structures and algorithms can be applied to solve real-world problems efficiently. The program
meets the main requirements of the scenario by providing a structured catalogue, generating
unique order numbers, handling online and on-site payments, supporting search functionality for
orders, and producing a final revenue calculation. Through the use of arrays, linked lists, stacks,
queues, and hash maps, the solution ensures that operations such as order creation, modification,
retrieval, and revenue reporting are handled in a reliable and scalable manner. The chosen data
structures proved to be highly effective for their intended purposes. Arrays were ideal for storing
the fixed catalogue due to their speed and simplicity, while linked lists provided flexibility for
dynamic customer orders. Hash maps enabled constant-time searching of orders by ID, ensuring
responsiveness in high-demand situations. Stacks and queues supported temporary operations and
fair customer handling, reflecting real-world practices at the event. These decisions not only
satisfied functional requirements but also highlighted important trade-offs between efficiency,
scalability, and memory usage. However, the current solution also has certain limitations. Being
an in-memory system, all data is lost once the program ends, meaning it is not suitable for real-
world deployment without persistent storage. Additionally, the console-based interface, while
sufficient for demonstration, is less user-friendly compared to a graphical or web-based interface.
These limitations highlight areas where future improvements could be made. Enhancements such
as integration with a database, a graphical user interface, and extended functionality like real-time
analytics or mobile access would make the system more practical for large-scale adoption.

Lessons Learnt
Developing this project provided several key insights into both theory and practice,

1. Importance of Data Structures and Algorithms

The project reinforced how crucial it is to choose the right data structure for the right task.
For example, arrays offered constant-time access for the catalogue, while linked lists
allowed dynamic order modifications without restructuring.

117
 2. Balancing Trade-offs
A major lesson was understanding trade-offs between time and space
complexity. For instance, hash maps offered instant searching but required more memory,
while linked lists saved shifting costs but required sequential traversal.
3. Error Handling in Practical Systems
Implementing validation for duplicate orders, incorrect inputs, and invalid operations
highlighted the importance of robustness in real systems. Error handling is not just an add-
on but a central feature that ensures reliability.
4. From Theory to Real-World Context
The project showed how abstract concepts like stacks, queues, and asymptotic analysis are
not just theoretical but have direct applications in scenarios such as bookings, undo
operations, and fair customer service queues.
5. Future-Oriented Thinking
Working within the assignment’s constraints made it clear that practical systems require
features beyond core functionality, such as persistence, user-friendly interfaces, and
scalability. This highlighted the importance of designing with future enhancements in
mind.

References

Brass, P. (2008). Advanced Data Structures. Cambridge University Press. Available at:
https://doi.org/10.1017/CBO9780511804425
(Accessed: 30 September 2025).

Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2009). Introduction to Algorithms. 3rd
ed. MIT Press. Available at: https://mitpress.mit.edu/9780262033848/introduction-to-algorithms/
(Accessed: 30 September 2025).

Karumanchi, N. (2011). Data Structures and Algorithms Made Easy. CareerMonk Publications.
Available at: https://www.careermonk.com
(Accessed: 30 September 2025).

118
GeeksforGeeks. (2025). Data Structures and Algorithms Tutorials.
GeeksforGeeks. Available at: https://www.geeksforgeeks.org/data-structures/
(Accessed: 30 September 2025).

W3Schools. (2025). Java Data Structures. W3Schools. Available at:

https://www.w3schools.com/java/java_data_structures.asp
(Accessed: 30 September 2025).

Oracle. (2025). The Java™ Tutorials – Collections and Data Structures. Oracle. Available at:
https://docs.oracle.com/javase/tutorial/collections/index.html
(Accessed: 30 September 2025).

Programiz. (2025). Stack Data Structure (with Java examples). Programiz. Available at:
https://www.programiz.com/dsa/stack
(Accessed: 30 September 2025).

Tutorialspoint. (2025). Queue Data Structure. Tutorialspoint. Available at:

https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm
(Accessed: 30 September 2025).

Baeldung. (2025). Guide to Java LinkedList. Baeldung. Available at:

https://www.baeldung.com/java-linkedlist
(Accessed: 30 September 2025).

Stack Overflow. (2025). Discussion on ADT and Stack Operations in Java. Stack Overflow.
Available at: https://stackoverflow.com
(Accessed: 30 September 2025).

119
Higher Nationals – Grading Rubric

Achieved/Not
Grading Criteria Comment
Achieved

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.

P3 Specify the abstract data type for a software stack using an imperative definition.

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 offering a justification for
the view.

P4 Test the system against user and system requirements. Implement a complex ADT and algorithm in

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

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.

121