BTEC Level 5 HND Computing: Data Structures and Algorithms Report

This report details the implementation and assessment of data structures and algorithms, specifically focusing on stack and queue implementations for a middleware system. The report covers the design of Abstract Data Types (ADTs), algorithm development, and the demonstration of operations with error handling. It includes an analysis of time and space complexity, efficiency measurement techniques, and the application of asymptotic analysis (Big O, Omega, Theta notations) to assess algorithm effectiveness. The report also evaluates the use of ADTs in design, considering complexity, trade-offs, and benefits. The implementation utilizes Java and includes examples of converting numbers to binary using a stack. The report further examines error handling using try-catch blocks and discusses the different growth rates of algorithms to determine efficiency. Finally, the report explores how to measure algorithm efficiency by considering factors such as space and time complexity.

Higher Nationals in Computing
Unit 19: Data Structures and
Algorithms
ASSIGNMENT 2
Learner’s name: Nguyễn Huỳnh Triệu
Tỉ ID:GCS190914
Class:GCS0805A
Subject ID: 1649
Assessor name: Vũ Thanh Hiền
Assignment due: Assignment submitted:

ASSIGNMENT 1 FRONT SHEET
Qualification BTEC Level 5 HND Diploma in Computing
Unit number and title Unit 19: Data Structures and Algorithms
Submission date Date Received 1st submission
Re-submission Date Date Received 2nd submission
Student Name Nguyen Huynh Trieu Ti Student ID GCS190914
Class GCS0805A Assessor name Vu Thanh Hien
Student declaration
I certify that the assignment submission is entirely my own work and I fully understand the consequences of plagiarism. I understand that
making a false declaration is a form of malpractice.
Student’s signature
Grading grid
P1 P2 P3 M1 M2 M3 D1 D2

 Summative Feedback:  Resubmission Feedback:
Grade: Assessor Signature: Date:
Internal Verifier’s Comments:
IV Signature:

ASSIGNMENT 2 BRIEF
Qualification BTEC Level 5 HND Diploma in Business
Unit number Unit 19: Data Structures and Algorithms
Assignment title Implement and assess specific DSA
Academic Year
Unit Tutor Vu Thanh Hien
Issue date Submission date
IV name and date
Submission Format:
Format: The submission is in the form of an individual written report. This should be written in a
concise, formal business style using single spacing and font size 12. You are required to make
use of headings, paragraphs and subsections as appropriate, and all work must be supported
with research and referenced using the Harvard referencing system. Please also provide a
bibliography using the Harvard referencing system.
Submission Students are compulsory to submit the assignment in due date and in a way requested by
the Tutors. The form of submission will be a soft copy in PDF posted on corresponding
course of http://cms.greenwich.edu.vn/ Project also needs to be submitted in zip format.
Note: The Assignment must be your own work, and not copied by or from another student or from
books etc. If you use ideas, quotes or data (such as diagrams) from books, journals or other sources, you
must reference your sources, using the Harvard style. Make sure that you know how to reference
properly, and that understand the guidelines on plagiarism. If you do not, you definitely get fail
Assignment Brief and Guidance:
Scenario: Continued from Assignment 1.
Tasks
For the middleware that is currently developing, one part of the provision interface is how message can be
transferred and processed through layers. For transport, normally a buffer of queue messages is implemented and
for processing, the systems requires a stack of messages.
The team now has to develop these kind of collections for the system. They should design ADT / algorithms for

these 2 structures and implement a demo version with message is a string of maximum 250 characters. The demo
should demonstrate some important operations of these structures. Even it’s a demo, errors should be handled
carefully by exceptions and some tests should be executed to prove the correctness of algorithms / operations.
The team needs to write a report of the implementation of the 2 data structures and how to measure the
efficiency of related algorithms. The report should also evaluate the use of ADT in design and development,
including the complexity, the trade-off and the benefits.
Learning Outcomes and Assessment Criteria
Pass Merit Distinction
LO1 Implement complex data structures and algorithms
P4 Implement a complex ADT and
algorithm in an executable
programming language to solve a
well defined problem.
M4 Demonstrate how the
implementation of an
ADT/algorithm solves a well-
defined problem
D3 Critically evaluate the
complexity of an implemented
ADT/algorithm
P5 Implement error handling
and report test results.
LO4 Assess the effectiveness of data structures and algorithms
D4 Evaluate three benefits of
using implementation
independent data structures
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

Table of contents
Table of contents..........................................................................................................................................................6
P4 Implement a complex ADT and algorithm in an executable programming language to solve a well defined
problem
......................................................................................................................................................................................
7
P5 Implement error handling and report test results...................................................................................................8
P6 Discuss how asymptotic analysis can be used to assess the effectiveness of an algorithm...................................10
1. Asymptotic Analysis – Analysis of Algorithms.........................................................................................................10
1.1 Big Oh Notation, Ο................................................................................................................................................10
1.2 Omega Notation, Ω...............................................................................................................................................11
1.3 Theta Notation, θ..................................................................................................................................................11
2. The execution Time of Algorithms..........................................................................................................................12
3. General rules for estimation...................................................................................................................................13
P7 Determine two ways in which the efficiency of an algorithm can be measured, illustrating your answer with an
example...................................................................................................................................................................... 13
1. Measurement of algorithm efficiency.....................................................................................................................14
2. Common Growth Rates..........................................................................................................................................17
3. Comparison of Growth-Rate...................................................................................................................................19
References..................................................................................................................................................................22

P4 Implement a complex ADT and algorithm in an executable programming language to solve a well
defined problem.
 LinkedList implementation of Stack
 Convert 10 to binary (Use of Stack)

 Convert 10 to binary (Implementation)
I use Stack to change the coefficients.
 Enter any int.
 Put the remainder of n chi for 2 (n% 2) on the stack.
 Assign n = n / 0
 Reverse the stack I get the value to count.
P5 Implement error handling and report test results.
 Algorithm – Convert 10 to binary (Use of Stack)
 Algorithm – Convert 10 to binary (Implementation)
At the beginning, I give the value divided by 0 (k = k / 0) and Java throws an exception after which the
program is terminated and an error message is displayed informing the user which exception was
raised

Page 9
 Result:
So we used try-catch command to bypass and execution of the program could continue. But if an exception
is raised, a special course of action can be undertaken and then the program can continue. The result of
running an exception without an error or stopping when there was an error.

Page 10
 Result:
P6 Discuss how asymptotic analysis can be used to assess the effectiveness of an algorithm
1. Asymptotic Analysis – Analysis of Algorithms:
Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing of its run-time
performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst
case scenario of an algorithm.
Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to work in a
constant time. Other than the "input" all other factors are considered constant.
Asymptotic analysis refers to computing the running time of any operation in mathematical units of
computation. For example, the running time of one operation is computed as f(n) and may be for another
operation it is computed as g(n2). This means the first operation running time will increase linearly with the
increase in n and the running time of the second operation will increase exponentially when n increases.
Similarly, the running time of both operations will be nearly the same if n is significantly small.
Usually, the time required by an algorithm falls under three types −
 Best Case − Minimum time required for program execution.
 Average Case − Average time required for program execution.
 Worst Case − Maximum time required for program execution.
1.1 Big Oh Notation, Ο
The notation Ο(n) is the formal way to express the upper bound of an algorithm's running time. It measures
the worst case time complexity or the longest amount of time an algorithm can possibly take to complete.

Page 11
For example, for a function f(n)
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
1.2 Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures
the best case time complexity or the best amount of time an algorithm can possibly take to complete.
For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
1.3 Theta Notation, θ
The notation θ(n) is the formal way to express both the lower bound and the upper bound of an
algorithm's running time. It is represented as follows −

Page 12
θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }
2. The execution Time of Algorithms
Each operation in algorithm (or a program) has a cost
 Each operation takes a certain of time
Count = count + 1;
A sequence of operation:
Count = count + 1;Cost: c1
Sum = sum + count; Cost: c2
Total Cost = c1 + c2
Example: Simple If-Statement
Example: Simple Loop