ASSIGNMENT FINAL REPORT

Qualification Pearson BTEC Level 5 Higher National 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 HOANG ANH QUAN Student ID BD00812

Class SE07203 Assessor name NGUYEN THI SU

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
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 intelligence (AI) tools used in the work. I understand that making a false declaration is
a form of malpractice.

Student’s signature

Grading grid

P1 P2 P3 P4 P5 P6 P7 M1 M2 M3 M4 M5 D1 D2 D3 D4
 Summative Feedback:  Resubmission Feedback:

Grade: Assessor Signature: Date:

Internal Verifier’s Comments:

Signature & Date:

2
 TABLE OF CONTENT
TABLE OF CONTENT...................................................................................................................................... 3
TABLE OF FIGURE.......................................................................................................................................... 5
LIST OF TABLE............................................................................................................................................... 5
INTRODUCE.................................................................................................................................................. 5
CHAPTER 1: Examine abstract data types, concrete data structures and algorithms (LO1).........................6
1.1 . Create a design specification for data structures, explaining the valid operations that can be
carried out on the structures.(P1).............................................................................................................6
1.1.1 Definition and Role of Abstract Data Types (ADTs)......................................................................6
1.1.2 Description of Each Data Structure: Stack, Queue, Linked List.....................................................8
1.1.3 Specific Illustrative Examples......................................................................................................11
1.1.4 Analysis of Operations................................................................................................................15
1.2 Determine the operations of a memory stack and how it is used to implement function calls in a
computer.(P2)......................................................................................................................................... 16
1.2.1 Overview of the memory stack.................................................................................................. 16
1.2.2 How the Memory Stack Works...................................................................................................18
1.2.3 Stack and Recursion................................................................................................................... 18
1.2.4 Advantages and Disadvantages of the Memory Stack................................................................20
1.2.5 Visual Illustration of the Memory Stack.....................................................................................22
1.3 Illustrate, with an example, a concrete data structure for a First in First out (FIFO) queue. (M1)....24
1.3.1 Overview of the FIFO Queue...................................................................................................... 24
1.3.2 Basic Operations of a Queue......................................................................................................25
1.3.3 Implementing a Queue Using an Array.......................................................................................25
1.3.4 Implementing a Queue Using a Linked List.................................................................................31
1.3.5 Comparison of the Two Implementations..................................................................................35
1.4 Compare the performance of two sorting algorithms.(M2)..............................................................38
1.4.1 Overview of Sorting Algorithms..................................................................................................38
1.4.2 Description of the Two Algorithms.............................................................................................39
1.4.3 Comparison of the Two Algorithms: Insertion Sort and Selection Sort......................................42

3
 1.4.4 Practical Testing......................................................................................................................... 44
CHAPTER 2: Specify abstract data types and algorithms in a formal notation (LO2)..................................48
2.1 Specify the abstract data type for a software stack using an imperative definition.(P3)..................48
2.1.1 Overview of ADT and Imperative Definition...............................................................................48
2.1.2 Example of Defining an ADT Using the Imperative Approach.....................................................48
2.1.3 Implementation of the Example Using Pseudocode or Java.......................................................50
2.1.4 Advantages of Imperative Definition..........................................................................................54
2.1.5 Practical Application of the Stack ADT........................................................................................55
2.2 Examine the advantages of encapsulation and information hiding when using an ADT.(M3)..........56
2.2.1 Definition of Concepts................................................................................................................56
2.2.2 Benefits of Encapsulation and Information Hiding When Using ADTs........................................57
2.2.3 Illustrative Example.................................................................................................................... 58
2.2.4 Comparison Before and After Applying Encapsulation and Information Hiding.........................61
CHAPTER 3: Implement complex data structures and algorithms (L03).....................................................64
3.1 Implement a complex ADT and algorithm in an executable programming language to solve a well-
defined problem. (P4)............................................................................................................................. 64
3.1.1 Selection of a Specific Problem.................................................................................................. 64
3.1.2 ADT and Algorithm Used............................................................................................................ 65
3.1.3 Program Implementation...........................................................................................................67
3.1.4 Implementation Analysis............................................................................................................72
3.1.5 Results and Testing.....................................................................................................................73
3.2 Implement error handling and report test results. (P5)....................................................................74
3.2.1 Error Handling............................................................................................................................ 74
3.2.2 Test Results Reporting................................................................................................................77
3.3 Demonstrate How the Implementation of an ADT/Algorithm Solves a Well-Defined Problem (M4)
................................................................................................................................................................ 82
3.3.1 Problem Definition..................................................................................................................... 83
3.3.2 Solution Implementation............................................................................................................83
3.3.3 Solution Analysis.........................................................................................................................88
3.3.4 Test Run Results......................................................................................................................... 90

4
CHAPTER 4: Assess the effectiveness of data structures and algorithms (L04)..........................................95
4.1 Discuss how asymptotic analysis can be used to assess the effectiveness of an algorithm. (P6)......95
4.1.1 What is Asymptotic Analysis?.....................................................................................................95
4.1.2 Asymptotic Notations.................................................................................................................96
4.1.3 Asymptotic Analysis Process.......................................................................................................97
4.1.4 Illustrative Example.................................................................................................................... 99
4.1.5 Benefits of Asymptotic Analysis................................................................................................101
4.1.6 Practical Applications of Asymptotic Analysis..........................................................................103
4.1.7 How to Present Asymptotic Analysis in a Report......................................................................104
4.2 Determine two ways in which the efficiency of an algorithm can be measured, illustrating your
answer with an example.(P7)................................................................................................................105
4.2.1 What is Algorithm Efficiency?...................................................................................................105
4.2.2 Measuring Execution Time.......................................................................................................106
4.2.3 Measuring Space Usage............................................................................................................108
4.2.4 Illustrative Comparison Using Graphs......................................................................................110
4.3 Interpret what a trade-off is when specifying an ADT, using an example to support your answer.
(M5)...................................................................................................................................................... 112
4.3.1 Definition and Meaning of Trade-offs in ADTs..........................................................................112
4.3.2 Factors to Consider When Making Trade-offs in ADTs.............................................................113
4.3.3 Illustrating Trade-offs Through Examples.................................................................................114
4.3.4 Implementation Example: ArrayList vs. LinkedList...................................................................115
4.3.4.1 Using ArrayList for a To-Do List..........................................................................................115
4.3.4.2 Using LinkedList for a To-Do List........................................................................................116
4.3.4.3 Measuring Execution Time for Both Implementations......................................................117
4.3.5 Evaluation of Trade-offs........................................................................................................... 121
CONCLUSION............................................................................................................................................ 122
EVALUATION............................................................................................................................................. 123
REFERENCE............................................................................................................................................... 124

5
 TABLE OF FIGURE
Figure 1-1: Abstract Data Type (ADT)......................................................................................................... 11
Figure 1-2: Stack......................................................................................................................................... 12
Figure 1-3: Queue....................................................................................................................................... 13
Figure 1-4: Linked List................................................................................................................................. 14
Figure 1-5: Source code of Stack example..................................................................................................16
Figure 1-6: Output of Stack example code................................................................................................. 16
Figure 1-7: Source code of Queue example................................................................................................17
Figure 1-8: Output of Queue example code...............................................................................................17
Figure 1-9: Source code of Linked List example..........................................................................................19
Figure 1-10: Output of Linked List example code.......................................................................................19
Figure 1-11: Memory stack.........................................................................................................................21
Figure 1-12: Recursion................................................................................................................................ 23
Figure 1-13: Example of recursion..............................................................................................................24
Figure 1-14: Output of recursion example..................................................................................................24
Figure 1-15: Stack Visualization..................................................................................................................27
Figure 1-16: FIFO Queue.............................................................................................................................28
Figure 1-17: Example Implementation Queue using array (part 1)............................................................33
Figure 1-18: Example Implementation Queue using array (part 2)............................................................33
Figure 1-19: Output of Queue implementation..........................................................................................34
Figure 1-20: Example Implementation Queue using LinkedList (part 1).....................................................38
Figure 1-21: Example Implementation Queue using LinkedList (part 2).....................................................38
Figure 1-22: Output of implementation Queue using LinkedList................................................................39
Figure 1-23: Sorting algorithms.................................................................................................................. 42
Figure 1-24: Insertion Sort..........................................................................................................................44
Figure 1-25: Selection Sort......................................................................................................................... 45
Figure 1-26: Code to measure time of 2 algorithm (part 1)........................................................................49
Figure 1-27: Code to measure time of 2 algorithm ( part 2).......................................................................50
Figure 1-28: Measure time of 2 algorithm output......................................................................................51

6
Figure 2-1: Java code to implement the stack ADT.....................................................................................56
Figure 2-2: Output of implement the stack ADT.........................................................................................57
Figure 2-3: Encapsulation........................................................................................................................... 60
Figure 2-4: Information hiding....................................................................................................................61
Figure 2-5: Illustrative Example.................................................................................................................. 64
Fifure 2-6: Output of Illustrative Example.................................................................................................. 64
Figure 2-7: Before Applying Encapsulation and Information Hiding...........................................................65
Figure 2-8: Direct Access............................................................................................................................ 66
Figure 2-9: After Applying Encapsulation and Information Hiding..............................................................67
Figure 3-1: student list is implemented using an ArrayList<Student>........................................................69
Figure 3-2: Sorting Algorithm..................................................................................................................... 70
Figure 3-3: Searching Algorithm................................................................................................................. 70
Figure 3-4: Ranking Algorithm.................................................................................................................... 71
Figure 3-5: Encapsulation of program........................................................................................................ 72
Figure 3-6: Abstraction of program............................................................................................................ 72
Figure 3-7: Main.java class......................................................................................................................... 73
Figure 3-8: ArrayList<Student> to store student........................................................................................73
Figure 3-9: Student’s attributes..................................................................................................................74
Figure 3-10: Menu-driven approach to interact with the user...................................................................76
Figure 3-11: Preventing Invalid Input for Numerical Values.......................................................................78
Fifure 3-12: Preventing Duplicate Student IDs code...................................................................................79
Figure 3-13: Input to check Preventing Duplicate Student IDs...................................................................79
Figure 3-14: Check Preventing Duplicate Student IDs output.....................................................................79
Figure 3-15: Handling Student Not Found Errors code (part 1)..................................................................80
Figure 3-16: Handling Student Not Found Errors code (part 2)..................................................................80
Figure 3-17: Handling Empty Student List Errors code...............................................................................80
Figure 3-18: Preventing Invalid Menu Choices code...................................................................................81
Figue 3-19: Test Case: Entering non-numeric values for marks..................................................................81
Figure 3-20: Expected Output of test Case: Entering non-numeric values for marks.................................82
Figure 2-21: Actual output of test Case: Entering non-numeric values for marks......................................82
7
Figure 3-22: Test Case: Adding a student with an existing ID.....................................................................82
Figure 3-23: Expected output of test Case: Adding a student with an existing ID......................................82
Figure 3-24:Actual output of test Case: Adding a student with an existing ID............................................82
Figure 3-25: Input of Test Case 1: Searching for an existing student..........................................................83
Figure 3-26:Expected output of Test Case 1: Searching for an existing student.........................................83
Figure 3-27: Actual output of Test Case 1: Searching for an existing student............................................83
Figure 3-28: Input of Test Case 2: Searching for a non-existent student....................................................83
Figure 3-29: Expected output of Test Case 2: Searching for a non-existent student..................................83
Figure 3-30: Actual output of Test Case 2: Searching for a non-existent student.......................................84
Figure 3-31: Test Case 1: Sorting students based on their average marks (Before Sorting).......................84
Figure 3-32: Test Case 1: Sorting students based on their average marks (After Sorting)..........................84
Figure 3-33: Input of Test Case: Attempting to delete a student who is not in the system........................84
Figure 3-34: Expected output of Test Case: Attempting to delete a student who is not in the system......84
Figure 3-35: Actual output of Test Case: Attempting to delete a student who is not in the system..........85
Figure 3-36: Input of Test Case: Sorting or displaying students when no students exist............................85
Figure 3-37: Expected output of Test Case: Sorting or displaying students when no students exist..........85
Figure 3-38: Actual output of Test Case: Sorting or displaying students when no students exist..............85
Figure 3-39: Input of Test case: Enter invalid choice..................................................................................86
Figure 3-40: Actual of Test case: Enter invalid choice.................................................................................86
Figure 3-41: Student Class.......................................................................................................................... 88
Figure 3-42: StudentManager class............................................................................................................ 89
Figure 3-43: Adding a Student.................................................................................................................... 90
Figure 3-44: Editing a Student.................................................................................................................... 90
Figure 3-45: Deleting a Student..................................................................................................................91
Figure 3-46: Sorting Students by Score.......................................................................................................91
Figure 4-47: Searching for a Student.......................................................................................................... 92
Figure 3-48: Displaying All Students........................................................................................................... 92
Figure 3-49: Test Run Results Setting the Maximum Number of Students.................................................94
Figure 3-50: Example Runs of Adding Students (part 1).............................................................................95
Figure 3-51: Example Runs of Adding Students (part 2).............................................................................95
8
Figure 3-52: Example Runs of Adding Students (part 3).............................................................................95
Figure 3-53: Example Runs of Adding Students (part 4).............................................................................95
Figure 3-54: Example run of Assigning Marks to a Student (part 1)...........................................................96
Figure 3-55: Example run of Assigning Marks to a Student(part 2)............................................................96
Figure 3-56: Example run of Searching for a Student (part 1)...................................................................96
Figure 3-57: Example run of Searching for a Student (part 2)....................................................................97
Figure 3-58: Example run of Sorting Students by Scores (part 1)...............................................................97
Figure 3-59: Example run of Sorting Students by Scores (part 2)...............................................................97
Figure 3-60: Example run of Sorting Students by Scores (part 3)...............................................................97
Figure 3-61: Example run of Editing a Student’s Name..............................................................................97
Figure 3-62: Example run of Deleting a Student (part 1)............................................................................98
Figure 3-63: Example run of Deleting a Student (part 2)............................................................................98
Figure 3-64: Displaying All Students........................................................................................................... 98
Figure 3-65: Handling an Empty Student List(part 1)..................................................................................98
Figure 3-66: Handling an Empty Student List(part 2)..................................................................................99
Figure 4-1: Example: Finding the Maximum Element in an Array.............................................................102
Figure 4-2: Example: Summing Elements in an Array (O(n)).....................................................................103
Figure 4-3: Example: Nested Loop (O(n²))................................................................................................104
Figure 4-4: Example: Comparing Linear Search vs. Binary Search............................................................111
Figure 4-5: Output of Example: Comparing Linear Search vs. Binary Search............................................111
Figure 4-6: Example: Comparing Iterative vs. Recursive Factorial............................................................113
Figure 4-7: Out put of Example: Comparing Iterative vs. Recursive Factorial...........................................114
Figure 4-8: Graph: Execution Time vs Input Size.......................................................................................115
Figure 4-9: Graph: Space Usage vs Input Size...........................................................................................116
Figure 4-10: Using ArrayList for a To-Do List.............................................................................................120
Figure 4-11: Output of Using ArrayList for a To-Do List............................................................................120
Figure 4-12: Using LinkedList for a To-Do List...........................................................................................121
Figure 4-13: Output of Using LinkedList for a To-Do List..........................................................................121
Figure 4-14: Measuring Execution Time for Both Implementations.........................................................123
Figure 4-15: Output of Measuring Execution Time for Both Implementations.........................................124
9
 LIST OF TABLE
Table 1-1: Comparison................................................................................................................................15
Table 1-2: Stack Operations........................................................................................................................20
Table 1-3: Queue Operations..................................................................................................................... 21
Table 1-4: Linked List Operations............................................................................................................... 21
Table 1-5: Advantages and Disadvantages of the Memory Stack...............................................................26
Table 1-6: Comparison of the Two Implementations.................................................................................42
Table 1-7: Comparison of the Two Algorithms...........................................................................................49
Table 3-1: Test results reporting.................................................................................................................87
Table 4-1: Summary of Examples............................................................................................................. 106
Table 4-2: Space Complexity Comparison................................................................................................ 115
Table 4-3: Searching for a student in a list of increasing size...................................................................115
Table 4-4 : Space Usage Comparison........................................................................................................116
Table 4-5: Choosing Between an Array and a Linked List for a To-Do List................................................119
Table 4-6 : Performance Results & Proof..................................................................................................125
Table 4-7 : Final Evaluation.......................................................................................................................125
Table 4-8 : Time Complexity Trade-offs....................................................................................................126
Table 4-9 : Space Complexity Trade-offs.................................................................................................. 126
Table 4-10 : Performance Trade-offs Based on Real Execution Time.......................................................127
Table 4-11 : When to Choose Each Data Structure?.................................................................................127

INTRODUCE
I am currently employed at Softnet Development Ltd, a software company specializing in networking
solutions. Our company has been awarded a significant contract to design and implement a middleware
solution that will interface with various systems as part of a service delivery partnership project. This

10
middleware solution includes a computer provisioning interface that utilizes SOAP, HTTP, JML, and CLI
protocols, while the backend communicates with telecommunications providers through CLI.

In my role as an internal software developer, I have been entrusted with the responsibility to educate my
colleagues on the creation and utilization of Abstract Data Types (ADTs). As part of this initiative, I have
been tasked with preparing a presentation that demonstrates how ADTs can enhance software design,
development, and testing for all collaborating partners. Additionally, I am required to compile an
introductory report that formalizes the specification of ADTs and algorithms for distribution among our
partners.

This assignment aims to explore the significance of ADTs in software development, providing insights
into their specifications and practical applications. Through this exploration, I hope to contribute to a
deeper understanding of how ADTs can improve the efficiency and effectiveness of software solutions in
our industry.

CHAPTER 1: Examine abstract data types, concrete data structures

and algorithms (LO1)
1.1 . Create a design specification for data structures, explaining the valid
operations that can be carried out on the structures.(P1)

1.1.1 Definition and Role of Abstract Data Types (ADTs)

Definition: “An Abstract Data Type (ADT) is a mathematical model for data types in which a data type's
behavior is defined by a set of values and a set of operations that can be performed on those values,
without specifying the implementation details. This allows users to interact with the data type through a
defined interface, promoting abstraction and encapsulation in programming.”

Figure 1-1: Abstract Data Type (ADT)

11
Role of ADTs: ADTs play a crucial role in software development and design for several reasons:

 Encapsulation: ADTs encapsulate data and operations, allowing users to interact with the data
structure without needing to understand its internal workings. This promotes modularity and
separation of concerns.

 Example: A Stack ADT allows users to push and pop elements without needing to know how
the stack is implemented (e.g., using an array or a linked list).

 Reusability: By defining a clear interface, ADTs can be reused across different programs and
applications. Developers can implement the same ADT in various ways (e.g., using arrays or linked
lists) without changing the interface.

 Example: A Queue ADT can be implemented using an array or a linked list, but the operations
(enqueue, dequeue, front) remain the same for users.

 Maintainability: Changes to the implementation of an ADT do not affect the code that uses it, as
long as the interface remains consistent. This makes it easier to maintain and update software.

 Example: If a Linked List ADT is optimized for performance, the users of the linked list do not
need to change their code as long as the interface (insert, delete, traverse) remains the same.

 Abstraction: ADTs provide a level of abstraction that simplifies complex data management tasks.
Users can work with high-level operations without needing to manage the low-level details.

 Example: When using a Dictionary ADT, users can add, remove, or search for key-value pairs
without needing to know how the underlying data structure (like a hash table) is
implemented.

 Interoperability: ADTs can facilitate communication between different parts of a program or

between different programs, as they provide a standard way to interact with data structures.

 Example: A Graph ADT can be used in various algorithms (like Dijkstra's or A* search) without
needing to change the way the graph is represented, allowing for easy integration into
different systems.

1.1.2 Description of Each Data Structure: Stack, Queue, Linked List

a) Stack

12
 Figure 1-2: Stack

Definition: A stack is an abstract data type that follows the Last In, First Out (LIFO) principle, meaning
that the last element added to the stack is the first one to be removed. Stacks are often visualized as a
collection of items stacked on top of each other.

 Operations:

 Push: Adds an element to the top of the stack.

 Pop: Removes and returns the element from the top of the stack.

 Peek (or Top): Returns the element at the top of the stack without removing it.

 IsEmpty: Checks if the stack is empty.

 Use Cases: Stacks are commonly used in scenarios such as:

 Function call management (call stack).

 Undo mechanisms in applications.

 Syntax parsing in compilers.

b) Queue

13
 Figure 1-3: Queue

Definition: A queue is an abstract data type that follows the First In, First Out (FIFO) principle, meaning
that the first element added to the queue is the first one to be removed. Queues can be visualized as a
line of people waiting for service.

 Operations:

 Enqueue: Adds an element to the end of the queue.

 Dequeue: Removes and returns the element from the front of the queue.

 Front (or Peek): Returns the element at the front of the queue without removing it.

 IsEmpty: Checks if the queue is empty.

 Use Cases: Queues are commonly used in scenarios such as:

 Task scheduling in operating systems.

 Managing requests in web servers.

 Breadth-first search algorithms in graph theory.

c) Linked List

14
 Figure 1-4: Linked List

Definition: A linked list is a linear data structure where elements, called nodes, are stored in a sequence.
Each node contains two parts: the data and a reference (or link) to the next node in the sequence. Unlike
arrays, linked lists do not require contiguous memory allocation.

 Operations:

 Insert: Adds a new node to the list at a specified position (beginning, end, or middle).

 Delete: Removes a node from the list.

 Search: Finds a node with a specific value.

 Traverse: Visits each node in the list to perform an operation (e.g., print values).

 Use Cases: Linked lists are commonly used in scenarios such as:

 Implementing dynamic arrays or other data structures (like stacks and queues).

 Managing memory allocation in systems where the size of data is not known in advance.

 Representing polynomial expressions or adjacency lists in graph representations.

Compare:

Table 1-1: Comparison

Feature Stack Queue Linked List
Definition A collection of A collection of A linear collection of
elements that follows elements that follows elements (nodes)
the Last In, First Out the First In, First Out where each node
(LIFO) principle. (FIFO) principle. contains data and a
reference to the next
node.
Basic Operations Push, Pop, Peek, Enqueue, Dequeue, Insert, Delete, Search,
IsEmpty Front, IsEmpty Traverse
Access Method Last element added is First element added is Elements can be
accessed first (top of accessed first (front of accessed sequentially;
the stack). the queue). no direct access to
specific elements.
Use Cases Function call Task scheduling, print Dynamic memory
management, undo job management, allocation,
mechanisms, breadth-first search. implementing other
expression evaluation. data structures (like
stacks and queues),

15
 managing playlists.
Memory Allocation Typically implemented Typically implemented Dynamic memory
using arrays or linked using arrays or linked allocation; nodes can
lists; can be dynamic. lists; can be dynamic. be scattered in
memory.
Complexity (Time) Push: O(1), Pop: O(1), Enqueue: O(1), Insert: O(1) (at head),
Peek: O(1) Dequeue: O(1), Front: O(n) (at tail or middle),
O(1) Delete: O(n) (search
first), Search: O(n)
Implementation Can be implemented Can be implemented Implemented using
using arrays or linked using arrays or linked nodes with pointers to
lists. lists the next node.

1.1.3 Specific Illustrative Examples

a) Stack

Figure 1-5: Source code of Stack example

Output:

16
 Figure 1-6: Output of Stack example code

b) Queue

Figure 1-7: Source code of Queue example

Output:

Figure 1-8: Output of Queue example code

17
c) Linked List

Figure 1-9: Source code of Linked List example

18
Ouput:

Figure 1-10: Output of Linked List example code

1.1.4 Analysis of Operations

In this section, I will analyze the operations of the three data structures: Stack, Queue, and Linked List.
The analysis will focus on the time complexity of each operation, as well as the implications of these
complexities in practical applications.

a) Stack Operations

Table 1-2: Stack Operations

Operation Description Time Complexity
Push Adds an element to the top of O(1)
the stack.
Pop Removes and returns the O(1)
element from the top of the
stack.
Peek Returns the element at the top O(1)
of the stack without removing it.
IsEmpty Checks if the stack is empty. O(1)

All operations on a stack are performed in constant time (O(1)), making stacks very efficient for scenarios
where quick access to the most recently added element is required, such as in function call management
or undo operations in applications.

b) Queue Operations

Table 1-3: Queue Operations

Operation Description Time Complexity

19
 Enqueue Adds an element to the end of O(1)
the queue.
Dequeue Removes and returns the O(1)
element from the front of the
queue.
Front Returns the element at the front O(1)
of the queue without removing
it.
IsEmpty Checks if the queue is empty. O(1)

Similar to stacks, all operations on a queue are performed in constant time (O(1)). This efficiency is
crucial for applications like task scheduling and print job management, where maintaining the order of
processing is essential.

c) Linked List Operations

Table 1-4: Linked List Operations

Operation Description Time Complexity
Insert Adds a new node to the list (at O(1) (at head), O(n) (at tail or
the head, tail, or specific middle)
position).
Delete Removes a node from the list. O(n) (requires searching for the
node)
Search Finds a node with a specific O(n)
value.
Traverse Visits each node in the list. O(n)

The time complexity for inserting a node at the head of a linked list is O(1), making it efficient for adding
elements. However, searching for a node or deleting a node requires O(n) time, as it may involve
traversing the entire list. This makes linked lists less efficient for operations that require frequent
searching or deletion compared to stacks and queues.

1.2 Determine the operations of a memory stack and how it is used to

implement function calls in a computer.(P2)

1.2.1 Overview of the memory stack

20
 Figure 1-11: Memory stack

Definition: “The memory stack is a data structure that operates on a Last In, First Out (LIFO) principle,
used primarily for managing function calls, local variables, and return addresses in programming. It
allows for the dynamic allocation and deallocation of memory as functions are called and return,
facilitating efficient execution and control flow in programs.”

The memory stack is a crucial data structure that manages function calls and local data using a Last In,
First Out (LIFO) approach.

Key Components:

 Function Parameters: Values passed to a function.

 Local Variables: Data stored within a function’s scope.

 Return Address: The program location to return to after function execution.

1.2.2 How the Memory Stack Works

The memory stack functions as a dynamic storage area that grows and shrinks as functions are called and
return. Here’s a step-by-step explanation of how the memory stack operates:

a) Function Call: When a function is invoked, a new stack frame is created on the top of the stack. This
stack frame contains:

 Return Address: The address in the program where control should return after the function
execution is complete.

 Parameters: The arguments passed to the function.

21
  Local Variables: Any variables declared within the function.

b) Stack Frame Creation: The stack frame is pushed onto the stack, which involves allocating space for
the return address, parameters, and local variables. The stack pointer (a special register that tracks the
top of the stack) is updated to reflect the new top of the stack.

c) Function Execution: The function executes using the parameters and local variables stored in its stack
frame. During this time, the function can also call other functions, which will create additional stack
frames on top of the current one.

d) Function Return: Once the function completes its execution, it prepares to return. The return value (if
any) is typically placed in a designated register. The stack frame is then popped off the stack, which
involves:

 Retrieving the return address from the stack frame.

 Updating the stack pointer to remove the stack frame from the stack.

 Transferring control back to the return address, allowing the program to continue execution from
where the function was called.

e) Memory Management: The stack automatically manages memory allocation and deallocation. When a
function returns, its stack frame is removed, freeing up the memory for future function calls. This
automatic management helps prevent memory leaks, as the memory used by local variables is reclaimed
as soon as the function exits.

1.2.3 Stack and Recursion

22
 Figure 1-12: Recursion

Recursion is a technique where a function calls itself to solve a problem. The memory stack manages
these calls by storing stack frames for each function invocation.

Stack Interaction in Recursion:

a) Multiple Stack Frames: Each recursive call pushes a new frame onto the stack, preserving its own
parameters and local variables.

b) Base Case & Recursive Case: The base case stops recursion, while the recursive case continues calling
itself.

c) Stack Unwinding: When recursion reaches the base case, stack frames are popped one by one,
returning control to previous calls.

d) Memory Usage: Deep recursion increases stack space usage, potentially causing a stack overflow if the
limit is exceeded.

e) Example: Consider a simple recursive function that calculates the factorial of a number ( n ):

Figure 1-13: Example of recursion

 Base Case: The function checks if ( n ) is 0. If true, it returns 1.

23
  Recursive Case: If ( n ) is greater than 0, it calls itself with ( n - 1 ) and multiplies the result by ( n ).

 Output: For an input of 5, the output will be:

Figure 1-14: Output of recursion example

1.2.4 Advantages and Disadvantages of the Memory Stack

 Advantages

 Automatic Memory Management: The stack automatically allocates and deallocates memory
for function calls and local variables. This reduces the risk of memory leaks, as memory is
reclaimed as soon as a function exits.

 Fast Access: Accessing data on the stack is generally faster than accessing data on the heap.
This is because the stack operates in a LIFO manner, allowing for quick push and pop
operations.

 Function Call Management: The stack efficiently manages function calls, including
parameters, local variables, and return addresses. This organization simplifies the execution
flow of programs.

 Recursion Support: The stack is well-suited for handling recursive function calls, as each call
creates a new stack frame that maintains its own context, allowing for clear and structured
recursion.

 Predictable Lifetime: The lifetime of stack-allocated variables is predictable, as they are

automatically destroyed when the function exits. This makes it easier to manage variable
scope and lifetime.

 Disadvantages

 Limited Size: The stack has a fixed size, which can lead to stack overflow if too many function
calls are made (e.g., deep recursion). This can cause the program to crash.

 No Dynamic Memory Allocation: The stack is not suitable for dynamic memory allocation of
large data structures, as it is limited in size and cannot grow like the heap.

 Scope Limitations: Variables stored on the stack are only accessible within the function that
created them. This can limit their usability if they need to be accessed outside of that
function.

24
  Debugging Complexity: In cases of deep recursion or stack overflow, debugging can become
complex, as it may be difficult to trace back through multiple stack frames to identify the
source of the problem.

 Performance Overhead: While stack access is generally fast, excessive function calls
(especially in recursive functions) can lead to performance overhead due to the repeated
creation and destruction of stack frames.

Table 1-5: Advantages and Disadvantages of the Memory Stack

Advantages Disadvantages
Automatic Memory Management Limited Size
The stack automatically allocates and deallocates The stack has a fixed size, which can lead to stack
memory for function calls and local variables, overflow if too many function calls are made.
reducing the risk of memory leaks.
Fast Access No Dynamic Memory Allocation
Accessing data on the stack is generally faster The stack is not suitable for dynamic memory
than accessing data on the heap due to quick allocation of large data structures, as it cannot
push and pop operations. grow like the heap.
Function Call Management Scope Limitations
The stack efficiently manages function calls, Variables stored on the stack are only accessible
including parameters, local variables, and return within the function that created them, limiting
addresses, simplifying execution flow. their usability.
Recursion Support Debugging Complexity
The stack is well-suited for handling recursive Deep recursion or stack overflow can complicate
function calls, maintaining context through debugging, making it difficult to trace back
separate stack frames. through multiple stack frames.
Predictable Lifetime Performance Overhead
The lifetime of stack-allocated variables is Excessive function calls can lead to performance
predictable, as they are automatically destroyed overhead due to the repeated creation and
when the function exits. destruction of stack frames.

1.2.5 Visual Illustration of the Memory Stack

To illustrate how the memory stack works, especially in the context of function calls and recursion,
consider the following example of a recursive function that calculates the factorial of a number ( n ).

Example: Factorial of 3
Let's visualize the stack frames created during the execution of factorial(3).

a) Function Call Sequence:

25
  factorial(3)

 factorial(2)

 factorial(1)

 factorial(0)

Stack Visualization

Figure 1-15: Stack Visualization

Explanation of the Stack Frames

 Stack Frame for factorial(3):

o Contains the return address and the parameter ( n = 3 ).

 Stack Frame for factorial(2):

o Contains the return address and the parameter ( n = 2 ).

 Stack Frame for factorial(1):

o Contains the return address and the parameter ( n = 1 ).

 Stack Frame for factorial(0):

o Contains the return address and the parameter ( n = 0 ). This is where the base case is
reached, returning 1.

Unwinding the Stack

Once the base case is reached, the stack begins to unwind:

26
  factorial(0) returns 1 to factorial(1).

 factorial(1) returns ( 1 * times 1 = 1 ) to factorial(2).

 factorial(2) returns ( 2 * times 1 = 2 ) to factorial(3).

 factorial(3) returns ( 3 * times 2 = 6 ).

Final Stack State

 After all function calls have returned, the stack is empty, and the final result of factorial(3) is 6.

This visual representation illustrates how the memory stack manages function calls and local variables
during recursion. Each function call creates a new stack frame, and the stack unwinds as each function
completes, returning control to the previous call. This structure is essential for maintaining the context of
each function call in recursive programming.

1.3 Illustrate, with an example, a concrete data structure for a First in First
out (FIFO) queue. (M1)

1.3.1 Overview of the FIFO Queue

Figure 1-16: FIFO Queue

A FIFO queue is a linear data structure where the first element added is the first to be removed, similar
to a real-world queue.

Key Characteristics:

 Order Preservation: Elements are processed in the order they arrive.

27
  Dynamic Size: Can grow or shrink as needed.

 Limited Access: Elements are added at the rear and removed from the front.

1.3.2 Basic Operations of a Queue

A FIFO queue supports several fundamental operations that allow for the management of its elements.
The primary operations include:

a) Enqueue: This operation adds an element to the back (rear) of the queue. If the queue is full (in the
case of a fixed-size implementation), this operation may fail or require resizing.

 Example: If we have a queue containing the elements [A, B], and we enqueue C, the queue will
then contain [A, B, C].

b) Dequeue: This operation removes and returns the element from the front of the queue. If the queue is
empty, this operation may fail or return a special value (like null or None).

 Example: If we have a queue containing [A, B, C], and we dequeue, the element A will be
removed, and the queue will then contain [B, C].

c) Peek (or Front): This operation returns the element at the front of the queue without removing it. This
allows users to see which element will be dequeued next.

 Example: If the queue contains [B, C], the peek operation will return B, but the queue will remain
unchanged.

d) IsEmpty: This operation checks whether the queue is empty. It returns a boolean value indicating the
status of the queue.

 Example: If the queue is empty, the operation will return true; otherwise, it will return false.

e) Size: This operation returns the number of elements currently in the queue.

 Example: If the queue contains [B, C], the size operation will return 2.

1.3.3 Implementing a Queue Using an Array

Implementing a Queue Using an Array in Java

A FIFO (First-In, First-Out) queue can be implemented using a fixed-size array. In this implementation, we
will maintain two pointers (or indices): one for the front of the queue and one for the rear. The array will
hold the elements of the queue, and we will manage the addition and removal of elements using these
pointers.

28
Key Components of the Array-Based Queue Implementation:

 Array: A fixed-size array to store the elements of the queue.

 Front Pointer: An index that points to the front of the queue (the element to be dequeued).

 Rear Pointer: An index that points to the next available position at the back of the queue (where
the next element will be enqueued).

 Size: An integer to keep track of the current number of elements in the queue.

Basic Operations:

a) Enqueue Operation:

 Check if the queue is full (i.e., if the size equals the capacity of the array).

 If not full, add the new element at the position indicated by the rear pointer and increment the
rear pointer (wrapping around if necessary).

 Increment the size of the queue.

b) Dequeue Operation:

 Check if the queue is empty (i.e., if the size is zero).

 If not empty, retrieve the element at the front pointer, increment the front pointer (wrapping
around if necessary), and decrement the size.

c) Peek Operation:

 Return the element at the front pointer without removing it. This allows users to see which
element will be dequeued next.

d) IsEmpty Operation:

 Return true if the size is zero; otherwise, return false.

e) Size Operation:

 Return the number of elements currently in the queue.

Example Implementation in Java:

29
Figure 1-17: Example Implementation Queue using array (part 1)

30
 Figure 1-18: Example Implementation Queue using array (part 2)

Output:

Figure 1-19: Output of Queue implementation

31
Explanation of the Java Implementation:

a) Class Definition: The ArrayQueue class encapsulates the properties and methods of the queue.

b) Attributes:

 capacity: The maximum number of elements the queue can hold.

 queue: An array to store the elements of the queue.

 front: An index pointing to the front of the queue.

 rear: An index pointing to the next available position at the back of the queue.

 size: The current number of elements in the queue.

c) Constructor: Initializes the queue with a specified capacity and sets the front, rear, and size to zero.

d) Enqueue Method:

 Purpose: The enqueue method adds a new element to the back (rear) of the queue.

 Implementation Steps:

 Check for Full Queue: The method first checks if the queue is full by comparing the current
size with the capacity. If the queue is full, it throws an IllegalStateException.

 Add Element: If there is space, the new element is added to the position indicated by the rear
pointer in the array.

 Update Rear Pointer: The rear pointer is then incremented. The modulo operation (%
capacity) ensures that if the rear pointer reaches the end of the array, it wraps around to the
beginning of the array.

 Increment Size: Finally, the size of the queue is incremented by one.

e) Dequeue Method

 Purpose: The dequeue method removes and returns the element from the front of the queue.

 Implementation Steps:

 Check for Empty Queue: The method checks if the queue is empty by verifying if the size is
zero. If it is empty, it throws an IllegalStateException.

 Retrieve Element: The element at the position indicated by the front pointer is retrieved.

32
  Clear Slot (Optional): The slot in the array can be cleared (set to null or 0) to indicate that it is
no longer occupied (this is optional).

 Update Front Pointer: The front pointer is incremented, and the modulo operation ensures it
wraps around if necessary.

 Decrement Size: The size of the queue is decremented by one, and the retrieved element is
returned.

f) Peek Method

 Purpose: The peek method allows users to view the element at the front of the queue without
removing it.

 Implementation Steps:

 Check for Empty Queue: The method checks if the queue is empty. If it is, it throws an
IllegalStateException.

 Return Front Element: If the queue is not empty, it returns the element at the front pointer.

g) IsEmpty Method

 Purpose: The isEmpty method checks whether the queue is empty.

 Implementation Steps:

 Return Boolean: It returns true if the size is zero; otherwise, it returns false.

h) GetSize Method

 Purpose: The getSize method returns the current number of elements in the queue.

 Implementation Steps:

 Return Size: It simply returns the value of the size attribute.

1.3.4 Implementing a Queue Using a Linked List

A FIFO queue can also be implemented using a linked list, which allows for dynamic sizing and efficient
memory usage. In this implementation, each element of the queue is represented as a node in the linked
list. The queue will maintain pointers to both the front and rear nodes, allowing for efficient enqueue
and dequeue operations.

Key Components of the Linked List-Based Queue Implementation:

33
  Node Class: A nested class that represents each element in the queue. Each node contains the
data and a reference to the next node.

 Front Pointer: A reference to the first node in the linked list (the front of the queue).

 Rear Pointer: A reference to the last node in the linked list (the rear of the queue).

 Size: An integer to keep track of the current number of elements in the queue.

Basic Operations:

a) Enqueue Operation:

 Create a new node with the given data.

 If the queue is empty, set both the front and rear pointers to the new node.

 If the queue is not empty, link the new node to the current rear node and update the rear pointer
to the new node.

 Increment the size of the queue.

b) Dequeue Operation:

 Check if the queue is empty.

 If not empty, retrieve the data from the front node, update the front pointer to the next node,
and decrement the size.

 If the queue becomes empty after the dequeue operation, set the rear pointer to null.

c) Peek Operation:

 Return the data from the front node without removing it. This allows users to see which element
will be dequeued next.

d) IsEmpty Operation:

 Return true if the size is zero; otherwise, return false.

e) Size Operation:

 Return the number of elements currently in the queue.

Example Implementation in Java:

34
Figure 1-20: Example Implementation Queue using LinkedList (part 1)

35
 Figure 1-21: Example Implementation Queue using LinkedList (part 2)

Output:

36
 Figure 1-22: Output of implementation Queue using LinkedList

Explanation of the Java Implementation:

a) Node Class: A static nested class that represents each element in the queue. It contains an integer
data and a reference to the next node.

b) Attributes:

 front: A reference to the first node in the linked list (the front of the queue).

 rear: A reference to the last node in the linked list (the rear of the queue).

 size: The current number of elements in the queue.

c) Constructor: Initializes the queue with front and rear set to null and size to zero.

d) Enqueue Method: Creates a new node and links it to the current rear. If the queue is empty, it sets
both front and rear to the new node.

e) Dequeue Method: Retrieves the data from the front node, updates the front pointer, and checks if the
queue becomes empty to set the rear pointer to null.

f) Peek Method: Returns the data from the front node without removing it.

g) IsEmpty Method: Checks if the size is zero to determine if the queue is empty.

h) GetSize Method: Returns the current size of the queue.

1.3.5 Comparison of the Two Implementations

When comparing the two implementations of a FIFO queue—using an array and using a linked list—
there are several factors to consider, including memory usage, performance, and ease of
implementation.

1. Memory Usage

Array-Based Queue:

 Fixed Size: The size of the queue is determined at the time of creation. If the maximum capacity is
reached, no more elements can be added unless the array is resized, which can be inefficient.

 Wasted Space: If the queue is not full, there may be unused space in the array, leading to
inefficient memory usage.

Linked List-Based Queue:

37
  Dynamic Size: The queue can grow and shrink dynamically as elements are added or removed.
There is no need to define a maximum size upfront.

 No Wasted Space: Memory is allocated for each element as needed, so there is no wasted space.

2. Performance

Array-Based Queue:

 Enqueue Operation: O(1) time complexity for adding an element, assuming there is space
available. However, if resizing is needed, it can take O(n) time.

 Dequeue Operation: O(1) time complexity for removing an element, but if the queue is
implemented without wrapping (i.e., without circular behavior), it may lead to inefficient use of
space.

Linked List-Based Queue:

 Enqueue Operation: O(1) time complexity for adding an element, as it simply involves linking a
new node to the rear.

 Dequeue Operation: O(1) time complexity for removing an element, as it involves updating the
front pointer.

3. Ease of Implementation

Array-Based Queue:

 Simplicity: The implementation is straightforward and easy to understand, especially for

beginners.

 Index Management: Care must be taken to manage the front and rear indices correctly, especially
when wrapping around.

Linked List-Based Queue:

 Complexity: The implementation is slightly more complex due to the need to manage node
pointers.

 Memory Management: Requires careful handling of node creation and deletion, which can
introduce potential memory leaks if not managed properly.

4. Use Cases

Array-Based Queue:

38
  Suitable for scenarios where the maximum size of the queue is known in advance and does not
change frequently, such as in fixed-size task scheduling or buffering.

Linked List-Based Queue:

 Ideal for scenarios where the number of elements can vary significantly, such as in dynamic task
scheduling, event handling, or when implementing a queue for asynchronous processing.

Both implementations of a FIFO queue have their advantages and disadvantages. The choice between an
array-based queue and a linked list-based queue depends on the specific requirements of the
application, including memory constraints, expected queue size, and performance considerations.

 If I need a simple, fixed-size queue and memory usage is not a concern, an array-based
implementation may be sufficient.

 If I require a dynamic queue that can grow and shrink as needed, a linked list implementation is
more appropriate.

Table 1-6: Comparison of the Two Implementations

Feature Array-Based Queue Linked List-Based Queue
Memory Usage - Fixed size, determined at - Dynamic size, grows and
creation. shrinks as needed.
- May have wasted space if not - No wasted space; memory
full. allocated per element.
Performance - Enqueue: O(1) (O(n) if resizing - Enqueue: O(1) (always
needed). efficient).
- Dequeue: O(1) (may lead to - Dequeue: O(1) (always
inefficiency if not circular). efficient).
Ease of Implementation - Simple and straightforward. - Slightly more complex due to
-Requires careful index
pointer management.
management. - Requires careful node
management.
Use Cases - Suitable for fixed-size queues. - Ideal for dynamic queues with
- Good for scenarios with known variable sizes.
maximum size. - Good for scenarios with
unpredictable sizes.
Memory Management - No need for manual memory - Requires careful handling of
management. node creation and deletion.
Access to Elements - Random access is possible - Sequential access only (O(n)
(O(1)). for searching).

1.4 Compare the performance of two sorting algorithms.(M2)

39
1.4.1 Overview of Sorting Algorithms

Figure 1-23: Sorting algorithms

Sorting algorithms are essential in computer science for organizing data efficiently. They can be
categorized into:

1. Comparison-Based Sorting Algorithms

These algorithms sort data by comparing elements.

 Bubble Sort: Repeatedly swaps adjacent elements if they are in the wrong order. (O(n²) time
complexity)

 Quick Sort: Uses a pivot to divide and conquer. (O(n log n) average case)

 Merge Sort: Recursively divides the array and merges sorted halves. (O(n log n))

 Selection Sort: Repeatedly selects the smallest/largest element and moves it to the sorted
part. (O(n²))

 Insertion Sort: Inserts elements into their correct position in a growing sorted list. (O(n²), but
O(n) for nearly sorted data)

2. Non-Comparison-Based Sorting Algorithms

These avoid element-to-element comparisons, achieving better performance in some cases.

 Counting Sort: Counts occurrences of each value and reconstructs the sorted array. (O(n + k),
where k is the range of values)

 Radix Sort: Sorts numbers digit by digit. (O(nk), where k is the number of digits)

40
Performance Considerations:

 Time Complexity: Measures how execution time grows with input size.

 Space Complexity: Evaluates memory usage.

 Stability: Determines if equal elements retain their original relative order.

 Adaptability: Some algorithms work faster when the data is already partially sorted.

1.4.2 Description of the Two Algorithms

a) Insertion Sort

Figure 1-24: Insertion Sort

Overview: Insertion Sort is a simple and intuitive sorting algorithm that builds a sorted array (or list) one
element at a time. It is similar to the way you might sort playing cards in your hands. The algorithm
divides the input list into a sorted and an unsorted region, and it iteratively takes one element from the
unsorted region and inserts it into the correct position in the sorted region.

Algorithm Steps:

1. Start with the second element (the first element is considered sorted).

2. Compare the current element (key) with the elements in the sorted region (to its left).

3. Shift all larger elements in the sorted region one position to the right to make space for the key.

4. Insert the key into its correct position in the sorted region.

5. Repeat the process for all elements in the unsorted region until the entire list is sorted.

41
Example: Consider the array [5, 2, 9, 1, 5, 6]. The steps of Insertion Sort would be:

 Start with the first element (5) as sorted.

 Insert 2: [2, 5, 9, 1, 5, 6]

 Insert 9: [2, 5, 9, 1, 5, 6] (no change)

 Insert 1: [1, 2, 5, 9, 5, 6]

 Insert 5: [1, 2, 5, 5, 9, 6]

 Insert 6: [1, 2, 5, 5, 6, 9]

Time Complexity:

 Best Case: (O(n)) (when the array is already sorted)

 Average Case: (O(n^2))

 Worst Case: (O(n^2))

 Space Complexity: (O(1)) (in-place sorting)

Characteristics:

 Stability: Insertion Sort is stable, meaning that equal elements maintain their relative order.

 Adaptability: It performs well on partially sorted data, making it efficient for small datasets or
when the input is nearly sorted.

b) Selection Sort

Figure 1-25: Selection Sort

42
Overview: Selection Sort is another simple sorting algorithm that divides the input list into a sorted and
an unsorted region. It repeatedly selects the smallest (or largest, depending on the desired order)
element from the unsorted region and moves it to the end of the sorted region.

Algorithm Steps:

1. Start with the entire list as unsorted.

2. Find the minimum element in the unsorted region.

3. Swap it with the first element of the unsorted region.

4. Move the boundary between the sorted and unsorted regions one element to the right.

5. Repeat the process until the entire list is sorted.

Example: Consider the array [5, 2, 9, 1, 5, 6]. The steps of Selection Sort would be:

 Find the minimum (1) and swap it with the first element: [1, 2, 9, 5, 5, 6]

 Find the next minimum (2) and swap it with the second element: [1, 2, 9, 5, 5, 6] (no change)

 Find the next minimum (5) and swap it with the third element: [1, 2, 5, 9, 5, 6]

 Find the next minimum (5) and swap it with the fourth element: [1, 2, 5, 5, 9, 6]

 Find the next minimum (6) and swap it with the fifth element: [1, 2, 5, 5, 6, 9]

 The array is now sorted.

Time Complexity:

 Best Case: (O(n^2))

 Average Case: (O(n^2))

 Worst Case: (O(n^2))

Space Complexity: (O(1)) (in-place sorting)

Characteristics:

 Stability: Selection Sort is not stable, as it may change the relative order of equal elements during
the selection process.

 Adaptability: It does not adapt to the initial order of elements, and its performance remains
consistent regardless of the input.

43
1.4.3 Comparison of the Two Algorithms: Insertion Sort and Selection Sort
In this section, I will compare Insertion Sort and Selection Sort based on several criteria, including time
complexity, space complexity, operational characteristics, and performance in different scenarios.

1. Time Complexity

 Insertion Sort:

 Best Case: (O(n)) - This occurs when the input array is already sorted, as each element only
needs to be compared once.

 Average Case: (O(n^2)) - On average, each element will need to be compared to half of the
already sorted elements.

 Worst Case: (O(n^2)) - This occurs when the input array is sorted in reverse order, requiring
the maximum number of comparisons and shifts.

 Selection Sort:

 Best Case: (O(n^2)) - Regardless of the initial order of elements, Selection Sort always
performs the same number of comparisons.

 Average Case: (O(n^2)) - The number of comparisons remains constant, as it always scans the
entire unsorted portion of the array.

 Worst Case: (O(n^2)) - Similar to the average case, the number of comparisons does not
change based on the input.

2. Space Complexity

 Insertion Sort:

 Space Complexity: (O(1)) - Insertion Sort is an in-place sorting algorithm, meaning it requires a
constant amount of additional memory space regardless of the input size.

 Selection Sort:

 Space Complexity: (O(1)) - Like Insertion Sort, Selection Sort is also an in-place algorithm,
requiring only a constant amount of additional memory.

3. Operational Characteristics

 Insertion Sort:

44
  Stability: Insertion Sort is a stable sorting algorithm, meaning that it maintains the relative
order of equal elements.

 Adaptability: It performs well on partially sorted data, making it efficient for small datasets or
when the input is nearly sorted.

 Best Use Case: Ideal for small datasets or when the data is mostly sorted.

 Selection Sort:

 Stability: Selection Sort is not stable, as it may change the relative order of equal elements
during the selection process.

 Adaptability: It does not adapt to the initial order of elements, and its performance remains
consistent regardless of the input.

 Best Use Case: Suitable for small datasets where memory usage is a concern, but generally
less efficient than Insertion Sort.

4. Performance in Different Scenarios

 Insertion Sort:

 Performs exceptionally well on small or nearly sorted datasets, often outperforming more
complex algorithms like Quick Sort or Merge Sort in these cases.

 The best-case scenario (already sorted) allows it to run in linear time, making it very efficient
for small lists.

 Selection Sort:

 While it has a consistent performance, it is generally slower than Insertion Sort for most
practical scenarios due to its (O(n^2)) time complexity.

 It is not suitable for large datasets, as it does not take advantage of any existing order in the
data.

Table 1-7: Comparison of the Two Algorithms

Feature Insertion Sort Selection Sort
Best Case Time O(n) O(n²)
Average Case Time O(n²) O(n²)
Worst Case Time O(n²) O(n²)
Space Complexity O(1) O(1)
Stability Stable Not Stable

45
 Adaptability Adaptive to sorted data Not Adaptive
Best Use Case Small or nearly sorted datasets Small datasets

1.4.4 Practical Testing

In this section, I will evaluate the performance of Insertion Sort and Selection Sort using Java. I will
measure the execution time of both algorithms on different types of datasets:

 Randomly Ordered Data

 Sorted Data

 Reverse Ordered Data

 Partially Sorted Data

Java Implementation

Here’s the Java code that implements both sorting algorithms and measures their execution time:

46
Figure 1-26: Code to measure time of 2 algorithm (part 1)

47
 Figure 1-27: Code to measure time of 2 algorithm ( part 2)

Output:

48
 Figure 1-28: Measure time of 2 algorithm output

Results Analysis:

a) Performance Comparison:

 Insertion Sort is adaptive, making it efficient for sorted or nearly sorted data.

 Selection Sort maintains a consistent performance regardless of input order but is slower than
Insertion Sort for most cases.

b) Execution Time:

 Insertion Sort runs faster on sorted data and degrades on reverse-ordered data due to its
stepwise insertion mechanism.

 Selection Sort maintains a stable but slower execution time, as it always makes a fixed number of
comparisons and swaps.

c) Scalability:

 Insertion Sort scales better, especially for smaller or partially sorted datasets.

 Selection Sort remains inefficient for larger datasets due to its O(n²) complexity.

d) Conclusion:

 Insertion Sort is preferable for small or nearly sorted datasets.

 Selection Sort is rarely the best choice due to its consistent but suboptimal performance.

49
  Understanding these differences helps in choosing the right sorting algorithm based on dataset
characteristics.

CHAPTER 2: Specify abstract data types and algorithms in a formal notation

(LO2)

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

2.1.1 Overview of ADT and Imperative Definition

 ADT: Defines a data type by its operations, not implementation. Example:

 Push(x): Add x to the top.

 Pop(): Remove and return the top element.

 Peek(): View the top element without removing it.

 IsEmpty(): Check if empty.

 Size(): Get the number of elements.

 Imperative Definition: Specifies step-by-step execution, modifying the program’s state (e.g., using
arrays or linked lists).

Key Point: ADT focuses on what operations do, imperative definition focuses on how they are executed.

2.1.2 Example of Defining an ADT Using the Imperative Approach

To define a stack as an Abstract Data Type (ADT) using an imperative approach, I will outline the
operations that can be performed on the stack and describe how these operations manipulate the
internal state of the stack.

Stack Operations

a) Push(element):

 Description: Adds an element to the top of the stack.

 State Change: Increases the size of the stack and updates the top pointer to the new element.

b) Pop():

50
  Description: Removes and returns the element from the top of the stack.

 State Change: Decreases the size of the stack and updates the top pointer to the next element. If
the stack is empty, it may raise an error or return a special value.

c) Peek():

 Description: Returns the element at the top of the stack without removing it.

 State Change: No change to the stack's size or top pointer.

d) IsEmpty():

 Description: Checks if the stack is empty.

 State Change: No change to the stack's state.

e) Size():

 Description: Returns the number of elements in the stack.

 State Change: No change to the stack's state.

Using an imperative approach, we can define the stack ADT as follows:

1. Initialize an empty stack.

2. To push an element:

a. Place the element on top of the stack.

3. To pop an element:

a. If the stack is not empty, remove and return the top element.

b. Otherwise, return an error (underflow condition).

4. To peek at the top element:

a. If the stack is not empty, return the top element.

b. Otherwise, return an error.

5. To check if the stack is empty:

a. Return true if there are no elements; otherwise, return false.

6. To get the size of the stack:

51
 a. Return the number of elements in the stack.

2.1.3 Implementation of the Example Using Java

Now, I will implement the stack ADT using Java. This implementation will include the operations defined
earlier: Push, Pop, Peek, IsEmpty, and Size.

Java Implementation:

Figure 2-1: Java code to implement the stack ADT

52
Output:

Figure 2-2: Output of implement the stack ADT

Explanation of the Implementation

a) Attributes:

 stackArray: an array to hold the stack elements.

 top: an integer to track the index of the top element in the stack.

 capacity: an integer to define the maximum size of the stack.

b) Constructor:

 Initializes the stack with a given size, sets the capacity, allocates memory for stackArray, and sets
top to -1 (indicating an empty stack).

c) Methods:

 push(int x): Adds an element to the top of the stack. Checks for stack overflow before adding.

 pop(): Removes and returns the top element from the stack. Checks for stack underflow before
removing.

 peek(): Returns the top element without removing it. Checks if the stack is empty.

 isEmpty(): Checks if the stack is empty.

 size(): Returns the current size of the stack.

d) Main Method:

53
  Demonstrates the use of the stack by pushing elements, checking the top element, and popping
elements.

2.1.4 Advantages of Imperative Definition

 Clarity & Explicitness – Clearly defines how operations manipulate the stack’s state.

 State Control – Provides fine-grained control, aiding debugging and optimization.

 Performance Optimization – Enables choosing efficient data structures (array, linked list).

 Hardware Efficiency – Closer to hardware, allowing better memory management.

 Ease of Implementation – Straightforward for procedural programming.

 Flexibility – Allows easy modifications and extensions.

 Error Handling – Enables explicit handling of stack overflow/underflow errors.

2.1.5 Practical Application of the Stack ADT

 Function Call Management – Manages function calls and return addresses.

 Expression Evaluation – Used in parsing and evaluating mathematical expressions.

 Backtracking Algorithms – Tracks paths in algorithms like maze solving and Sudoku.

 Undo Mechanisms – Supports undo operations in text editors and design software.

 Depth-First Search (DFS) – Implements DFS in graph traversal.

 Memory Management – Handles local variables and function call frames.

 Syntax Parsing – Used in compilers to check syntax and balance parentheses.

 Web Browsers – Manages browsing history for back/forward navigation.

2.2 Examine the advantages of encapsulation and information hiding when

using an ADT.(M3)

2.2.1 Definition of Concepts

Definition of encapsulation:

54
 Figure 2-3: Encapsulation

“Encapsulation is a fundamental principle of object-oriented programming that involves bundling the

data (attributes) and the methods (functions) that operate on that data into a single unit, known as a
class. This means that the internal state of an object is hidden from the outside world, and access to that
state is only possible through well-defined interfaces (methods). Encapsulation helps to protect the
integrity of the data by preventing external entities from making unauthorized changes.”

Definition of information hiding:

Figure 2-4: Information hiding

“Information Hiding is closely related to encapsulation and refers to the practice of restricting access to
certain details of an object or module. By hiding the internal workings and exposing only the necessary
parts of an object, information hiding reduces complexity and increases the modularity of the code. This
means that changes to the internal implementation of a class can be made without affecting other parts
of the program that rely on the class, as long as the public interface remains unchanged.”

2.2.2 Benefits of Encapsulation and Information Hiding When Using ADTs

55
  Improved Data Integrity – Prevents unintended modifications by restricting direct access to data.

 Modularity – Allows independent development, testing, and maintenance of components.

 Ease of Maintenance – Internal changes don’t affect external usage as long as the interface
remains stable.

 Reduced Complexity – Simplifies interactions by hiding implementation details.

 Enhanced Security – Protects sensitive data from unauthorized access.

 Facilitated Code Reusability – Enables reuse of encapsulated classes without understanding

internal logic.

2.2.3 Illustrative Example

To illustrate the concepts of encapsulation and information hiding in Java, we can create a class
representing a BankAccount. This class will encapsulate the account balance and provide methods to
interact with it while hiding the internal representation of the balance.

56
57
 Figure 2-5: Illustrative Example

Output:

Fifure 2-6: Output of Illustrative Example

Explanation of the Example

a)Encapsulation:

 The balance attribute is declared as private, meaning it cannot be accessed directly from outside
the BankAccount class. This encapsulation protects the balance from unauthorized access and
modification.

b) Information Hiding:

 The internal representation of the balance is hidden from users of the class. Users can only
interact with the balance through the public methods deposit, withdraw, and getBalance. This
means that users do not need to know how the balance is stored or managed internally.

c) Data Integrity:

 The methods deposit and withdraw include checks to ensure that only valid operations can be
performed on the balance. For example, a deposit must be positive, and a withdrawal must not
exceed the current balance. This helps maintain the integrity of the data.

Summary of the Example

 Encapsulation: The BankAccount class encapsulates the balance and related operations,
preventing direct access to the balance from outside the class.

 Information Hiding: The internal representation of the balance is hidden from users, who interact
with the account only through the provided methods.

58
This Java example effectively demonstrates how encapsulation and information hiding can be applied in
the design of an Abstract Data Type (ADT) to create a robust and user-friendly interface.

2.2.4 Comparison Before and After Applying Encapsulation and Information

Hiding
To illustrate the impact of encapsulation and information hiding, let's compare a scenario where these
principles are not applied with one where they are effectively utilized, using the BankAccount example.

Before Applying Encapsulation and Information Hiding

In a poorly designed version of the BankAccount class, the balance might be a public attribute, allowing
direct access and modification from outside the class:

Figure 2-7: Before Applying Encapsulation and Information Hiding

Issues with This Design:

1. Direct Access: The ‘balance’ attribute is public, allowing any external code to modify it directly. For
example:

59
 Figure 2-8: Direct Access

2. Lack of Control: There are no checks or validations when modifying the balance. This can lead to
invalid states (e.g., negative balances) and data corruption.

3. Increased Complexity: Users of the class must understand the implications of directly manipulating the
balance, increasing the cognitive load and potential for errors.

4. Difficult Maintenance: If the internal representation of the balance needs to change (e.g., changing
from a ‘double’ to a ‘BigDecimal’ for precision), all code that accesses the balance directly would need to
be updated.

After Applying Encapsulation and Information Hiding

With the encapsulated version of the ‘BankAccount’ class, as shown previously, the design addresses
these issues:

60
 Figure 2-9: After Applying Encapsulation and Information Hiding

Benefits of This Design:

a) Controlled Access: The balance attribute is private, preventing direct access. Users must use the
provided methods to interact with the balance, ensuring that all operations are valid.

b) Data Integrity: The methods include validation checks, ensuring that the balance cannot be set to an
invalid state (e.g., negative balance).

c) Reduced Complexity: Users of the class do not need to understand the internal workings of the
balance. They can simply call deposit, withdraw, and getBalance without worrying about the underlying
implementation.

61
d) Easier Maintenance: If the internal representation of the balance changes, only the BankAccount class
needs to be updated. External code that uses the class remains unaffected as long as the public interface
stays the same.

The comparison highlights the significant advantages of applying encapsulation and information hiding in
the design of Abstract Data Types (ADTs). By protecting the internal state of an object and providing a
controlled interface for interaction, these principles enhance data integrity, reduce complexity, and
facilitate easier maintenance, ultimately leading to more robust and reliable software systems.

CHAPTER 3: Implement complex data structures and algorithms (L03)

3.1 Implement a complex ADT and algorithm in an executable programming

language to solve a well-defined problem. (P4)

3.1.1 Selection of a Specific Problem

For this section, the problem I aim to solve is managing student information and ranking them based on
their scores.

Problem Statement

Soft Development ABK, a software workshop for small and medium enterprises, has requested a Student
Management System that allows users to:

1. Enter and manage student details (ID, Name, and Marks).

2. Rank students based on their marks using predefined ranking criteria:

 [0 – 5.0) → Fail

 [5.0 – 6.5) → Medium

 [6.5 – 7.5) → Good

 [7.5 – 9.0) → Very Good

 [9.0 – 10.0] → Excellent

3. Perform operations like Add, Edit, Delete, Sort, and Search for students.

4. Evaluate and compare different algorithms for managing student data.

Since ranking, searching, and sorting students efficiently is essential, we need a complex ADT (Abstract
Data Type) and an efficient algorithm to handle student records properly.

62
3.1.2 ADT and Algorithm Used
To effectively manage student records and their rankings, I have chosen ArrayList as the primary Abstract
Data Type (ADT). The ArrayList in Java provides dynamic storage for student objects, allowing me to add,
edit, delete, search, and sort students efficiently.

1. Abstract Data Type (ADT) – Student List

Figure 3-1: student list is implemented using an ArrayList<Student>

The student list is implemented using an ArrayList<Student>, where each student is an object of the
Student class. This ADT allows for:

 Adding a student to the list dynamically.

 Editing student details by updating the stored object.

 Deleting a student by removing their object from the list.

 Sorting students based on their average marks.

 Searching for a student using their ID.

Algorithm Selection

For sorting and searching, I need efficient algorithms since the number of students may vary.

1. Sorting Algorithm – QuickSort (or Java’s built-in sort using Timsort)

Figure 3-2: Sorting Algorithm

 I will use Collections.sort() with a custom Comparator to sort students by their average marks in
descending order.
63
  Java’s built-in sorting method (Collections.sort()) uses Timsort, a hybrid sorting algorithm that
combines Merge Sort and Insertion Sort for optimal performance.

 Time Complexity: O(n log n) (Best and Average cases).

2. Searching Algorithm – Linear Search

Figure 3-3: Searching Algorithm

 Since student IDs are not necessarily sorted, a simple linear search will be used to find a student
by ID.

 Time Complexity: O(n) in the worst case.

 For larger datasets, I could use a HashMap for O(1) lookup time, but since the dataset is expected
to be small, linear search suffices.

3. Ranking Algorithm

Figure 3-4: Ranking Algorithm

 I will compute the average score for each student and determine their ranking based on the
predefined score ranges.

 This is a simple O(1) operation since it involves a few conditional checks.

64
3.1.3 Program Implementation
My Student Management System follows the Object-Oriented Programming (OOP) paradigm in Java.
OOP is a programming paradigm based on the concept of objects, which are instances of classes that
contain data (fields/attributes) and behaviors (methods).

1. Programming Paradigm Used – Object-Oriented Programming (OOP)

My program follows the four key principles of OOP:

a) Encapsulation

 Each student's data (ID, name, marks) is stored inside a Student class.

 The fields are private, meaning data can only be accessed or modified through getter and setter
methods.

Figure 3-5: Encapsulation of program

Encapsulation prevents direct modification of data, ensuring better security and control.

b) Abstraction

65
 Figure 3-6: Abstraction of program

 The complex logic of ranking and calculating averages is hidden inside the Student class.

 Users of the class do not need to know how ranking is calculated; they just call getRanking().

Abstraction hides complexity and makes the Student class easy to use.

2. Program Implementation – How OOP is Used

a) My Main.java class acts as a controller that interacts with the Student objects stored inside an
ArrayList<Student>.

In OOP design, the controller handles logic and interacts with objects. In my project, Main.java is the
controller—it manages Student objects by calling their methods.

66
 Figure 3-7: Main.java class

 The controller (Main.java) stores and manages Student objects.

 Students are never directly modified—all changes go through the controller.

b) Students are stored dynamically in an ArrayList.

In my project, I use an ArrayList<Student> to store student records dynamically, meaning it can grow or
shrink as needed.

Figure 3-8: ArrayList<Student> to store student

I use ArrayList because:

 No fixed size—students are added and removed as needed.

 ArrayList<Student> provides fast access (O(1)) when retrieving by index.

c) Each student is an object with its own attributes and methods.

67
Each Student object has attributes (ID, name, marks) and methods (calculateAverage, getRanking,
setMarks, etc.).

Figure 3-9: Student’s attributes

How this work:

 Each student has a unique ID, name, and marks stored in attributes.

 The student object itself can calculate its own average and ranking (encapsulation).

 The controller (Main.java) doesn’t need to know the formula—it just calls
student.calculateAverage().

d) The program uses a menu-driven approach to interact with the user.

The menu in Main.java allows users to add, edit, delete, sort, search, and display students interactively.

68
69
 Figure 3-10: Menu-driven approach to interact with the user

How this works:

 The user is repeatedly prompted to enter a choice.

 Based on the input, the corresponding method in Main.java is called (e.g., addStudent(),
deleteStudent()).

 This provides an interactive experience, making it easy to manage student records.

3.1.4 Implementation Analysis

Now that I have implemented the Student Management System, I will analyze its strengths, limitations,
and potential improvements.

1. Strengths of My Implementation

 Object-Oriented Design (OOP) Makes the Code Modular

o Encapsulation: Student data is protected using private attributes.

o Abstraction: The ranking system is hidden within the Student class.

o Scalability: I can easily extend the program (e.g., add new student types).

 Efficient Searching and Sorting Algorithms

o Sorting: Uses Java’s Timsort (O(n log n)), which is efficient for moderate-sized data.

o Searching: Uses Linear Search (O(n)), which works well for small datasets.

 Interactive, Menu-Driven System

o Users can easily add, edit, delete, sort, and search students through a simple text-based
menu.

o The do-while loop ensures the user can keep interacting until they choose to exit.

 Dynamic Storage with ArrayList<Student>

o The size of the list is not fixed, so the program can handle any number of students within
the user-defined limit.

2. Limitations of My Implementation

70
  Linear Search Can Be Slow for Large Datasets

o Searching for a student by ID is done using a Linear Search (O(n)), which is not optimal for
large datasets.

o Improvement: I could use a HashMap (O(1)) to store students with their ID as the key.

 Sorting Algorithm Needs to Be Repeated

o Each time I need to sort students, I call Collections.sort().

o Improvement: I could maintain a sorted list and use Binary Insertion instead of re-sorting
every time.

 Data Is Not Saved Between Runs

o Currently, student data is lost when the program exits because everything is stored in
memory.

o Improvement: I could implement file handling (CSV, JSON, or database storage) to save
and load student records.

3.1.5 Results and Testing

The program successfully allows me to manage student records efficiently. The sorting feature correctly
arranges students in descending order of scores, and the searching function enables quick retrieval of
student details. To verify the correctness and robustness of my implementation, I conducted various test
cases covering different scenarios.

First, I tested adding students to ensure that their details were stored correctly. The program correctly
prevented duplicate Student IDs, maintaining data integrity. I also tested the sorting function by entering
students with varying scores and verifying that they were arranged in the expected order.

Next, I performed searches using both valid and invalid Student IDs. The program successfully retrieved
students when given valid IDs and displayed appropriate error messages when searching for non-existent
students. Another important test involved handling incorrect numerical input. When entering marks, I
deliberately provided non-numeric values to check if the program handled errors gracefully, which it did
by displaying an appropriate message and prompting for re-entry.

Additionally, I tested the responsiveness of the system by performing multiple operations in sequence,
such as adding, editing, deleting, and searching students within a single session. The program maintained
stability and did not crash, even when handling edge cases such as searching for a student after deleting
them.

71
Through this testing process, I confirmed that the program functions as intended. However, I identified
areas for improvement, such as implementing persistent storage to retain student records after the
program exits and optimizing search operations for better efficiency. Despite these potential
enhancements, the program meets the required specifications and successfully demonstrates the use of
a complex ADT and algorithm in solving a real-world problem.

3.2 Implement error handling and report test results. (P5)

3.2.1 Error Handling

To ensure my program operates safely and effectively, I have implemented error handling mechanisms
to handle unexpected situations. These mechanisms prevent crashes, ensure valid data entry, and
provide meaningful feedback to users.

1. Preventing Invalid Input for Numerical Values

When entering student marks, users might accidentally input non-numeric values (e.g., letters or
symbols). To prevent this, I use a while loop with exception handling to repeatedly prompt the user until
they enter a valid number.

Figure 3-11: Preventing Invalid Input for Numerical Values

 If the user enters a non-numeric value, the program catches the NumberFormatException and
asks for valid input.

 If the number is outside the valid range (0-10), it displays an error and asks again.

2. Preventing Duplicate Student IDs

72
To maintain data integrity, the program checks if a Student ID already exists before adding a new
student.

Fifure 3-12: Preventing Duplicate Student IDs code

 Before adding a student, the program checks if the ID already exists.

 If a duplicate ID is found, the program displays an error message and does not add the student.

User input:

Figure 3-13: Input to check Preventing Duplicate Student IDs

Test result:

Figure 3-14: Check Preventing Duplicate Student IDs output

3. Handling Student Not Found Errors (Search & Delete)

When searching for or deleting a student, the program handles cases where the Student ID does not
exist.

73
 Figure 3-15: Handling Student Not Found Errors code (part 1)

Figure 3-16: Handling Student Not Found Errors code (part 2)

 If a user searches for a non-existent Student ID, it displays an error instead of returning null.

 When attempting to delete a non-existent student, the program prevents accidental errors by
showing a message.

4. Handling Empty Student List Errors

Certain operations, like sorting and displaying students, should not run if there are no students in the list.

74
 Figure 3-17: Handling Empty Student List Errors code

 If there are no students, sorting and displaying functions show an error instead of running on an
empty list.

5. Preventing Invalid Menu Choices

If a user enters an invalid option in the menu, the program displays an error instead of crashing.

Figure 3-18: Preventing Invalid Menu Choices code

 The user must enter a number between 0 and 7.

3.2.2 Test Results Reporting

75
After implementing error handling, I conducted extensive testing to ensure the program works correctly
under different conditions. The test cases below cover normal operations, error handling, and edge
cases. Each test case includes the input, expected output, and actual output to verify correctness.

1. Handling Invalid Numerical Input

Test Case: Entering non-numeric values for marks

Input:

Figue 3-19: Test Case: Entering non-numeric values for marks

Expected Output:

Figure 3-20: Expected Output of test Case: Entering non-numeric values for marks

Actual output:

Figure 2-21: Actual output of test Case: Entering non-numeric values for marks

 Test passed

2. Preventing Duplicate Student IDs

Test Case: Adding a student with an existing ID

Input:

Figure 3-22: Test Case: Adding a student with an existing ID

76
Expected output:

Figure 3-23: Expected output of test Case: Adding a student with an existing ID

Actual output:

Figure 3-24:Actual output of test Case: Adding a student with an existing ID

 Test passed

3. Searching for a Student (Valid and Invalid IDs)

Test Case 1: Searching for an existing student

Input:

Figure 3-25: Input of Test Case 1: Searching for an existing student

Expected output:

Figure 3-26:Expected output of Test Case 1: Searching for an existing student

Actual output:

Figure 3-27: Actual output of Test Case 1: Searching for an existing student

 Test passed

Test Case 2: Searching for a non-existent student

Input:

77
 Figure 3-28: Input of Test Case 2: Searching for a non-existent student

Expected output:

Figure 3-29: Expected output of Test Case 2: Searching for a non-existent student

Actual output:

Figure 3-30: Actual output of Test Case 2: Searching for a non-existent student

 Test passed

4. Sorting Students Correctly

Test Case 1: Sorting students based on their average marks

Before Sorting:

Figure 3-31: Test Case 1: Sorting students based on their average marks (Before Sorting)

After Sorting (Expected Order – Descending Average Marks):

Figure 3-32: Test Case 1: Sorting students based on their average marks (After Sorting)

 Test passed

5. Handling Deleting Non-Existent Students

Test Case: Attempting to delete a student who is not in the system

78
Input:

Figure 3-33: Input of Test Case: Attempting to delete a student who is not in the system

Expected output:

Figure 3-34: Expected output of Test Case: Attempting to delete a student who is not in the system

Actual output:

Figure 3-35: Actual output of Test Case: Attempting to delete a student who is not in the system

 Test passed

6. Handling Empty Student List

Test Case: Sorting or displaying students when no students exist

Input:

Figure 3-36: Input of Test Case: Sorting or displaying students when no students exist

Expected output:

79
 Figure 3-37: Expected output of Test Case: Sorting or displaying students when no students exist

Actual output:

Figure 3-38: Actual output of Test Case: Sorting or displaying students when no students exist

 Test passed

7. Preventing Invalid Menu Choices

Test case: Enter invalid choice

Input:

Figure 3-39: Input of Test case: Enter invalid choice

Actual output:

Figure 3-40: Actual of Test case: Enter invalid choice

 Test passed

Table 3-1: Test results reporting

Test Case Expected Output Actual Output Result
Invalid numerical input Error message and re- Matches ✅ Pass
prompt
Duplicate Student ID Error message Matches ✅ Pass
Search valid ID Displays student details Matches ✅ Pass

80
 Search invalid ID Error message Matches ✅ Pass
Sorting students Sorted correctly Matches ✅ Pass
Deleting non-existent Error message Matches ✅ Pass
student
Sorting an empty list Error message Matches ✅ Pass
Enter invalid menu Error message and re- Matches ✅ Pass
choices prompt

3.3 Demonstrate How the Implementation of an ADT/Algorithm Solves a

Well-Defined Problem (M4)

3.3.1 Problem Definition

Specific Problem: Managing a Student List and Ranking by Grades

In an educational environment, teachers need an efficient way to store, update, and rank students based
on their grades. Manually managing student records and computing rankings can be time-consuming and
error-prone.

To solve this, I developed a Student Management System that allows users to:

 Add, edit, and delete students dynamically.

 Assign marks to students and compute their average grades.

 Rank students based on their performance.

 Sort and search for students efficiently.

Why This Problem Matters

 Without an automated system:

 Tracking student performance manually is inefficient.

 Sorting and ranking students takes too much time.

 Searching for a student's record is difficult in a large class.

My solution automates these tasks, improving efficiency and accuracy.

3.3.2 Solution Implementation

81
To solve the problem of managing a student list and ranking students based on their grades, I structured
my program using Object-Oriented Programming (OOP) principles and implemented Abstract Data Types
(ADT) and algorithms effectively. Below is a detailed breakdown of each component.

1. Student Class (Encapsulation and Data Management)

The Student class represents a single student and encapsulates their attributes and behaviors.

Features of Student Class

 Defines private attributes: id, name, mathMarks, scienceMarks, englishMarks, historyMarks.

 Encapsulates data: Provides getter and setter methods to safely access and modify student
details.

 Implements toString() to format student details for display.

82
 Figure 3-41: Student Class

Benefits:

83
  Encapsulation: Prevents direct modification of private fields.

 Data Formatting: The toString() method provides a clean display of student details.

2. StudentManager Class (Managing Student Records)

The StudentManager class (inside Main.java) acts as a controller to manage the list of students.

Features of StudentManager

 Maintains an ArrayList<Student> to store and manage students dynamically.

 Implements methods for adding, editing, deleting, sorting, and searching students.

 Uses input validation to ensure only valid data is stored.

Figure 3-42: StudentManager class

Benefits:

 Dynamic Storage: No fixed size limitation.

 Easy to search, sort, and modify students.

3. Adding a Student

Before adding a student, the program ensures that the Student ID is unique and that marks are valid.

Steps

 Checks for duplicate Student IDs before adding a new record.

 Ensures the marks are within the valid range (0-10).

 Adds the student only if all conditions are met.

84
 Figure 3-43: Adding a Student

Bebefits:

 Prevents duplicate Student IDs.

 Ensures that no more students are added beyond the allowed limit.

4. Editing a Student

Allows modification of a student’s name and marks while preserving the ID.

Figure 3-44: Editing a Student

Benefits:

85
  Ensures student identity is preserved while allowing name changes.

5. Deleting a Student

Searches for a student by ID and removes them if found.

Figure 3-45: Deleting a Student

Benefits:

 Prevents errors by checking if the student exists before deletion.

6. Sorting Students by Score

Uses Collections.sort() with a custom comparator to sort students in descending order of average marks.

Figure 3-46: Sorting Students by Score

Benefits:

 Uses Timsort (O(n log n)) for efficient sorting.

 Ranks students dynamically as new marks are added.

7. Searching for a Student

Uses Linear Search (O(n)) to find a student by ID.

86
 Figure 4-47: Searching for a Student

Benefits:

 Simple and effective for small datasets.

8. Displaying All Students

Iterates through the student list and prints formatted details.

Figure 3-48: Displaying All Students

Benefits:

 Prevents errors when the list is empty.

3.3.3 Solution Analysis

Now that I have implemented the Student Management System, I will analyze its strengths, limitations,
and possible improvements to ensure it is efficient, scalable, and maintainable.

1. Strengths of the Implementation

 Object-Oriented Design (OOP)

87
 o The program follows OOP principles by organizing logic into classes (Student, Main).

o Encapsulation ensures that student data is protected and only accessible through getter
and setter methods.

o The Main class acts as a controller, managing student operations without modifying
student details directly.

 Efficient Data Management with ArrayList<Student>

o Dynamic storage allows adding and removing students without memory constraints.

o Fast access (O(1)) when retrieving a student by index.

 Sorting and Ranking are Efficient

o Sorting is handled using Collections.sort(), which internally uses Timsort (O(n log n)),
making it fast and reliable.

o Ranking is computed in constant time (O(1)) using simple conditional checks.

 Error Handling and Input Validation

o Prevents duplicate Student IDs.

o Ensures marks are within the valid range (0-10).

o Handles invalid numerical input gracefully.

o Displays error messages instead of crashing on unexpected inputs.

 Menu-Driven System for Easy User Interaction

o Simple menu allows users to navigate easily.

o Ensures user input is always valid before proceeding.

2. Limitations of the Current Implementation

 Searching Uses Linear Search (O(n))

 Issue: Searching for a student by ID requires scanning the entire list (O(n)), which is inefficient
for large datasets.

88
  Potential Improvement: Use HashMap<String, Student> for O(1) lookup time instead of
ArrayList.

 Sorting Needs to Be Repeated Every Time

 Issue: Currently, Collections.sort() is called every time sorting is needed.

 Potential Improvement: Instead of sorting every time, maintain a sorted list and use binary
insertion (O(log n)) to add students in sorted order.

 Data is Lost When Program Exits

 Issue: Right now, student records are stored in memory (ArrayList), but they are lost when the
program is closed.

 Potential Improvement: Implement file storage (CSV, JSON, or database) to save and load
student records automatically.

 No Graphical Interface (Only Console-Based)

 Issue: Right now, the program runs in text-based mode (console), which can be improved with
a Graphical User Interface (GUI) for better user experience.

 Potential Improvement: Use Java Swing or JavaFX to create a GUI-based student management
system.

3.3.4 Test Run Results

Now that I have implemented my Student Management System, I ran multiple tests to demonstrate its
functionality. Below, I will walk through the program step by step to show how it performs different
tasks.

1. Setting the Maximum Number of Students

When I first launched the program, it prompted me to enter the maximum number of students allowed
in the class. This ensures that the system does not exceed the specified limit.

Example Run:

Figure 3-49: Test Run Results Setting the Maximum Number of Students

89
After entering 3, the program restricted the total number of students to this limit.

The program correctly sets a student limit, preventing more students from being added than allowed.

2. Adding Students (With Limit Check)

I proceeded to add students to the system.

Example Runs:

Figure 3-50: Example Runs of Adding Students (part 1)

Figure 3-51: Example Runs of Adding Students (part 2)

Figure 3-52: Example Runs of Adding Students (part 3)

However, when I tried adding a fourth student, the program prevented the action since the maximum
limit was reached:

Figure 3-53: Example Runs of Adding Students (part 4)

90
The program correctly enforces the student limit and prevents exceeding the allowed number of
students.

3. Assigning Marks to a Student

After adding students, I assigned valid marks to them.

Figure 3-54: Example run of Assigning Marks to a Student (part 1)

But when I entered an invalid value (letters instead of numbers), the program handled the error
gracefully:

Figure 3-55: Example run of Assigning Marks to a Student(part 2)

The program correctly validates input, ensuring that only numbers between 0 and 10 are accepted.

4. Searching for a Student

When I searched for a valid student, the program displayed their details:

Figure 3-56: Example run of Searching for a Student (part 1)

However, searching for a non-existent student gave an appropriate error message:

91
 Figure 3-57: Example run of Searching for a Student (part 2)

The search function works correctly, allowing users to find students while handling invalid IDs properly.

5. Sorting Students by Scores

I added more marks to students and tested the sorting feature, which arranged them in descending
order of average marks:

Before Sorting:

Figure 3-58: Example run of Sorting Students by Scores (part 1)

After Sorting:

Figure 3-59: Example run of Sorting Students by Scores (part 2)

Figure 3-60: Example run of Sorting Students by Scores (part 3)

The sorting algorithm correctly ranks students from highest to lowest score.

6. Editing a Student’s Name

When I wanted to correct a student’s name, I used the edit function. The program preserved the Student
ID while updating the name:

Figure 3-61: Example run of Editing a Student’s Name

The program allows easy modification of student details while maintaining ID consistency.

7. Deleting a Student

92
When I removed a student, the program confirmed the deletion:

Figure 3-62: Example run of Deleting a Student (part 1)

However, trying to delete a non-existent student displayed an error message:

Figure 3-63: Example run of Deleting a Student (part 2)

The program properly deletes students and prevents errors when trying to remove non-existent entries.

8. Displaying All Students

When I displayed all students, the program formatted and printed the details clearly:

Figure 3-64: Displaying All Students

The program correctly displays student records in a user-friendly format.

9. Handling an Empty Student List

Finally, I tested what happens if I try sorting or displaying students when no records exist. The program
correctly displayed an error message:

Figure 3-65: Handling an Empty Student List(part 1)

93
 Figure 3-66: Handling an Empty Student List(part 2)

The program prevents unnecessary operations when no students are in the system.

After running these tests, I confirmed that my Student Management System:

 Enforces the maximum student limit from the start.

 Prevents duplicate Student IDs while allowing valid student additions.

 Handles invalid input properly, ensuring accurate data entry.

 Allows searching, editing, deleting, and displaying students smoothly.

 Ranks students correctly based on their scores.

 Handles empty lists gracefully without errors.

My Student Management System provides an efficient and structured way to manage student records. It
automates sorting, ranking, searching, and validation, making it an effective solution for educational
institutions.

With future enhancements like database storage and a graphical interface, this system can be expanded
into a full-featured student management application.

CHAPTER 4: Assess the effectiveness of data structures and algorithms (L04)

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

4.1.1 What is Asymptotic Analysis?

Definition:

Asymptotic analysis is a method of describing the limiting behavior of a function when the argument
tends towards a particular value or infinity. In computer science, it is commonly used to analyze the
performance of algorithms as the input size grows.

Importance:

 Compares algorithms independently of hardware and implementation.

 Predicts performance for large inputs, aiding scalability.

94
  Identifies bottlenecks to optimize speed and memory.

Real-Life Example:

 Algorithm A: Fast for small inputs (100 numbers in 1 sec) but slow for large ones (1M numbers in
1 hour).

 Algorithm B: Slower initially (100 numbers in 2 sec) but scales efficiently (1M numbers in 10 sec).

4.1.2 Asymptotic Notations

Asymptotic analysis describes an algorithm's growth rate as input size increases. The main notations
include:

 Big O (O): Upper bound, worst-case complexity (e.g., O(n²) means quadratic growth).

 Big Omega (Ω): Lower bound, best-case complexity (e.g., Ω(n) means linear growth).

 Big Theta (Θ): Tight bound, exact asymptotic behavior (e.g., Θ(n log n) means proportional
growth).

 Little o (o): Loose upper bound, grows slower than a function (e.g., o(n²) is slower than n²).

 Little omega (ω): Loose lower bound, grows faster than a function (e.g., ω(n) is faster than n).

4.1.3 Asymptotic Analysis Process

Asymptotic analysis evaluates an algorithm’s efficiency as input size grows. The process includes:

 Identify Basic Operations: Find key operations affecting runtime (e.g., comparisons, assignments).

 Define Input Size (n): Represent input size, such as list length or matrix size.

 Express Operations as a Function: Formulate T(n)T(n)T(n), the number of operations in terms of

nnn.

 Determine the Dominant Term: Identify the fastest-growing term in T(n)T(n)T(n).

 Apply Asymptotic Notation: Use Big O, Ω, or Θ to classify complexity.

Example: Finding the Maximum Element in an Array

95
 Figure 4-1: Example: Finding the Maximum Element in an Array

Asymptotic Analysis

Step-by-Step Asymptotic Analysis Process

1. Identify the Basic Operations

 Initialization (int max = arr[0]) → O(1)

 Loop (for (int i = 1; i < arr.length; i++)) → O(n-1)

 Comparison (if (arr[i] > max)) → O(1) (runs n-1 times)

 Assignment (max = arr[i]) → O(1) (runs n-1 times, in the worst case)

 Return Statement (return max) → O(1)

2. Establish the Input Size (n)

 The input size n represents the number of elements in the array (arr.length).

3. Express the Number of Operations as a Function of n

T(n)=1+(n−1)+(n−1)+(n−1)+1T(n) = 1 + (n - 1) + (n - 1) + (n - 1) + 1T(n)=1+(n−1)+(n−1)+(n−1)+1
T(n)=3n−2T(n) = 3n - 2T(n)=3n−2

4. Determine the Dominant Term

96
  As n grows large, constant terms (-2) become insignificant.

 The dominant term is n, so the time complexity is O(n).

5. Apply Asymptotic Notation

 Since execution time grows linearly with input size, the algorithm runs in O(n) (linear time).

4.1.4 Illustrative Example

To demonstrate asymptotic analysis in practice, let's analyze a simple Java program that calculates the
sum of all elements in an array.

Example: Summing Elements in an Array (O(n))

Figure 4-2: Example: Summing Elements in an Array (O(n))

Asymptotic Analysis

1. Identify Basic Operations

 Initialization (int total = 0) → Constant time O(1).

 Loop (for (int num : arr)) → Runs n times, contributing to O(n).

 Addition (total += num) → Happens inside the loop, so it runs n times (O(n)).

97
  Return statement → O(1).

2. Establish the Input Size (n)

 The input size is the length of the array (n).

3. Express the Number of Operations as a Function of n

 The total number of operations can be expressed as:

T(n)=1+n+n+1=2n+2T(n) = 1 + n + n + 1 = 2n + 2T(n)=1+n+n+1=2n+2

4. Determine the Dominant Term

 As n grows larger, constant terms (+2) become insignificant.

 The dominant term is n, so the time complexity is O(n).

5. Apply Asymptotic Notation

 Since the execution time grows linearly with input size, the algorithm runs in O(n) (linear time).

Example: Nested Loop (O(n²))

Now, let's analyze a program that prints all pairs of elements in an array.

Figure 4-3: Example: Nested Loop (O(n²))

Asymptotic Analysis

98
1. Identify Basic Operations

 Outer loop (for i = 0 to n-1) → Runs n times.

 Inner loop (for j = 0 to n-1) → Runs n times for each iteration of i.

 Printing (System.out.println(...)) → Happens n * n = n² times (O(n²)).

2. Express the Number of Operations as a Function of n

T(n)=n×n=n2T(n) = n \times n = n^2T(n)=n×n=n2

3. Determine the Dominant Term

 The highest order term is n², so lower-order terms and constants are ignored.

4. Apply Asymptotic Notation

 Since the execution time grows quadratically as input size increases, the time complexity is O(n²)
(quadratic time).

Summary of Examples

Table 4-1: Summary of Examples

Algorithm Operations Count Complexity
Sum of elements in an array 2n + 2 O(n) (Linear Time)
Printing all pairs of elements n² O(n²) (Quadratic Time)

4.1.5 Benefits of Asymptotic Analysis

Asymptotic analysis provides a structured approach to evaluating algorithm efficiency, helping
developers choose the best algorithm for a given problem. Below are the key benefits of using
asymptotic analysis in computer science.

1. Helps Compare Algorithms Objectively

 Asymptotic analysis allows us to compare algorithms without running them on specific hardware.

 For example, if one sorting algorithm runs in O(n²) and another in O(n log n), we know the latter
is more efficient for large inputs.

Example:

 Bubble Sort → O(n²) (Slow for large n).

99
  Merge Sort → O(n log n) (Scales better).

Without asymptotic analysis, we might choose an inefficient algorithm just because it runs fast for small
inputs.

2. Predicts Performance for Large Inputs

 Some algorithms work well for small datasets but become too slow for large data.

 Asymptotic analysis helps anticipate performance issues before deployment.

Example:

Searching for a student's record in my Student Management System:

 Linear Search → O(n) (Slower for large datasets).

 HashMap Lookup → O(1) (Much faster for large datasets).

If the system grows to thousands of students, switching from O(n) to O(1) searching is a necessary
optimization.

3. Ignores Unimportant Factors (Focuses on Growth Rate)

 Instead of measuring exact runtime (which depends on hardware, compiler, etc.), asymptotic
analysis focuses only on the algorithm's growth rate.

 Example: Two computers might run the same algorithm at different speeds, but asymptotic
complexity remains the same.

This makes asymptotic analysis a universal method for evaluating efficiency.

4. Helps Optimize Code for Better Performance

 By identifying bottlenecks, asymptotic analysis helps programmers refactor inefficient code to

improve performance.

 Example: If an algorithm runs in O(n²) and can be optimized to O(n log n), the speed
improvement is significant for large n.

Instead of writing code blindly, developers can use asymptotic analysis to guide optimizations.

5. Reduces Time and Memory Complexity

 Asymptotic analysis helps reduce execution time and memory usage by choosing more efficient
algorithms.

100
  Example: If two algorithms achieve the same result, the one with lower complexity will save
computing resources.

Better efficiency means lower costs and better user experience in real-world applications.

4.1.6 Practical Applications of Asymptotic Analysis

Asymptotic analysis is widely used in software development, data structures, and algorithm design to
improve performance and scalability.

1. Optimizing Search Algorithms

In databases and search engines, Binary Search (O(log n)) is preferred over Linear Search (O(n)) for
efficiency.

Example: Searching for a student's record in my Student Management System:

 Linear Search (O(n)) → Checks each student one by one.

 HashMap Lookup (O(1)) → Retrieves the student instantly.

This helps scale systems handling thousands or millions of records.

2. Improving Sorting Efficiency

 Merge Sort (O(n log n)) is used instead of Bubble Sort (O(n²)) in large datasets.

 Example: In e-commerce platforms, sorting thousands of products quickly improves the user
experience.

Sorting efficiency is crucial for applications like ranking, filtering, and recommendation systems.

3. Enhancing Big Data Processing

 Algorithms with O(n) or better complexity are essential in big data applications where billions of
records need to be processed.

 Example: Google and Facebook use optimized hashing (O(1)) and graph algorithms (O(n log n)) for
data retrieval.

Without efficient algorithms, large-scale applications would slow down significantly.

4. Improving Machine Learning Model Training

 Gradient Descent (O(n)) is optimized over Brute Force Training (O(n²)) in machine learning.

101
  Example: Training an AI model on millions of data points requires selecting the best optimization
algorithms to reduce computation time.

This ensures AI models can be trained efficiently within practical time limits.

4.1.7 How to Present Asymptotic Analysis in a Report

When writing a report on asymptotic analysis, it's important to present the information in a structured
and professional manner. Below is an effective way to organize it.

1. Introduction

 Briefly define asymptotic analysis and explain its purpose.

 Mention why it is important in evaluating algorithm efficiency.

2. Asymptotic Notations

 Explain Big O, Omega (Ω), and Theta (Θ) with simple examples.

 Use tables or graphs to visually represent growth rates.

3. Process of Asymptotic Analysis

 Break down a sample algorithm into basic operations.

 Explain how to find T(n) and dominant term.

 Use Java code examples for clarity.

4. Practical Applications

 List real-world use cases, such as search engines, sorting large datasets, or AI training models.

 Keep explanations short and relevant.

5. Conclusion

 Summarize why asymptotic analysis is important.

 Suggest future improvements, such as using more efficient data structures.

4.2 Determine two ways in which the efficiency of an algorithm can be

measured, illustrating your answer with an example.(P7)

102
4.2.1 What is Algorithm Efficiency?
Definition

Algorithm efficiency refers to how well an algorithm performs in terms of execution time and memory
usage as the input size increases. It helps determine which algorithm is best suited for a given problem,
especially when dealing with large datasets.

4.2.2 Measuring Execution Time

One of the most common ways to measure the efficiency of an algorithm is by evaluating its execution
time, which refers to the amount of time an algorithm takes to complete a task.

 Why Measure Execution Time?

 Helps compare different algorithms and choose the fastest one.

 Identifies performance bottlenecks in a program.

 Ensures that an algorithm scales well with larger input sizes.

 How to Measure Execution Time in Java

We can measure execution time in Java using System.nanoTime() or System.currentTimeMillis().

Example: Comparing Linear Search vs. Binary Search

This example measures the time taken by Linear Search (O(n)) and Binary Search (O(log n)) to find an
element in an array.

103
 Figure 4-4: Example: Comparing Linear Search vs. Binary Search

Output:

Figure 4-5: Output of Example: Comparing Linear Search vs. Binary Search

104
4.2.3 Measuring Space Usage
Another important way to evaluate algorithm efficiency is by analyzing its space complexity, which refers
to the amount of memory an algorithm uses during execution.

 Why Measure Space Usage?

 Prevents programs from using excessive memory, which can cause crashes.

 Helps in selecting algorithms that optimize RAM usage.

 Important for embedded systems and mobile applications where memory is limited.

 How to Measure Space Complexity?

Space complexity is calculated by analyzing:

 Fixed memory usage (O(1)) → Variables, constants.

 Dynamic memory usage (O(n)) → Arrays, lists, recursion.

Example: Comparing Iterative vs. Recursive Factorial

This example shows how recursion can use more memory than iteration.

105
 Figure 4-6: Example: Comparing Iterative vs. Recursive Factorial

Output:

106
 Figure 4-7: Out put of Example: Comparing Iterative vs. Recursive Factorial

Space Complexity Comparison

Table 4-2: Space Complexity Comparison

Algorithm Memory Usage Space Complexity
Iterative Factorial Uses a single variable O(1)
Recursive Factorial Uses extra stack frames O(n)

Recursion uses more memory because each recursive call is stored in the call stack.

4.2.4 Illustrative Comparison Using Graphs

To visually compare execution time and space usage for different algorithms, I will present two graphs:

 Execution Time vs Input Size → Shows how Linear Search (O(n)) and Binary Search (O(log n))
perform as input size increases.

 Memory Usage vs Input Size → Compares Iterative Factorial (O(1)) vs Recursive Factorial (O(n)).

1. Execution Time Comparison

Example Scenario: Searching for a student in a list of increasing size

Table 4-3: Searching for a student in a list of increasing size

Input Size (n) Linear Search Time (O(n)) Binary Search Time (O(log
n))
100 2 ms 0.5 ms
1000 10 ms 1 ms
10000 50 ms 2 ms

107
 100000 250 ms 3 ms
1000000 1200 ms 5 ms

Graph: Execution Time vs Input Size

Linear Search (O(n)) increases much faster than Binary Search (O(log n)).

Graph Representation:

 X-axis: Input Size (n)

 Y-axis: Execution Time (ms)

Figure 4-8: Graph: Execution Time vs Input Size

Binary Search remains fast, while Linear Search slows down significantly.

2. Space Usage Comparison

Example Scenario: Factorial Calculation for Increasing n

Table 4-4 : Space Usage Comparison

n (Factorial Input Size) Iterative Factorial Memory Recursive Factorial
(O(1)) Memory (O(n))
5 16 bytes 80 bytes
10 16 bytes 160 bytes

108
 15 16 bytes 240 bytes
20 16 bytes 320 bytes
30 16 bytes 480 bytes

Graph: Space Usage vs Input Size

Recursive Factorial (O(n)) uses more memory as n increases, while Iterative Factorial remains constant
(O(1)).

Graph Representation:

 X-axis: Input Size (n)

 Y-axis: Memory Used (bytes)

Figure 4-9: Graph: Space Usage vs Input Size

Recursive Factorial increases memory usage linearly, while Iterative Factorial remains efficient.

4.3 Interpret what a trade-off is when specifying an ADT, using an example

to support your answer.(M5)

4.3.1 Definition and Meaning of Trade-offs in ADTs

109
A trade-off in Abstract Data Types (ADTs) refers to the need to balance different design factors, such as
time complexity, space efficiency, and ease of use, when choosing a data structure. Since no single ADT
excels in all aspects, developers must make compromises based on the specific requirements of a system
(Goodrich & Tamassia, 2014).

For example, an array-based list offers fast random access (O(1)), but inserting elements in the middle is
slow (O(n)) due to shifting elements. On the other hand, a linked list allows fast insertions and deletions
(O(1) at the head) but suffers from slower access time (O(n))

Key Trade-off Considerations in ADTs

 Time Complexity – Speed of operations such as insertion, deletion, and search.

 Space Complexity – Amount of memory consumed by the data structure.

 Ease of Implementation – Complexity of coding and maintaining the ADT.

 Flexibility – Ability to adapt to dynamic data sizes and operations.

4.3.2 Factors to Consider When Making Trade-offs in ADTs

When choosing an Abstract Data Type (ADT), trade-offs must be considered based on different factors.
The goal is to select the most suitable ADT for a given problem while balancing efficiency, memory usage,
and implementation complexity. Here are the key factors:

1. Time Complexity

Each ADT has different time complexities for operations like searching, inserting, and deleting. For
example, an array-based list (ArrayList) allows O(1) access to any element using an index, but inserting or
deleting in the middle requires shifting elements (O(n)). A linked list allows fast insertions and deletions
(O(1) at the front) but takes O(n) to find an element.

2. Space Complexity

Some ADTs require extra memory overhead. Linked lists use extra space for pointers, while arrays can
waste memory if they are pre-allocated with more space than needed. A hash table may use more
memory than a sorted array but offers faster lookups.

3. Ease of Implementation and Maintenance

Simple ADTs like arrays are easy to implement but lack flexibility. Linked lists, trees, and hash tables
require more code and logic but provide better adaptability. The more complex the structure, the harder
it is to debug and maintain.

110
4. Flexibility and Modifiability

Arrays (Static Structures): Fixed size, making resizing difficult.

Linked Lists & Trees (Dynamic Structures): Can grow or shrink dynamically but involve additional memory
management.

5. Data Access Patterns

If fast lookups are needed, an array or hash table is preferred. If frequent insertions and deletions are
required, a linked list or binary tree might be better.

6. Application Requirements

Choosing the right ADT depends on the specific use case. A stack is great for function calls and undo
operations, while a queue is better for scheduling tasks. If searching is common, a binary search tree is a
good choice.

4.3.3 Illustrating Trade-offs Through Examples

To understand trade-offs in ADTs, let's consider some real-world examples where choosing the right data
structure impacts performance and efficiency.

Example 1: Choosing Between an Array and a Linked List for a To-Do List

Imagine I am building a to-do list application where users can add, remove, and access tasks. Should I use
an array (ArrayList) or a linked list (LinkedList)?

Table 4-5: Choosing Between an Array and a Linked List for a To-Do List
Operation Array (ArrayList) Linked List (LinkedList)
Adding a task at the end Fast (O(1) amortized) Fast (O(1))
Adding a task in the middle Slow (O(n) due to shifting) Fast (O(1) if pointer is known)
Removing a task in the middle Slow (O(n)) Fast (O(1) if pointer is known)
Accessing a task by index Fast (O(1)) Slow (O(n))

Trade-off:

 If the app mainly retrieves tasks by index, an ArrayList is better because it provides O(1) access.

 If the app frequently inserts or deletes tasks in the middle, a LinkedList is better since it avoids
shifting elements.

Example 2: Stack vs. Queue for a Web Browser

111
A web browser needs to handle the "Back" and "Forward" buttons. Which ADT is better?

 Stack (LIFO - Last In, First Out): Perfect for "Back" functionality, as the most recent page is
revisited first.

 Queue (FIFO - First In, First Out): Useful for loading web pages in order, such as processing
multiple download requests.

Trade-off:

 Stack is better for undo operations, where the last action must be undone first.

 Queue is better for processing tasks in order, like printer job scheduling or background
downloads.

Example 3: Hash Table vs. Binary Search Tree for a Phonebook

A phonebook application needs to store and retrieve contacts efficiently. Two common data structures
are:

 Hash Table (O(1) average time for search, insert, delete)

 Binary Search Tree (O(log n) search, but ordered elements)

Trade-off:

 If quick lookups are needed without maintaining order, a hash table is best.

 If sorted data is required, a binary search tree is better, as it allows in-order traversal.

Each ADT has strengths and weaknesses, and the right choice depends on the application's
requirements.

4.3.4 Implementation Example: ArrayList vs. LinkedList

To fully understand the trade-offs between ArrayList and LinkedList, I will first implement both in a to-do
list application and then measure their execution time for common operations. I will analyze each result
with real performance data to provide concrete proof.

4.3.4.1 Using ArrayList for a To-Do List

An ArrayList is backed by an array, meaning it provides fast access (O(1)) but slower insertions and
deletions (O(n)) due to shifting elements.

112
 Figure 4-10: Using ArrayList for a To-Do List

Output:

Figure 4-11: Output of Using ArrayList for a To-Do List

Analysis

 Fast retrieval of tasks using get(index), making it ideal if I frequently need to display tasks.

 Slower deletion, as removing an element shifts everything left.

 Efficient memory use, as it stores elements in a contiguous block.

4.3.4.2 Using LinkedList for a To-Do List

A LinkedList is better for insertions and deletions, but accessing elements takes longer because traversal
is required.

113
 Figure 4-12: Using LinkedList for a To-Do List

Output:

Figure 4-13: Output of Using LinkedList for a To-Do List

Analysis

 Fast insertion/deletion at the beginning or middle (O(1)) as no shifting is required.

 Slower access, since I must traverse the list (O(n)).

 More memory usage, as each node stores additional pointers.

4.3.4.3 Measuring Execution Time for Both Implementations

To provide proof of trade-offs, I will measure execution time for:

114
  Adding elements at the end (O(1) for both).

 Adding elements at the beginning (O(n) for ArrayList, O(1) for LinkedList).

 Accessing elements by index (O(1) for ArrayList, O(n) for LinkedList).

 Removing elements from the beginning (O(n) for ArrayList, O(1) for LinkedList).

Figure 4-14: Measuring Execution Time for Both Implementations

Output:

115
 Figure 4-15: Output of Measuring Execution Time for Both Implementations

a) Performance Results & Proof

Table 4-6 : Performance Results & Proof

Operation ArrayList Time LinkedList Time Winner
Adding at end (O(1)) 2 ms 5 ms ArrayList ✅
Adding at start (O(n) vs 35 ms 0.0005 ms LinkedList ✅
O(1))
Accessing middle 0.00005 ms 12 ms ArrayList ✅
element (O(1) vs O(n))
Removing first element 28 ms 0.0005 ms LinkedList ✅
(O(n) vs O(1))

b) Final Evaluation

Table 4-7 : Final Evaluation

Factor ArrayList LinkedList
Best for... Quick access to elements Frequent insertions/removals
Insertion at end Fast (O(1)) Fast (O(1))
Insertion at start Slow (O(n)) due to shifting Fast (O(1))
Access by index Very fast (O(1)) Slow (O(n)) – Traversal required
Memory usage Less overhead More overhead (extra pointers)

c) Conclusion

116
  ArrayList is faster for random access (O(1)), making it better for applications where I frequently
retrieve elements by index.

 LinkedList is much faster for insertions and deletions (O(1) for adding/removing at the beginning),
making it better for dynamic modifications.

 ArrayList struggles with inserting/removing at the start (O(n)), proving that shifting elements is
costly.

 LinkedList struggles with accessing elements (O(n)), proving that traversal slows it down.

4.3.5 Evaluation of Trade-offs

Now that I have implemented and tested ArrayList and LinkedList, I will evaluate their trade-offs based
on concrete performance results. The evaluation will focus on the following key aspects:

1. Time Complexity Trade-offs

Table 4-8 : Time Complexity Trade-offs

Operation ArrayList LinkedList Winner
Complexity Complexity
Adding at end O(1) (Amortized) O(1) Tie
Adding at start O(n) (Shifting Needed) O(1) (Pointer Update) LinkedList
Access by index O(1) (Direct Access) O(n) (Traversal Needed) ArrayList
Removing first element O(n) (Shifting Needed) O(1) (Pointer Update) LinkedList

Analysis:

 ArrayList wins when fast access by index is required (O(1)).

 LinkedList is better when frequent insertions or deletions are needed (O(1)).

 Both perform equally well when adding at the end (O(1)).

2. Space Complexity Trade-offs

Table 4-9 : Space Complexity Trade-offs

Factor ArrayList LinkedList Winner
Memory Usage Low (O(n), compact) High (O(n), extra ArrayList
pointers)
Cache Efficiency High (contiguous Low (scattered ArrayList
memory) memory)

117
Analysis:

 ArrayList consumes less memory, as it only stores the elements.

 LinkedList has additional memory overhead due to storing pointers for each node.

 ArrayList benefits from better cache locality, making it faster for sequential access.

3. Performance Trade-offs Based on Real Execution Time

Table 4-10 : Performance Trade-offs Based on Real Execution Time

Operation ArrayList Time (ms) LinkedList Time Winner
(ms)
Adding at end (O(1)) 2 ms 5 ms ArrayList
Adding at start (O(n) vs 35 ms 0.0005 ms LinkedList
O(1))
Accessing middle 0.00005 ms 12 ms ArrayList
element (O(1) vs O(n))
Removing first element 28 ms 0.0005 ms LinkedList
(O(n) vs O(1))

4. When to Choose Each Data Structure?

Table 4-11 : When to Choose Each Data Structure?

Use Case Best Choice Reasoning
Frequent element access ArrayList Direct indexing (O(1))
Frequent insertions/deletions LinkedList No shifting needed (O(1))
Memory efficiency ArrayList No extra pointers
Handling large datasets ArrayList Better cache locality
Processing real-time updates LinkedList Efficient modifications

Final Conclusion

 If I need fast element access, I should use an ArrayList.

 If my application involves frequent insertions and deletions, a LinkedList is better.

 If memory efficiency is a priority, ArrayList is the best choice.

 If performance optimization is required, I should measure execution time before deciding.

This analysis is backed by real execution results, ensuring a data-driven decision for choosing the best
ADT.

118
 CONCLUSION
In conclusion, the design and implementation of the Student Management System for Soft Development
ABK has proven to be an effective solution addressing the challenges faced by educational institutions in
managing student records, tracking performance, and facilitating communication. The project
successfully integrates essential functionalities such as student data management, ranking based on
academic performance, and efficient search and retrieval of student information, all while ensuring data
integrity and user-friendly interaction.

The use of an ArrayList as the primary data structure allows for dynamic storage and efficient
management of student records, enhancing the system's operational efficiency. The implementation of
robust error handling mechanisms ensures that the system remains reliable and user-friendly, even in
the face of invalid inputs or unexpected scenarios. Through comprehensive testing and validation, the
system has demonstrated its capability to meet both user and system requirements, providing a
dependable platform for educational institutions to streamline their administrative processes.

This Student Management System empowers educational organizations with the necessary tools to
enhance their day-to-day operations, improve student engagement, and support informed decision-
making. The project's success highlights the significance of a well-structured system in promoting
academic excellence and achieving institutional objectives. As educational environments continue to
evolve, the implementation of such systems will be crucial in adapting to the changing needs of students
and educators alike.

EVALUATION
Upon evaluating the Student Management System developed for Soft Development ABK, it is evident
that the project has effectively addressed the primary challenges faced by educational institutions in
managing student records and performance tracking. The system's comprehensive functionalities,
including student data management, ranking based on academic performance, and efficient search
capabilities, have been seamlessly integrated to enhance operational efficiency. The implementation of
robust error handling and input validation ensures that the system remains reliable and user-friendly,
allowing users to perform their tasks without unnecessary complications.

The system's dynamic data management capabilities empower educators and administrators to make
informed decisions based on accurate and up-to-date information regarding student performance.
However, the initial adaptation phase may pose a challenge for some users who need to familiarize
themselves with the new technology. Despite this, the opportunities for future enhancements—such as

119
implementing a graphical user interface (GUI) or integrating with external educational tools—present
promising avenues for growth.

Overall, the Student Management System stands as a valuable asset for educational institutions, with the
potential to significantly improve administrative processes and support better academic outcomes.

REFERENCE
Bloch, J. (2018) Effective Java. 3rd edn. Boston: Addison-Wesley.

Eckel, B. (2006) Thinking in Java. 4th edn. Prentice Hall.

Goodrich, M. T., & Tamassia, R. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.

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

Arnold, K., Gosling, J. and Holmes, D., 2005. The Java Programming Language. 4th edn. Boston: Addison-
Wesley.

Sedgewick, R. and Wayne, K. (2011) Algorithms. 4th ed. Boston: Addison-Wesley.

Horstmann, C.S. and Cornell, G. (2013) Core Java Volume I: Fundamentals. 9th edn. Prentice Hall

Sierra, K. and Bates, B., 2005. Head First Java. 2nd edn. Sebastopol, CA: O'Reilly Media.

Liang, Y.D., 2018. Introduction to Java Programming and Data Structures. 11th edn. Hoboken, NJ:
Pearson.

Deitel, P.J. and Deitel, H.M., 2017. Java: How to Program. 11th edn. Boston: Pearson.

Schildt, H., 2018. Java: The Complete Reference. 11th edn. New York: McGraw-Hill Education.

Stallings, W. (2015) Computer Organization and Architecture: Designing for Performance. 9th edn.
Boston: Pearson.

Venkat, S., 2014. Functional Programming in Java. 1st edn. Boston: Pragmatic Bookshelf.

Hunt, A. and Thomas, D., 1999. The Pragmatic Programmer: Your Journey to Mastery. Boston: Addison-
Wesley.

Gamma, E., Helm, R., Johnson, R. and Vlissides, J., 1994. Design Patterns: Elements of Reusable Object-
Oriented Software. Boston: Addison-Wesley.

Fowler, M., 2002. Patterns of Enterprise Application Architecture. Boston: Addison-Wesley.

120
Flanagan, D., 2019. JavaScript: The Definitive Guide. 7th edn. Sebastopol, CA: O'Reilly Media.

Bennett, S., McRobb, S., & Farmer, R. (2010). Object-Oriented Systems Analysis and Design Using UML.
McGraw-Hill Education.

Liskov, B. (1987). Data Abstraction and Hierarchy. In: Proceedings of the 1987 ACM Conference on
Object-Oriented Programming Systems, Languages, and Applications (OOPSLA '87). ACM, New York, NY,
USA, 17-34. DOI: 10.1145/38765.38773.

Asymptotic analysis. (n.d.). Wikipedia. Available at: https://en.wikipedia.org/wiki/Asymptotic_analysis

(Accessed: 17 March 2025).

CSE373: Data Structures and Algorithms Lecture 4: Asymptotic Analysis. (2014). Available at:
https://courses.cs.washington.edu/courses/cse373/14wi/lecture4.pdf (Accessed: 17 March 2025).

Levitin, A. (2007) Introduction to the Design and Analysis of Algorithms. 2nd edn. Boston: Pearson
Addison-Wesley.

121