Basic Laboratory Rules

1. Laboratory Conduct: Students must maintain utmost professionalism in the laboratory.

Use of computers and network must comply with the computer lab policy.

2. Face-to-Face Mode Policy: Laboratory sessions will be conducted in F2F mode by default,

unless the University announces a change of modality of delivery.

3. Laboratory Session Structure: Sessions are generally composed of at least an hour of

discussions on pre-lab concepts and theories, while the remaining time are allocated for

deliverables.

4. Coding conventions: Students are expected to observe proper coding conventions

specified in their respective programming language standards.

5. Late Submission Penalty: Late submissions will receive 5 point deduction within the first

day, and 2 points per succeeding days (including weekends).

6. Generative AI Use Policy: Use of Generative AI tools for generating codes is banned, and

will be considered as an act of academic dishonesty.

7. Cheating, Plagiarism, and Acts of Academic Dishonesty: Any form of dishonesty is

prohibited and shall be severely dealt with by the University according to the Student

Handbook.

8. Individual and Group Work: All lab exercises must be done individually. Group

collaboration is only allowed for group projects.

9. Final Project: Project is to be done with at most 3 members in a team. The project must

attempt to solve a real-world problem or scenario, and demonstrates the ability to

correctly and effectively use data structures and algorithms.

2
 Table of Contents
Module 1: Introduction to Data Structures and Algorithms 6
I. Objectives 6
II. Materials 6
III. Pre-lab Discussion 6
Data Structures and Algorithms 6
Pseudocode and Conventions 7
Algorithm Analysis and Big-Θ Notation 11
Operation Counting Rules 13
Terminology 15
IV. Laboratory Activities 16
1. Time to Solve for a Given Data 16
2. Maximum Element Search Algorithm 17
3. Worst-Case Time Complexity Table 18
4. Comparing Time Performances 19
V. Summary of Deliverables 19
References: 19
Module 2: Linked List Data Structure 20
I. Objectives 20
II. Materials 20
III. Pre-lab Discussion 20
Linked List 20
Operations on Linked Lists 21
Singly-linked list 26
Doubly-linked lists 26
Circular linked lists 26
IV. Laboratory Familiarization Exercises 27
V. Laboratory Activities 32
1. Utilizing Linked Lists 32
2. Implementing a Linked List 32
3. Josephus problem 33
4. LinkedList Split Algorithm 33
5. Intersection of Two Linked Lists 34
6. Questions for the Final Report: 34

3
Module 3: Stack Data Structure 35
Objectives: 35
Discussion: 35
Terminology: 36
Stack Implementation 37
Laboratory Familiarization Exercises 39
Laboratory Problems/Activities 41
Questions for the Lab Report 45
References: 46
Appendix: 46
Module 4: Queue 50
Objectives: 50
Discussion: 50
Laboratory Familiarization Exercises 52
Program No. 1 52
Program No. 2 53
Program No. 3 54
Program No. 4 56
Program No. 5 57
Laboratory Activities 58
References: 62
Appendix: 62
Module 5: Tree Data Structures 64
Objectives: 64
Discussion: 64
Tree Terminologies 64
Binary Tree 66
Operations on Binary Tree 67
Binary Search Tree 69
Heaps 71
AVL Tree 71
Laboratory Familiarization Exercises 72
Laboratory Problems/Activities 76
Module 6: Graph Data Structure 79
Objectives: 79
Discussion: 79

4
 Laboratory Familiarization Exercises 88
Program No. 1 88
Laboratory Problems/Activities 90
Module 7: Sorting, Searching Algorithms, and Advanced Problems 96
Objectives: 96
Discussion: 96
Selection Sort 97
Insertion Sort 97
Bubble Sort 98
Merge Sort 99
Laboratory Familiarization Exercises 101
Program No. 1 101
Program No. 2 103
Program No. 3 105
Laboratory Problems/Activities 106
APPENDIX A. Laboratory Report Format 109

5
LBYCPA2 - Data Structures and Algorithms Laboratory
AY 2025-26, Term 1

Module 1: Introduction to Data Structures and Algorithms

I. Objectives
1. To define and familiarize algorithms and write them with pseudocode and

conventional notation.

2. To introduce and describe algorithm analysis, operation counting, and big-Θ

notation.

3. To define basic data structures and algorithms terminologies, i.e. Abstract Data Type

(ADT), time and space complexity, and so on.

4. To familiarize and illustrate or visualize analogies of common data structures - static

array, dynamic array, singly-linked list, doubly-linked list, stack, queue, binary search

tree, and hash table.

5. To research the time complexities of common data structures - static array, dynamic

array, singly-linked list, doubly-linked list, stack, queue, binary search tree, and hash

table.

II. Materials
1. IntelliJ IDEA Ultimate - Educational License (Free)

2. Java Development Kit (JDK 21 or higher)

3. DrawIO (https://app.diagrams.net)

III. Pre-lab Discussion

Data Structures and Algorithms

6
 An algorithm is any well-defined computational procedure that takes some value, or

set of values, as input and produces some value, or set of values, as output. It includes a

sequence of computational steps that transform the input into the output. It can also be

viewed as a tool for solving a well-specified computational problem. The statement of the

problem specifies in general terms the desired input/output relationship. The algorithm

describes a specific computational procedure for achieving that input/output relationship.

Thus, an algorithm can be defined as a finite sequence of precise instructions for performing

a computation or for solving a problem.

“Bad programmers worry about the code.

Good programmers worry about data structures and their relationships.”

- Linus Torvalds, creator of Linux OS

A data structure is a way to store and organize data in order to facilitate access and

modifications. It is a collection of data values and the relationships among them, including

the operations that can be applied to the data. No single data structure works well for all

purposes, and thus, it is important to know the strengths and limitations of several of them

since different data structures are suited for different problems. Some common data

structures include Arrays (Static and Dynamic), Linked List, Stack, Queue, Tree, Graph,

Heap, Hash Table, and so on. The functional definition of a data structure is referred to as

an Abstract Data Type (ADT) which is independent of implementation left on developers to

decide which technology is proper for their project needs. For instance, Stack ADT is a

structure which supports operations such as push and pop. It can be implemented in a

number of ways, for example using an array or using a linked list.

Pseudocode and Conventions

Pseudocode is an informal high-level description of the computational procedure or

algorithm. The conventions of pseudocode writing utilized in this course involves the

following: (Erciyes, 2018)

7
 ● Every algorithm starts with the declaration of its input and the output produced.

● The lines of the algorithm are numbered for reference.

● Indentations to show blocks which are executed within control structures.

● A procedure that is used from the main body of the algorithm is shown explicitly.

Each line of an algorithm is a statement which commonly evaluates an expression or

performs a specific function such as calling a procedure. An expression consists of constants,

variables, and operators. Declaration of a variable is performed as shown in the following

examples:

boolean visited ← false

Here a Boolean variable visited is declared and initialized to false value.

setofint vertices ← {Ø}

A set of vertices which will contain integer values is declared and initialized as empty.

General Conventions:

Arithmetic and logical operators

8
Control structures are used to alter the flow of execution. Selection and repetition are two

main modes of control as described below. Selecting one of few alternative flows is

commonly performed by the if-then-else construction. The Boolean expression after the if

statement is evaluated and the branch after then is taken if this expression yields a true

value. We can specify an else block to specify the alternative flow when the expression yields

a false value. An example is depicted in Algorithm A.1 where we want to test which of the

given two integers a and b is greater than the other or whether they are equal to each other.

We see line 7 is executed in this example.

We can select a specific flow of execution from a number of alternative flows again by the

evaluation of a number of expressions using the case-of structure. A simple calculator that

can perform addition, subtraction, multiplication, and division is shown in Algorithm A.2.

9
We use the loop constructs for, while, and repeat..until to implement a statement for a

number of times. The for-do loop is commonly used when the number of iterations is known

beforehand. The example shown in Algorithm A.3 finds the sum of the elements of a matrix

with integer elements.

When we are dealing with sets and do not know the size of the set, the for all loop can be

conveniently used. Commonly, we arbitrarily select an element of the set and perform an

operation on this element as shown in Algorithm A.4 where we simply output each element

of set S which consists of integers.

10
There are cases when we want to enter a loop based on a condition. The while loop can be

used for such implementations, and this type of loop may be entered 0 or more times based

on the evaluation of a Boolean expression as shown in Algorithm A.5 where the sum of

numbers entered is calculated until 99 is entered. Note that 99 may be entered as the first

input causing no execution of the block inside the loop.

Our last loop structure we use in the algorithms is the Repeat .. Until loop where the decision

to execute the loop is made after the loop is run. This type of loop is used when we know the

loop is to run at least once as shown in Algorithm A.6, where we implement the above

example of adding numbers entered. Note that we do not need the input statement before

the loop this time since we know the loop will execute at least once.

Algorithm Analysis and Big-Θ Notation

An analysis of the time required to solve a problem of a particular size involves the time

complexity of the algorithm. An analysis of the computer memory required involves the

space complexity of the algorithm. Considerations of time and space complexity of an

11
algorithm are essential when algorithms are implemented. It is important to know whether

an algorithm will produce an answer in a microsecond, a minute, or a billion years. Likewise,

the required memory must be available to solve a problem, so that space complexity must

be taken into account.

The time complexity of an algorithm can be expressed in terms of the number of operations

used by the algorithm when the input has a particular size. The operations used to measure

time complexity can be the comparison of integers, the addition of integers, the

multiplication of integers, the division of integers, or any other basic operation. In other

words, time complexity is usually described in terms of the number of operations required

instead of actual computer time because of the difference in time needed for different

computers to perform basic operations.

Fig. 1 Amount of input, n, vs. no. of operations Growth of Functions

12
Fig. 1 illustrates the various approximations of no. of operations growth with respect to the

increase in input. For example, an algorithm that finds the largest of the first 100 terms of a list of

n elements to the sequence of the first 100 terms, where n is an integer with n ≥ 100, has constant

complexity because it uses 99 comparisons no matter what n is. The linear search algorithm has

linear (worst-case) complexity and the binary search algorithm has logarithmic (worst-case)

complexity. Many important algorithms have n log n, or linearithmic (worst-case) complexity,

e.g. merge sort. Trying to break a password by testing every possible combination (Brute

Force) has exponential complexity, while finding all permutations of a given string has

factorial complexity.

Operation Counting Rules

1. Declarations with no initialization have no (zero) operation count.

2. Delimiters (such as { and }) have no (zero) operation count.

3. Function headings such as main() have no operation count.

4. Each operator (whether arithmetic, logical, relational) has a constant running time, ci

13
 5. The operation count of an expression depends on the number of operators

(arithmetic, logical, relational) present, ci

6. The operation count of an assignment statement is constant, ci.

7. Each function call has an operation count of constant, ci.

8. The overall operation count of the if-else statement is the operation count of the

<condition> plus the maximum between the operation counts of <S1> and <S2>. The

keyword else does not consume any operation count.

if (condition)

<S1>;

else

<S2>;

9. The total operation count of a statement inside a group of nested loops is the

operation count of the statement multiplied by the product of all the sizes of all the

loops.

10. The running time of the algorithm is the sum of running times for each statement

executed; a statement that takes ci steps to execute and executes n times will

contribute cin to the total running time.

Example: Given the following Insertion sort algorithm, give the worst-case running time, or

the longest running time for any input of size n.

14
Analysis:

Assuming worst-case, that is, when the input array is in reverse sorted order.

Thus, the worst-case running time of insertion sort is a quadratic function, Θ(n²).

Terminology

● Abstract Data Type (ADT) - a functional definition of a data structure independent

of implementation.

15
 ● Algorithm - a finite sequence of precise instructions for performing a computation

or for solving a problem.

● Array - is a data structure that is designed to store a group of objects. It can hold

primitives as well as references. It is the most efficient data structure for storing and

accessing a sequence of objects. It is a random access data structure, where each

element can be accessed directly and in constant time.

● Graph - is a nonlinear data structure which consists of a nonempty set of vertices V

and a set of edges (or arcs) E. Each edge is associated with a pair of vertices. A graph

data structure may also associate to each edge some edge value, such as a symbolic

label or a numeric attribute.

● Linked list - is a dynamic data structure where each element (node) is a separate

object consisting of two items - the data and a reference to the next node. It is a

sequential access data structure, where each element can be accessed only in

particular order.

● Time Complexity - refers to the amount of time an algorithm requires to run, as a

function of the amount of input, n, ignoring constant terms and factors.

● Space Complexity - refers to the amount of space, or memory required by an

algorithm to solve a given problem.

● Stack - is a data structure where objects are inserted and removed according to the

last-in first-out (LIFO) principle. In the pushdown stacks only two operations are

allowed: push the item into the stack, and pop the item out of the stack. A stack is a

limited access data structure - elements can be added and removed from the stack

only at the top.

● Tree - is a nonlinear (hierarchical) data structure, compared to arrays, linked lists,

stacks and queues which are linear data structures. A tree can be empty with no

nodes or a tree is a structure consisting of one node called the root and zero or one

or more subtrees. A tree has the following general properties: (a) One node is

distinguished as a root; (b) Every node (exclude a root) is connected by a directed

edge from exactly one other node; A direction is: parent -> children

16
 ● Queue - is a data structure where objects are inserted and removed according to the

first-in first-out (FIFO) principle. In the queue only two operations are allowed -

enqueue and dequeue. Enqueue means to insert an item into the back of the queue,

dequeue means removing the front item.

IV. Laboratory Activities

1. Time to Solve for a Given Data

Write a Java program that will print the following table, shown below. For each function f(n)

and time t in the following table, determine the largest size n of a problem that can be solved

in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

Note:

1. Use ^ symbol to signify exponent in the printed table, but note however, that ^ is not

exponentiation in C++ or Java expressions

2. lg n is binary logarithm or log base 2 of a number n

3. Use sqrt() for the square root symbol (√)

17
2. Maximum Element Search Algorithm

Using the pseudocode conventions discussed above, (a) design an algorithm that finds the

maximum element (output) from an input array of n integers. (b) analyze your algorithm by

counting the number of operations using the operation counting guidelines discussed

above. (c) Determine the Big-Θ time complexity of your algorithm. (d) write a Java program

with your algorithm as a function. The input array must consist of 100 integers initialized

randomly using Random.nextInt() function (within value 1000 range). Print both the input

array and the output of the algorithm.

Random.nextInt Documentation: Random (Java Platform SE 8 ) (oracle.com)

3. Worst-Case Time Complexity Table

Research on the basic data structures, its common operations, and time complexity. Write a

Java program summarizing the worst-case complexity of each basic operation as shown

below. Note: Access or indexing refers to the operation of accessing a single element. Search

operation involves finding a certain element within the data structure. Insertion or Insert

operation refers to inserting a single element to the data structure. Deletion or delete

operation involves removing an element to the data structure.

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

Worst-Case Time Complexity Table

by: FirstName Surname, LBYCPA2-Section

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

Data Structure Access Search Insert Delete

18
 Static Array - -

Dynamic Array

Singly-Linked List

Doubly-Linked List

Stack

Queue

Binary Search
Tree

Hash Table

Using your prior knowledge of Static Arrays, explain the time complexity research results for

the Access, Search, Insert, and Delete operations.

4. Comparing Time Performances

Compare the time performance of a Matrix Multiplication algorithm with the Fibonacci

algorithm. Create randomized matrices for matrix multiplication, and perform the

multiplication for size NxN. For the Fibonacci algorithm, get the Nth value from N-1th and N-

2th value, until it reaches f(0) and f(1). Identify the time complexity of the algorithms by

plotting the trend of the graph, and performing operation count.

10 x 10 20 x 20 30 x 30 40 x 40 50 x 50 60 x 60 70 x 70
Matrix Mult

f(10) f(20) f(30) f(40) f(50) f(60) f(70)

19