ASSIGNMENT 2 FRONT SHEET

Qualification BTEC Level 5 HND Diploma in Computing

Unit number and title Unit 19: Data Structures and Algorithms

Submission date 5/5/2024 Date Received 1st submission

Re-submission Date Date Received 2nd submission

Student Name Trần Hũu Vương Student ID GCH190643

Class SP_24_1649_RE_SP24 Assessor name Đỗ Hồng Quân

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
 Summative Feedback:  Resubmission Feedback:

Grade: Assessor Signature: Date:

Internal Verifier’s Comments:

IV Signature:

Contents
P4 .................................................................................................................................................................................. 3
 Linked list ................................................................................................................................................................ 3
how it works: ........................................................................................................................................................... 4
Explain: .................................................................................................................................................................... 5
ArrayList ADT ............................................................................................................................................................ 8
How it work? ........................................................................................................................................................... 9
Explain ................................................................................................................................................................... 10
3. Implement error handling and report test results (P5) ..................................................................................... 12
3.1. Testing plan .................................................................................................................................................... 12
3.2 Evaluation ........................................................................................................................................................ 13
P6 ................................................................................................................................................................................ 13
Asymptotic Notations: ......................................................................................................................................... 13
P7 ................................................................................................................................................................................ 16
Time Complexity ................................................................................................................................................... 16
Space Complexity.................................................................................................................................................. 17
+ Input space ......................................................................................................................................................... 17
+ Auxiliary space................................................................................................................................................... 17
Ex01 ............................................................................................................................................................................ 18
EX02 ........................................................................................................................................................................... 19
REFERENCES.......................................................................................................................................................... 20

P4
Linked list
A singly linked list is a data structure consisting of a sequence of elements where each
element points to the next one in the sequence. Unlike arrays, linked lists do not have a
fixed size in memory and elements can be efficiently inserted or removed from any
position in the list. However, accessing elements in a linked list can be less efficient
compared to arrays because you have to traverse the list from the beginning to reach a
specific element.
In a singly linked list, each element is called a "node." Each node contains two parts: the
data and a reference (or pointer) to the next node in the sequence. The first node in the list
is called the "head," and the last node typically has a reference to null to indicate the end of
the list.

how it works:
Initialization: To create a singly linked list, you typically start by creating a "head" node.
This node serves as the starting point of the list.

Adding Nodes: To add new elements to the list, you create a new node with the desired
data and adjust the pointers to incorporate the new node into the existing list. Typically,
you add nodes to the end of the list, but you can also insert them at the beginning or in the
middle.

Traversal: To access or manipulate elements in the list, you traverse the list by following
the pointers from one node to the next until you reach the desired node. This traversal
process allows you to search for specific elements, retrieve data, delete nodes, or perform
other operations.

Accessing Elements: Unlike arrays, where elements can be accessed directly using an
index, accessing elements in a linked list usually requires traversing the list from the head
node to the desired node. This traversal process can be less efficient than array indexing,
especially for large lists.

Removing Nodes: To remove nodes from the list, you adjust the pointers of the
neighboring nodes to bypass the node you want to delete, effectively removing it from the
sequence. Once the node is no longer referenced by any other node, it can be garbage-
collected to free up memory.

Termination: Singly linked lists typically terminate with a node whose next pointer is set to
null or None, indicating the end of the list.

Overall, singly linked lists provide dynamic memory allocation, efficient insertion and
deletion operations (especially at the beginning or end of the list), and flexibility in
managing sequential data. However, they may not be as efficient for random access or
searching as arrays due to the need for sequential traversal.
Explain:
The data field will be stored between the value and next will be a pointer to point to its
next straight.

Head is the first value and tail is the last value. Initially they are both null

Befor

After

Befor

After adding

First, allocate a new node and input the data. After that, we will consider two cases. If the
initial value is empty (I,e, the linked list is empty) assign the anode value to head and tail.
At this point, the linked list has 1 element. If the linked list is not empty, we will create a
variable current and start looking for the last node using the while loop as shown. After
loop is finished , we have found the last node. Start assigning it to the tail. At this point ,
the tail is the newly added anode element.

Befor
After

Befor

After adding:

First, allocate a new node and input the data. After that , we will consider two cases. If the
initial value is empty, assign the anode value to head. At this point, the linked list has 1
element . If the linked list is not empty, direct the next cursor to the head. Start assigning it
to the head. At this point, the head is the newly added anode element

Befor

After
Befor

After remove

This is the function that removes the top value of the linked list. If the list is not empty,
create a temp variable. Change the head value and use the variable temp to disconnect the
first element from the linked list

Befor

After

Befor

After remove
This is the function that removes the last value of the linked list. The first is to find the
second element from the bottom of the linked list. Create a current variable as shown and
use the while loop to find the second element from the bottom of the linked list . After
finding that element assign a null value to the element after it

The toString() method return the string representation of the object. If any object is printed,
the Java compiler calls the toString() method. So override the toString() method, which
returns the desired output, it can be the state of an object.

ArrayList ADT
An ArrayList is a dynamic array implementation of the List interface in Java. It's part of
the Java Collections Framework and provides resizable arrays. ArrayLists automatically
resize themselves as more elements are added to them. They are similar to arrays but offer
more functionality and flexibility. ArrayLists also allow you to add, remove, access, and
manipulate elements easily.

Here's a basic rundown of its key features:

Dynamic Resizing: ArrayLists can grow or shrink dynamically to accommodate adding or

removing elements. When the internal array capacity is exceeded, it automatically
reallocates memory to a larger array.

Random Access: Elements within an ArrayList can be accessed directly using their index,
much like arrays. This allows for fast access to elements at any position.

Insertion and Deletion: Adding and removing elements from ArrayLists is relatively
efficient. When an element is inserted or removed, the other elements are shifted
accordingly to accommodate the change.

Implementation of List Interface: ArrayLists implement the List interface, which means
they support all the operations defined by List, such as adding elements, removing
elements, checking if an element exists, getting the size of the list, etc.

Ordered Collection: Elements in an ArrayList are ordered and maintain their insertion
order. This means that elements are stored in the order they were added and can be
accessed in that same order.
Resizable: Unlike arrays, ArrayLists are resizable. They can grow or shrink in size as
needed, making them convenient for situations where the number of elements is not known
in advance.

The underlying data structure of an ArrayList is an array of objects. When you create an
ArrayList, it internally creates an array to store the elements. As elements are added to the
ArrayList and its capacity is reached, it creates a new array with a larger capacity, typically
doubling the size of the previous array, and copies all elements from the old array to the
new one. This process is known as "resizing" and happens transparently to the user.

How it work?

Initialization: When you create an ArrayList, it starts with an initial capacity (typically 10).
An underlying array of this initial capacity is created to hold the elements.

Adding Elements: When you add elements to the ArrayList using the add() method, the
ArrayList checks if there is enough space in its internal array to accommodate the new
element. If there is sufficient space, the element is simply added to the end of the array.

Resizing: If the internal array is not large enough to hold the new element, the ArrayList
creates a new array with a larger capacity. The usual practice is to double the size of the
current array. Then, it copies all the elements from the old array to the new one.

Adding Element after Resizing: After resizing and creating a new array, the new element is
added to the end of the resized array.

Accessing Elements: You can access elements in an ArrayList using their index. Since
ArrayLists use an array internally, accessing elements by index is fast and efficient.

Removing Elements: When you remove an element from an ArrayList, it shifts all
subsequent elements to the left by one position to fill the gap left by the removed element.
This operation can be relatively costly for large ArrayLists, especially if the element being
removed is near the beginning of the list, as it may require shifting a large number of
elements.
Memory Management: ArrayLists consume more memory than arrays because they
maintain extra space to accommodate potential growth. However, they offer flexibility and
convenience in exchange for this extra memory overhead.

Overall, ArrayLists provide a convenient way to work with dynamic collections of

elements in Java, offering automatic resizing and efficient element access. However, it's
essential to be mindful of potential performance implications, especially when dealing with
large lists or frequent insertions and removals.

Explain
Befor

First I have a list that looks like 5 positions, and I'll add the color red to the first position

After add

After adding red color in the first position. Next I will add blue in the 2nd position
Next I'll add orange in the 3rd position

After the first 3 positions have been added, for the 4th position I will add pink

And finally the 5th position I will add black

I'm going to remove the black

After removing the black color, I will add purple

3. Implement error handling and report test results (P5)
3.1. Testing plan

NO Scope Operatio Testing Input Expected Actual Status

n type Output Output

1 Arrays Add Normal List[Red, List[Red, The same Passed

list Green, Green, Orange, as
Orange,Pink] Pink, Black] expected
Add(Black) Size List = 4 output
Get(4) return =
Black
Remove Normal List [4] List[Red, The same Passed
Remove(0) Green, Orange, as
,Pink, Black] expected
Size List = 4 output
Remove(4)
Return 4 get (4)
Return = Black
Remove Normal List[4] List[Red, Not the Failed
Remove[10] Green, Orange, same as
,Pink, Black] expected
Size List = 4 output
Remove (10)
Return = null
2 Linked Add Normal List[5,6,3,4,2] List[5,6,3,4,2,1] The same Passed
list Add(1) Size List = 5 as
Get(5) return = expected
1 output
Remove Normal List [5] List[5,6,3,4,2,1] The same Passed
Remove(0) Size List = 5 as
Remove(5) expected
Return 5 get (5) output
Return = 1
 Remove Normal List[5] List[5,6,3,4,2,1] Not the Failed
Remove(10) Size List = 5 same as
Remove (10) expected
Return = null output

3.2 Evaluation
There are two test cases and each test case has a failure

+ Arrays list has a test case that fails because the element you want to delete exceeds the
number of elements in the array. Specifically, you want to delete the 10th element but there
are only 4 elements in the array.

The solution is to request deletion of elements that do not exceed the number of elements
in the array

+ Linked list has a test case that fails because the element you want to delete exceeds the
number of elements in the array. Specifically, you want to delete the 10th element but there
are only 5 elements in the array.

The solution is to request deletion of elements that do not exceed the number of elements
in the array

P6
It's a method used in computer science and mathematics to describe the behavior of
functions as their input values become very large. It's particularly useful in analyzing
algorithms, as it helps us understand how their performance scales with the size of the
input. Typically, we express the complexity of an algorithm using big O notation, which
gives us an upper bound on the growth rate of the algorithm's runtime or space usage.

Asymptotic Notations:
Falling leaf notation serves as a mathematical tool for evaluating algorithm performance by
examining how their efficiency scales with increasing input size. It offers a concise method
to assess time or space complexity as input size approaches infinity. Instead of directly
comparing algorithms, the focus is on understanding the relative growth rates of
complexity. This approach abstracts away constant factors and machine-specific details,
emphasizing trends. By utilizing symbols like Big O, Big Omega, and Big Theta,
algorithms can be classified based on their worst-case, best-case, or average-case
complexity, offering valuable insights into their effectiveness.

1. Theta Notation (Θ-Notation):

Theta notation encompasses both the upper and lower limits of a function. It's employed to
evaluate the average-case complexity of an algorithm by summing the running times for all
potential input combinations and calculating their average.

Figure 1 Theta notation

Example

{ 100 , log (2000) , 10^4 } belongs to Θ(1)

{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Θ(n)

{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Θ( n2)

2. Big-O Notation (O-notation):

Big-O notation is utilized to describe the upper limit of an algorithm's runtime, serving as
an indicator of its worst-case complexity. This notation is extensively employed in
asymptotic analysis and signifies the upper boundary of a function. It denotes the
maximum time an algorithm may require, encapsulating its worst-case time complexity. In
essence, Big-O represents the highest potential output value for a given input, particularly
emphasizing the scenario where an algorithm takes the longest time to execute its
statements.
Figure 2Big-O Notation (O-notation):
Example

{ 100 , log (2000) , 10^4 } belongs to O(1)

U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to O(n)

U { (n^2+n) , (2n^2) , (n^2+log(n))} belongs to O( n^2)

3: Omega Notation (Ω-Notation):

Omega notation is a mathematical representation indicating the minimum time complexity
of an algorithm, offering insight into its best-case scenario.

Figure 3Omega Notation (Ω-Notation):

Example

{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Ω( n^2)

U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Ω(n)

U { 100 , log (2000) , 10^4 } belongs to Ω(1)

P7
Time Complexity
Time complexity, in computer science, refers to the amount of time an algorithm takes to
run based on the size of its input. It describes how the runtime of an algorithm changes as
the input data grows. Time complexity is commonly expressed using Big O notation,
which gives an upper limit on how the algorithm's runtime grows with input size.
Essentially, it helps us understand how much computational time an algorithm needs as the
input size increases, aiding in analyzing and comparing algorithm efficiency.
Space Complexity
Space complexity refers to the amount of memory an algorithm requires to execute and
produce a result. While it was once a critical consideration due to limited memory
resources, modern machines typically have ample memory, reducing the immediate
concern for most users. However, in scenarios where memory is constrained or monitored
closely, estimating space complexity remains essential. It's important to note that space
complexity can vary based on factors like the programming language, compiler, and the
specific hardware running the algorithm.

+ Input space
Input space, within the realm of machine learning and data science, denotes the entirety of
potential inputs or features that a model can receive. It encompasses the wide range of
values or configurations that the model may encounter during its training or when
processing data. Simply put, it includes all the various types of information that describe
each instance in a dataset. Recognizing the input space is vital for developing and training
machine learning models, as it guides the selection of relevant features and influences the
model's complexity and ability to generalize to new data.

+ Auxiliary space
The auxiliary space in machine learning pertains to extra or supporting information utilized
to assist in learning. This supplementary data, while not directly linked to the main task,
can offer valuable context or aid in enhancing the model's performance. It encompasses
various kinds of data, like side information or additional features, which help the model
better grasp the primary data or improve its predictive abilities. Effectively incorporating
auxiliary space can bolster the resilience and precision of machine learning models,
particularly in situations where the primary data might be restricted or nois
Ex01

Time Complexity:

The time complexity of this function also depends on the size of the input array arr. Let's
denote the size of the array as n.

The for loop iterates through each element of the array once. So, the loop has a time
complexity of O(n).

Inside the loop, the operations are constant time, such as comparisons and assignments.

Therefore, the overall time complexity of the findMax function is O(n).

Space Complexity:

The space complexity here is also O(1) because we're only using a constant amount of
extra space (maxElement), regardless of the size of the input array.

To summarize:

Time Complexity: O(n)

Space Complexity: O(1)

EX02

Time Complexity:

The time complexity of this recursive factorial function depends on the value of n.

In each recursive call, the function decrements n by 1 until n becomes 0 or 1. So, the
number of recursive calls is proportional to n.

Each recursive call involves constant-time operations, such as multiplication.

Therefore, the overall time complexity of the factorial function is O(n).

Space Complexity:

The space complexity here is O(n) because, for each recursive call, a new stack frame is
created to store the local variables and function call information.

To summarize:

Time Complexity: O(n)

Space Complexity: O(n)

REFERENCES

GeeksforGeeks (2024) Types of asymptotic notations in complexity analysis of algorithms,

GeeksforGeeks. Available at: https://www.geeksforgeeks.org/types-of-asymptotic-
notations-in-complexity-analysis-of-algorithms/ (Accessed: 05 May 2024).

Mitchell, J.A. and Thomson, M. (2017) A guide to citation.3rd edn. London: London
Publishings

Mitchell, J.A. ‘How citation changed the research world’, The Mendeley, 62(9), p70-81.

Mitchell, J.A. ‘How citation changed the research world’, The Mendeley, 62(9)
[online]. Available at: https://www.mendeley.com/reference-management/reference-
manager (Accessed: 05 May 2024).

Mitchell, J.A. (2017). How and when to reference [Online]. Available

at: https://www.howandwhentoreference.com/ (Accessed: 05 May 2024).