Assignment Data Structures and Algorithms

Student Number: HE12628

Student Name: Mazilu Ioana-Adriana

0
 Table of Contents
Introduction............................................................................................................................... 3

Task 1 .................................................................................................................................... 3

Description........................................................................................................................ 3

Linear Search................................................................................................................... 4

Bubble Sort....................................................................................................................... 6

Graphical Visualisation ................................................................................................... 8

Insertion Sort .................................................................................................................. 11

Graphical Visualisation ................................................................................................. 14

Big O Notations.............................................................................................................. 16

Complete Code .............................................................................................................. 18

Test Logs ........................................................................................................................ 19

Output.............................................................................................................................. 20

Task 2_1.............................................................................................................................. 20

Description...................................................................................................................... 20

Complete Code .............................................................................................................. 20

Shallow Copy ................................................................................................................. 25

Advantages of ArrayList ............................................................................................... 26

Disadvantages of ArrayList .......................................................................................... 26

Test Logs ........................................................................................................................ 26

Output.............................................................................................................................. 30

Task 2_2.............................................................................................................................. 30

1
 Description...................................................................................................................... 30

Complete Code .............................................................................................................. 31

Advantages of ArrayDeque that implements Deque interface ............................... 36

Disadvantages of ArrayDeque that implements Deque interface .......................... 37

Test Logs ........................................................................................................................ 37

Output.............................................................................................................................. 40

Task 2_3.............................................................................................................................. 40

Description...................................................................................................................... 40

Complete Code .............................................................................................................. 41

Advantages of PriorityQueue ...................................................................................... 45

Disadvantages of PriorityQueue ................................................................................. 45

Test Logs ........................................................................................................................ 45

Output.............................................................................................................................. 48

Task 3 .................................................................................................................................. 48

References ............................................................................................................................. 49

Appendix ................................................................................................................................. 50

2
 Introduction

This Java programming project will cover a wide range of computer science

subjects, such as data structures, sorting techniques, searching algorithms, and

object-oriented programming concepts. The exercises aim to strengthen

understanding of the Java collections framework, algorithmic efficiency, and the

practical implications of data structure selection on the behaviour and performance of

programmes. In the first task, various data structures, including bubble sort, insertion

sort, and linear search, are implemented in a given array. There are three smaller jobs

in the second task. ArrayList and Shallow copy are implemented in the first subtask;

ArrayDeque is implemented in the second subtask in place of ArrayList; and

PriorityQueue is implemented in the third subtask in place of ArrayList. In Task 3, a

reflection of this assignment is requested to underline the understanding of the

requirements, steps taken, challenges and ability to find solutions.

Task 1

Description

The first task involves a thorough analysis of the Java implementation of the

linear search algorithm and how it works to locate a particular member in an unsorted

array. The design, implementation, and discussion of the linear search will be followed

by an examination of the subtle differences between Bubble Sort and Insertion Sort.

Flowcharts, graphical visualisations, and pseudocode will be used to augment the

explanations. Code samples, testing proof, and a comparative study of the Big O

notations for the algorithms will all be presented.

3
Linear Search

Explanation

The linear search is started by comparing the first item of given array with the

searched item by user (Horstmann 2020). If matched, then the search is ended and

returns the index of the item; if not, -1 is returned to indicate that the target is not in

the list and move on to the next item.

Pseudocode

4
Flowchart

Code Snippet

5
Bubble Sort

Explanation

The stated sorting algorithm is done by swapping adjacent elements repeatedly

if these elements are present in the wrong order till no further swaps are required

(Insanudin 2019).

Pseudocode

6
Flowchart

7
Graphical Visualisation

Let assume the given array is {5,2,30,41,22}.

i)

ii)

iii)

8
iv)

v)

vi)

vii)

9
viii)

ix)

x)

xi)

10
xii)

This is the final output after bubble sorting.

Code Snippet

Insertion Sort

Explanation

The stated sorting algorithm is done by making a sorted array a single item at

a time (Ali, Nawaz and Maitlo 2021). For each iteration, a single item is taken from the

input data to find its perfect position within the sorted list and moved higher elements

up to make the space.

11
Pseudocode

12
Flowchart

13
Graphical Visualisation

Let assume the given array is {5,2,30,41,22}.

i)

ii)

iii)

14
iv)

v)

vi)

vii)

15
viii)

This is the final output after insertion sorting.

Code Snippet

Big O Notations

Time complexity of linear search algorithm: O(n).

Time complexity of bubble sort algorithm: O(n^2).

Time complexity of Insertion sort algorithm: O(n^2).

While Bubble Sort and Insertion Sort have similar worst-case and average time

complexity (O(n^2)), Insertion Sort works better with smaller arrays or arrays that are

16
almost sorted. Although it isn't related to the sorting, Linear Search has an O(n) time

complexity and is included here as part of the overall assignment.

Big O Notation Graphic

17
Complete Code

18
Test Logs

Test Case Input Expected Actual Output Result

Name Output

Linear Search {5, 2, Index 11 Index 11 Passed

30, 41,

22, 15,

25, 6,

33, 20,

13, 44,

39, 27,

5, 11}

44

Bubble Sort {5, 2, [2, 5, 5, 6, 11, [2, 5, 5, 6, 11, Passed

30, 41, 13, 15, 20, 22, 13, 15, 20, 22,

22, 15, 25, 27, 30, 33, 25, 27, 30, 33,

25, 6, 39, 41, 44] 39, 41, 44]

33, 20,

13, 44,

39, 27,

5, 11}

Insertion Sort {5, 2, [2, 5, 5, 6, 11, [2, 5, 5, 6, 11, Passed

30, 41, 13, 15, 20, 22, 13, 15, 20, 22,

22, 15, 25, 27, 30, 33, 25, 27, 30, 33,

25, 6, 39, 41, 44] 39, 41, 44]

33, 20,

19
 13, 44,

39, 27,

5, 11}

Output

Task 2_1

Description

This task is an extension of the investigation that focuses on Java object-

oriented design. A "Flight" class and a "Airline" class must be created, with the latter

using an ArrayList to manage a group of Flight objects. We will examine mutators,

constructors, accessors, and show how objects interact with one another in a Java

project. We'll also talk about the benefits and drawbacks of managing Flight objects

with an ArrayList and investigate the effects of object cloning via shallow copies.

Complete Code

20
21
22
23
24
Shallow Copy

In the Program class, the concept of shallow copy is executed. In this, original

object is preserved, and only address of the reference is copied (J Eck 2021). Here, a

clone of a Flight object is made and printed details in console. Then, destination of

original object is modified, and the object’s details are printed in console.

25
Advantages of ArrayList

i) Capability of dynamic resizing.

ii) Constant time performance.

iii) Provide built-in methods for some operations, for example, add, remove, size and

many more.

Disadvantages of ArrayList

i) Consumed huge memory.

ii) Not thread safe.

Test Logs

Test Case Input Expected Actual Output Result

Name Output

Task 2_1 Flight ID: After landed After landed Passed

FL7412, flight, details of flight, details

Destination: aircraft: of aircraft:

Paris,

26
Capacity: Flight ID: Flight ID:

123, Priority FL7412, FL7412,

Code: P10, Destination: Destination:

Flight Type: Paris, Paris,

international, Capacity: 123, Capacity:

Date: Priority Code: 123, Priority

30/12/2023 P10, Flight Code: P10,

Flight ID: Type: Flight Type:

FL9146, international, international,

Destination: Date: Date:

Australia, 30/12/2023 30/12/2023

Capacity: Flight ID: Flight ID:

187, Priority FL1235, FL1235,

Code: P27, Destination: Destination:

Flight Type: Sydney, Sydney,

cargo, Date: Capacity: 169, Capacity:

13/12/2023 Priority Code: 169, Priority

Flight ID: P19, Flight Code: P19,

FL1235, Type: Flight Type:

Destination: international, international,

Sydney, Date: Date:

Capacity: 15/5/2024 15/5/2024

169, Priority Flight ID: Flight ID:

Code: P19, FL0154, FL0154,

Flight Type: Destination: Destination:

27
international, UK, Capacity: UK, Capacity:

Date: 127, Priority 127, Priority

15/5/2024 Code: P85, Code: P85,

Flight ID: Flight Type: Flight Type:

FL0154, national, Date: national,

Destination: 10/11/2023 Date:

UK, Flight ID: 10/11/2023

Capacity: FL7913, Flight ID:

127, Priority Destination: FL7913,

Code: P85, Sydney, Destination:

Flight Type: Capacity: 149, Sydney,

national, Priority Code: Capacity:

Date: P37, Flight 149, Priority

10/11/2023 Type: Code: P37,

Flight ID: international, Flight Type:

FL7913, Date: international,

Destination: 13/6/2024 Date:

Sydney, 13/6/2024

Capacity:

149, Priority

Code: P37,

Flight Type:

international,

Date:

13/6/2024

28
 Land the

flight object

Shallow copy Destination The The Passed

of flight destination of destination of

object 2 = Original Flight Original Flight

Brisbane 2: Australia 2: Australia

The The

destination of destination of

the Cloned the Cloned

Flight: Flight:

Australia Australia

After Modifying After

the Original Modifying the

Flight 2: Original Flight

2:

The

destination of The

Original Flight destination of

2: Brisbane Original Flight

The 2: Brisbane

destination of The

the Cloned destination of

the Cloned

29
 Flight: Flight:

Australia Australia

Output

Task 2_2

Description

In order to understand how collections can operate as both a queue and a stack,

Task 2_2 ask us to convert the data structure from an ArrayList to an ArrayDeque. It

also requests to examine the advantages and disadvantages of utilising a Deque

interface over alternative data structures.

30
Complete Code

31
32
33
34
35
Advantages of ArrayDeque that implements Deque interface

i) Used as both a stack and queue.

ii) When it comes to stack operations, ArrayDeque outperforms LinkedList (push and

pop)

36
Disadvantages of ArrayDeque that implements Deque interface

i) Consumed more memory (Santos, Zhang and Mirakhorl 2022).

ii) In constant time, not have the ability to access items with the index.

iii) Null elements can’t be inserted

Test Logs

Test Case Input Expected Actual Output Result

Name Output

Task 2_2 Flight ID: After Popping After Popping a Passed

FL7412, a flight: flight:

Destination: Flight ID: Flight ID: FL0154,

Paris, FL0154, Destination: UK,

Capacity: Destination: Capacity: 127,

123, Priority UK, Capacity: Priority Code: P85,

Code: P10, 127, Priority Flight Type:

Flight Type: Code: P85, national, Date:

international, Flight Type: 10/11/2023

Date: national, Date: Flight ID: FL1235,

30/12/2023 10/11/2023 Destination: Sydney,

Flight ID: Flight ID: Capacity: 169,

FL9146, FL1235, Priority Code: P19,

Destination: Destination: Flight Type:

Australia, Sydney, international, Date:

Capacity: Capacity: 169, 15/5/2024

187, Priority Priority Code:

37
Code: P27, P19, Flight Flight ID: FL9146,

Flight Type: Type: Destination:

cargo, Date: international, Australia, Capacity:

13/12/2023 Date: 187, Priority Code:

Flight ID: 15/5/2024 P27, Flight Type:

FL1235, Flight ID: cargo, Date:

Destination: FL9146, 13/12/2023

Sydney, Destination: Flight ID: FL7412,

Capacity: Australia, Destination: Paris,

169, Priority Capacity: 187, Capacity: 123,

Code: P19, Priority Code: Priority Code: P10,

Flight Type: P27, Flight Flight Type:

international, Type: cargo, international, Date:

Date: Date: 30/12/2023

15/5/2024 13/12/2023

Flight ID: Flight ID:

FL0154, FL7412,

Destination: Destination:

UK, Paris,

Capacity: Capacity: 123,

127, Priority Priority Code:

Code: P85, P10, Flight

Flight Type: Type:

national, international,

38
Date: Date:

10/11/2023 30/12/2023

Flight ID:

FL7913,

Destination:

Sydney,

Capacity:

149, Priority

Code: P37,

Flight Type:

international,

Date:

13/6/2024

Popping a

flight object

39
Output

Task 2_3

Description

In this task, the previous two classes that are Flight and Airline classes are

copied and after that, some changes are made in the Airline class and we are asked

to use PriorityQueue instead of ArrayDeque.

40
Complete Code

41
42
43
44
Advantages of PriorityQueue

i) Based on priority, permitted retrieval of items.

ii) After adding or removing, resize itself dynamically.

Disadvantages of PriorityQueue

i) By index, cannot access any element.

ii) Not able to set maximum capacity.

Test Logs

Test Case Input Expected Actual Output Result

Name Output

Task 2_3 Flights in Landing flights Landing flights Passed

Airline on the based on their based on their

basis of the priority: priority:

priority or Landing Flight: Landing Flight:

capacity: FL7412 with FL7412 with

Flight ID: capacity 123 capacity 123

FL7412,

Destination:

45
Paris, Landing Flight: Landing Flight:

Capacity: FL0154 with FL0154 with

123, Priority capacity 127 capacity 127

Code: P10, Landing Flight: Landing Flight:

Flight Type: FL7913 with FL7913 with

international, capacity 149 capacity 149

Date: Landing Flight: Landing Flight:

30/12/2023 FL1235 with FL1235 with

Flight ID: capacity 169 capacity 169

FL0154, Landing Flight: Landing Flight:

Destination: FL9146 with FL9146 with

UK, capacity 187 capacity 187

Capacity:

127, Priority

Code: P85,

Flight Type:

national,

Date:

10/11/2023

Flight ID:

FL1235,

Destination:

Sydney,

Capacity:

169, Priority

46
Code: P19,

Flight Type:

international,

Date:

15/5/2024

Flight ID:

FL9146,

Destination:

Australia,

Capacity:

187, Priority

Code: P27,

Flight Type:

cargo, Date:

13/12/2023

Flight ID:

FL7913,

Destination:

Sydney,

Capacity:

149, Priority

Code: P37,

Flight Type:

international,

47
 Date:

13/6/2024

Output

Task 3

After ending this assignment, I gained an understanding of data structures and

object-oriented programming concepts in Java. Here, the linear search algorithm is

discussed, and two sorting algorithms Bubble Sort and Insertion Sort, are elaborated.

The first achieved learning outcome was the capability of unique distinguishing

between various data structures, for example, ArrayList, ArrayDeque, and

PriorityQueue. This is used in the perfect position for all the given tasks. In this,

concepts of package, class, object, methods, and several other things are correctly

declared and discussed. Also, Javadoc is created for the Java programming

developed in Task 2_1, 2_2 and 2_3. Javadoc is the process of commenting in Java

programming. In the Task 2_1, the concept of ArrayList and the shallow copy are

properly executed. Also, in the Task 2_2, the concept of ArrayDeque is used instead

of ArrayList. Lastly, in the Task 2_3, the concept of PriorityQueue is implemented

instead of ArrayList. In this assignment, making a robust foundation in Java is taught

also, this is provided hands-on experience in coding.

48
References

Ali, H., Nawaz, H. and Maitlo, A., 2021. Performance Analysis of Heap Sort and

Insertion Sort Algorithm. International Journal, 9(5).

Horstmann, C.S., 2020. Big Java: Early Objects. John Wiley & Sons.

Insanudin, E., 2019, November. Implementation of python source code comparison

results with Java using bubble sort method. In Journal of Physics: Conference Series

(Vol. 1280, No. 3, p. 032027). IOP Publishing.

J Eck, D., 2021. Introduction to programming using Java. Hobart and William Smith

Colleges.

Santos, J.C., Zhang, X. and Mirakhorli, M., 2022, November. Counterfeit object-

oriented programming vulnerabilities: an empirical study in Java. In Proceedings of the

1st International Workshop on Mining Software Repositories Applications for Privacy

and Security (pp. 21-28).

49
Appendix

Javadoc file

Zip file of Task 1 solution

Zip file of Task 2_1,2_2 and 2_3 solution

50