ASSIGNMENT 2 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

❒ SummativeDate
Re-submission Feedback: ❒Received
Date 2nd submission
Resubmission Feedback:

Student Name Student ID GCD18499

Class GCD0704 Assessor name

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

P4 P5 P6 P7 M4 M5 D3 D4

1
Grade: Assessor Signature: Date:
Signature & Date:
List of figures

Figure 1: Code 1.............................................................................................................................................................................................7

Figure 2: Code 2.............................................................................................................................................................................................8
Figure 3: Code 3.............................................................................................................................................................................................9
Figure 4: Code 4...........................................................................................................................................................................................10
Figure 5: Error handling program.............................................................................................................................................................12
Figure 6: Common Asymptotic Notations.................................................................................................................................................15
Figure 7: Big Oh...........................................................................................................................................................................................17
Figure 8: Omega...........................................................................................................................................................................................18
Figure 9: Theta.............................................................................................................................................................................................19
Figure 10: Example 1...................................................................................................................................................................................22
Figure 11: Example 2...................................................................................................................................................................................22

2
Table of content

Introduction....................................................................................................................................................................................................5

P4 Implement a complex ADT and algorithm in an executable programming language to solve a well defined problem.................6

Chapter 1: Algorithms and ADT in programming languages...................................................................................................................6

1.1 The implementation steps of the algorithm........................................................................................................................................6

2.2 Code.......................................................................................................................................................................................................6

P5 Implement error handling and report test results...............................................................................................................................11

Chapter 2: Error and result........................................................................................................................................................................11

2.1 The program performs error handling............................................................................................................................................11

2.2 Test.......................................................................................................................................................................................................13

P6 Discuss how asymptotic analysis can be used to assess the effectiveness of an algorithm...............................................................15

Chapter 3: Efficiency of the algorithm.......................................................................................................................................................15

P7 Determine two ways in which the efficiency of an algorithm can be measured, illustrating your answer with an example.......17

Chapter 4: Time efficiency and Space efficiency.......................................................................................................................................20

4.1 Time efficiency....................................................................................................................................................................................20

4.2 Space efficiency...................................................................................................................................................................................21

Reference.......................................................................................................................................................................................................23

3
 Introduction

For middleware currently under development, part of the delivery interface is how notifications can be transferred and processed across
layers. In order to transmit, typically a buffer of queue messages is deployed and for processing, systems require a stack of messages. Our
team is currently developing these types of collections for the system. We designed the ADT / algorithm for these 2 structures and
implemented the demo version with the message being a string of up to 250 characters. The demo will demonstrate some important
operations of these structures. The following is a report on the implementation of two data structures and how to measure the
effectiveness of related algorithms and evaluate the use of ADT in design and development, including complexity, exchange and
benefits.

4
P4 Implement a complex ADT and algorithm in an executable programming language to solve a well defined
problem.

Chapter 1: Algorithms and ADT in programming languages

1.1 The implementation steps of the algorithm.

 Here are the steps of the algorithm:

 Step 1: Enter the characters in the string s1 will be from 1 to 250
 Step 2: Convert characters from the string s1 to the corresponding Queue buffer.
 Step 3: If the queue is not full then put the characters into the queue.
 Step 4: Convert the characters in the Queue to s2.
 Step 5: Repeat the above steps until the string s1 is empty and the queue is empty, then 250 characters have been converted
from string s1 to string s2 with "Queue".

2.2 Code.

 Create the class and enter the required parameters in the program.

5
Figure 1: Code 1

6
 Create 2 values of s1 and s2

Figure 2: Code 2

7
 Use the "try ....catch" statement to handle the error.

Figure 3: Code 3

8
 Create the data to print to the screen

Figure 4: Code 4

9
P5 Implement error handling and report test results.

Chapter 2: Error and result

2.1 The program performs error handling.

 When running the program, there are many different types of errors that can occur, such as errors due to the mistake of the writer,
errors of input errors or unforeseen errors. And when an error occurs, Java will stop and display the error information, which is
often called ‘throw an exception / error’.
 The catch block in java is used to handle exceptions. It must be used after the try block.
 You can use multiple catch blocks with a single try block.

10
Figure 5: Error handling program

11
2.2 Test.

Number Test case Result Test log

1 Enter string “s” is empty Error

2 Enter string “s” Possibility

containing 50 characters

12
3 Enter string "s" Possibility
containing
100 characters

4 Enter string "s" Possibility

containing
250 characters

5 Enter string "s" Error

containing
more than 250 characters

13
P6 Discuss how asymptotic analysis can be used to assess the effectiveness of an algorithm

Chapter 3: Efficiency of the algorithm

 Asymptotic analysis of an algorithm refers to the determination of the mathematical / framework limit of its runtime performance.
It tries to estimate time as a function of input size. For example, when analyzing the worst-case runtime of the list of numbers, we
would consider how long it takes to function as a length of the input list.

Figure 6: Common Asymptotic Notations

14
 This analysis requires a variable input for the algorithm, otherwise the job is assumed to require a constant amount of time. All
factors other than input operations are considered to be constant.
 Asymptotic analysis refers to the running time calculation of any activity in a calculation unit. For example, that is the running
time of an activity is f (n) and for other activities is calculated as g (n2). It is realized that the first run time will increase linearly
with increasing n and the running time of the second operation will increase exponentially as n increases. And the running time of
the two operations will be the same if n is the smallest.
 Typically, the time required by the algorithm falls into three categories -
 Best case - The minimum time required to execute the program.
 Average case - The average time required to execute the program.
 Worst case - The maximum time required to execute the program.
 Asymptotic analysis is bound to input if there is no input to the algorithm, it is concluded to be operating in constant time.
 In addition, in Proximity Analysis, we always talk about input sizes larger than constant values. It is possible that these large
inputs are never provided to your software and the symptom is slower, which always works better for your specific situation. So
eventually you can choose a slower but faster algorithm for your software.
 Although run-time performance can be calculated with a variety of functions, the algorithm's limited behavior is represented
graphically by using simple notation:
 Ο(n): Is the upper limit of the running time of the algorithm and measures the worst case of how long the algorithm may take
to complete a certain operation.
 Ω(n): Is the lower limit of the algorithm's runtime and measures the best case scenario of how long the algorithm may take to
complete a given operation.
 Θ(n): Diagram of both the upper and lower running time boundaries, with the average case scenario expressed as the average
between each border.

15
1. Big Oh Notation (Ο):

 Ο(n): is the official way to express the upper limit of the running time of the algorithm. It measures the complexity of the worst-
case time or the longest time the algorithm can take to complete.

Figure 7: Big Oh

16
2. Omega Notation (Ω):

 Ω(n): is the official way to represent the lower limit of the algorithm runtime. It measures the best case time complexity or the
best amount of time the algorithm can take to complete.

Figure 8: Omega

17
3. Theta Notation (Θ):

 Θ(n): is the official way to represent both the lower and the upper limits of the algorithm runtime. It is presented as follows:

Figure 9: Theta

18
P7 Determine two ways in which the efficiency of an algorithm can be measured, illustrating your answer with
an example.

Chapter 4: Time efficiency and Space efficiency

 Time efficiency and spatial effectiveness depend on a number of things, including:

 Quality of the code.
 The nature of the processor.
 Input data.

4.1 Time efficiency.

 Time efficiency is a function that describes the amount of algorithm time used by the algorithm's number of inputs. "Time" can
mean the number of memory accesses made, the number of comparisons between integers, the number of times an internal loop
has been executed, or some other natural unit involved,… amount of real time that the algorithm will use.
 Theory:
 Algorithm analysis, often using time complexity analysis to estimate run time as a function of the size of the input data.
 Expected run time:
 Number of activities of Method 1: select the activity (s) most frequently performed and determines the number of
activities performed each time.
 2-step counting method: determining the total number of steps, possibly coding, performed by the program.
 Actual runtime depends on many factors:
 Computer speed: CPU (not just clock speed), I / O, etc.
 Compiler, compiler option.
 Amount of data.
 The last actual data
 Practice:

19
  Use benchmarks to calculate algorithm time. Many programming languages have functions available that provide CPU time.
 By executing the code, we can:
 Benchmarking: running programs on different data sets and measuring performance.
 Profile: A report of the amount of time spent on each program routine, used to find and correct hotspots in it.

4.2 Space efficiency.

 Spatial efficiency is a function that describes the amount of memory (space) that an algorithm uses according to the algorithm's
number of inputs. We often talk about the "auxiliary" memory needed, not counting the memory needed to store input. Again, we
use natural units (but have a fixed length) to measure this. We can use bytes, the number of fixed-sized structures, and so on.
Finally, the function we devised will be independent of the actual number of bytes needed to represent the unit.
 Theory:
 This section will involve the use of memory resources while the algorithm is being implemented, often using spatial
complexity analysis to estimate the required runtime memory as a function such as the size of the data. Whether. Input data.
Results are usually specified by Big O.
 Practice:
 There are up to four aspects of memory usage to consider:
 The amount of memory required to hold the code for the algorithm.
 The amount of memory required for input data.
 The amount of memory required for all output data
 The amount of memory required as the workspace during the calculation.
 Example code in Java:
 Example 1: Queues between 10 and 20 and enter the string s as paragraph include 150 characters:

20
 Figure 10: Example 1

 Example 2: Queues between 20 and 80 and enter the string s as paragraph include 150 characters:

Figure 11: Example 2

 Result: After doing two examples, it showed us: the more space, the less time and vice versa, the more time and space. That
proves that the hypothesis is true.

21
Reference

https://www.tutorialspoint.com/data_structures_algorithms/asymptotic_analysis

https://www.cs.bham.ac.uk/~jxb/DSA/dsa.pdf

http://jcsites.juniata.edu/faculty/rhodes/cs2/ch12a.htm

https://en.wikipedia.org/wiki/Algorithmic_efficiency#Theory

22