COLLEGE OF COMPUTER SCIENCE AND
INFORMATION TECHNOLOGY
JAZAN UNIVERSITY
ALGORITHMS & DATA STRUCTURES-1 (COMP 221)
LAB MANUAL
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
1
INDEX
Sl. Page
Contents
No. No.
1 Program to demonstrate primitive data types in Java. 3
2 Program to demonstrate the concept of Generics in Java. 4
Program demonstrating the use of arrays in Java.(Sum of
3 5
array elements)
4 Program to search an element from the given list of 6
elements using Linear Search technique.
Program to search a key element in the given list of
5 7
elements using Binary Search technique.
Program to sort the given list of elements using Selection
6 9
sort technique.
Program to sort the given list of elements using Bubble
7 10
sort technique.
8 Program to implement Singly linked list. 11
Program to demonstrate an Array based implementation of
9 14
Stack and its operations.
Program to demonstrate an Array based implementation of
10 16
Queue and its operations.
Program to demonstrate the inorder, preorder and postorder
11 19
traversal of a binary tree.
Program to check whether the given tree is a Binary Search
12 21
Tree or not.
13 Program to implement Heap. 23
14 Program to implement Depth First Search traversal of Graph. 27
Program to implement Breadth First Search traversal of
15 29
Graph.
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
2
1. Program to demonstrate primitive data types in Java.
public class PrimitiveDemo {
public static void main(String[] args)
{
boolean flag = true;
char grade = 'A';
byte b = 12;
short s = 24;
int i, j, k = 257; // three variables declared; only k initialized
long l = 890L; // note the use of "L" here
float pi = 3.1416F; // note the use of "F" here
double e = 2.71828, a = 6.022e23; // both variables are initialized
System.out.println("flag = " + flag);
System.out.println("grade = " + grade);
System.out.println("s = " + s);
System.out.println("k = " + k);
System.out.println("l = " + l);
System.out.println("pi = " + pi);
System.out.println("e = " + e);
System.out.println("a = " + a);
}
}
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
3
2. Program to demonstrate the concept of Generics in Java.
class Test<T>
{
// An object of type T is declared
T obj;
Test(T obj) { this.obj = obj; } // constructor
public T getObject() { return this.obj; }
}
public class Generics
{
public static void main (String[] args)
{
// instance of Integer type
Test <Integer> i = new Test<Integer>(15);
System.out.println(i.getObject());
// instance of String type
Test <String> s = new Test<String>("Jazan University");
System.out.println(s.getObject());
}
}
Output:
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
4
3. Program demonstrating the use of arrays in Java.(Sum of array
elements)
public class ArraySum {
public static void main(String[] args) {
int[] array={1,2,3,4}; //Declaring and initialization
System.out.println("Array Sum:"+sum(array));
}
public static int sum(int[] a)
{
int total = 0;
for (int j=0; j < a.length; j++) // note the use of length
total += a[j];
return total;
}
}
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
5
4. Program to search an element from the given list of elements
using Linear Search technique.
public class LSearch {
public static int search(int a[], int x)
{
int n = a.length;
for(int i = 0; i < n; i++)
{
if(a[i] == x)
return i;
}
return -1;
}
public static void main(String args[])
{
int a[] = { 2, 3, 4, 10, 40 };
int key = 10;
int result = search(a, key);
if(result == -1)
System.out.print("Element not found");
else
System.out.print("Element found at position " + result);
}
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
6
5. Program to search a key element in the given list of elements
using Binary Search technique.
public class BSearch {
public static int bsearch(int a[],int x)
int n=a.length;
int first=0; int last=n-1;
while(first<=last)
int location=(first+last)/2;
if(a[location]==x)
return location;
else
if(a[location]<x)
first=location+1;
else
last=location-1;
return -1;
public static void main(String args[])
int a[] = { 2, 3, 4, 10, 40 };
int key = 10;
int result = bsearch(a, key);
if(result == -1)
System.out.print("Element not found");
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
7
else
System.out.print("Element found at position " + result); //index
position starts at 0
Output:
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
8
6. Program to sort the given list of elements using Selection
sort technique.
public class SSort {
public static void main(String args[]){
int a[] = {56, 44, 35, 5, 22, 10, 89};
int n = a.length;
for (int i = 0; i < n-1; i++)
// Find the minimum element in unsorted array
int minpos = i;
for (int j = i+1; j < n; j++)
if (a[j] < a[minpos])
minpos = j;
// Swap the found minimum element with the first element
int temp = a[minpos];
a[minpos] = a[i];
a[i] = temp;
System.out.println("Sorted list is ");
for (int i=0; i<n; ++i)
System.out.print(a[i] + " ");
Output:
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
9
7. Program to sort the given list of elements using Bubble sort
technique.
public class BSort {
public static void main(String args[])
int a[] = {56, 44, 35, 5, 22, 10, 89};
int n = a.length;
for (int i = 0; i < n-1; i++)
for (int j = 0; j < n-i-1; j++)
if (a[j] > a[j+1])
// swap arr[j+1] and arr[i]
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
System.out.println("Sorted list is ");
for (int i=0; i<n; ++i)
System.out.print(a[i] + " ");
Output:
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
10
8. Program to implement Singly linked list.
public class SinglyLinkedList<E> {
private static class Node<E> {
private E element; // reference to the element stored at this node
private Node<E> next; // reference to the next node in the list
public Node(E e, Node<E> n) {
element = e;
next = n;
public E getElement( ) { return element; }
public Node<E> getNext( ) { return next; }
public void setNext(Node<E> n) { next = n; }
// instance variables of the SinglyLinkedList
private Node<E> head = null; // head node of the list (null if empty)
private Node<E> tail = null; // last node of the list (null if empty)
private int size = 0; // number of nodes in the list
public SinglyLinkedList( ) { } // constructs an initially empty list
// access methods
public int size( ) { return size; }
public boolean isEmpty( ) { return size == 0; }
public E first( ) { //returns (but does not remove) the first element
if (isEmpty( )) return null;
return head.getElement( );
public E last( ) { // returns (but does not remove) the last element
if (isEmpty( )) return null;
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
11
return tail.getElement( );
// update methods
public void addFirst(E e) { // adds element e to the front of the list
head = new Node<>(e, head); // create and link a new node
if (size == 0)
tail = head; // special case: new node becomes tail also
size++;
public void addLast(E e) { // adds element e to the end of the list
Node<E> newest = new Node<>(e, null); //node will eventually be thetail
if (isEmpty( ))
head = newest; // special case: previously empty list
else
tail.setNext(newest); // new node after existing tail
tail = newest; // new node becomes the tail
size++;
public E removeFirst( ) { // removes and returns the first element
if (isEmpty( )) return null; // nothing to remove
E answer = head.getElement( );
head = head.getNext( ); // will become null if list had only one node
size--;
if (size == 0)
tail = null; // special case as list is now empty
return answer;
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
12
}
public void display(){
Node<E> cur= null;
cur=head;
System.out.println("The contents of the list are:");
for(int i=1;i<=size();i++){
System.out.print(cur.element+" ");
cur=cur.getNext();
public static void main(String[] args) {
SinglyLinkedList <Integer> list1= new SinglyLinkedList <Integer>();
list1.addFirst(10);
list1.addFirst(20);
list1.addFirst(30);
list1.addFirst(40);
list1.addLast(50);
list1.removeFirst();
list1.display();
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
13
9. Program to demonstrate an Array based implementation of Stack
and its operations.
public class ArrayStack<T> {
protected final int DEFCAP = 5; // default capacity
protected T[] stack;
protected int topIndex=-1;
public ArrayStack() {
stack = ( T[ ] ) new Object[DEFCAP];
public boolean isEmpty() // Returns true if stack is empty,
if(topIndex==-1)
return true;
else
return false;
public boolean isFull() // Returns true if stack is full
if(topIndex==(stack.length-1))
return true;
else
return false;
public void push(T element)
if(!isFull())
topIndex++;
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
14
stack[topIndex]=element;
else
System.out.println("Push attempted on a full stack");
public void pop()
{ if(!isEmpty())
{ stack[topIndex]=null;
topIndex--;
else
System.out.println("Pop attempted on an empty stack");
public void display(){
System.out.println("Stack Contents are:");
for(int i=0;i<=topIndex;i++)
System.out.println(stack[i]+" ");
public static void main(String args[]){
ArrayStack<Integer> s=new ArrayStack<Integer>();
s.pop();
s.push(40);
s.push(50);
s.pop();
s.display();
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
15
10. Program to demonstrate an Array based implementation of Queue
and its operations.
public class ArrayQueue<T>
protected final int DEFCAP = 5; // default capacity
protected T[] queue; //arrays that holds the queue elements
protected int count=0; //number of elements in the queue
protected int front=0,rear=0;
public ArrayQueue(){
queue = ( T[ ] ) new Object[DEFCAP];
public boolean isEmpty() // Returns true if queue is empty
return(count==0);
public boolean isFull() // Returns true if queue is full
return(count==queue.length);
public void enqueue(T element)
if(isFull())
System.out.println("Enqueue attempted on full queue");
else
queue[rear]=element;
rear=(rear+1)%queue.length;
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
16
count++;
}//end of else
} //end of enqueue
public T dequeue(){
if(isEmpty()){
System.out.println("Dequeue attempted on empty queue");
return null;
else
T delElement = queue[front];
queue[front]=null;
front=(front+1)%queue.length;
count--;
return delElement;
public void display(){
System.out.print("Queue Contents are:");
int i=front;
do{
System.out.print(queue[i]+" ");
i=(i+1)%DEFCAP;
while(i!=rear);
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
17
public static void main(String args[])
ArrayQueue<Integer> q=new ArrayQueue<Integer>();
q.dequeue();
q.enqueue(5);
q.enqueue(6);
q.enqueue(7);
q.dequeue();
q.enqueue(8);
q.enqueue(9);
q.enqueue(10);
q.enqueue(11);
q.display();
Output:
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
18
11. Program to demonstrate the inorder, preorder and postorder
traversal of a binary tree.
class Node{
int data;
Node left,right;
Node(int n){
data=n;
left=right=null;
public class BinaryTree {
Node root;
//Inorder traversal
public void Inorder(Node node){
if (node != null) {
Inorder(node.left);
System.out.print(" " + node.data);
Inorder(node.right);
//Preorder traversal
public void Preorder(Node node){
if (node != null) {
System.out.print(" " + node.data);
Preorder(node.left);
Preorder(node.right);
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
19
//Postorder traversal
public void Postorder(Node node){
if (node != null) {
Postorder(node.left);
Postorder(node.right);
System.out.print(" " + node.data);
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
// create nodes of the tree
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
System.out.print("\nInorder traversal of Binary Tree: ");
tree.Inorder(tree.root);
System.out.print("\nPreorder traversal of Binary Tree: ");
tree.Preorder(tree.root);
System.out.print("\nPostorder traversal of Binary Tree: ");
tree.Postorder(tree.root);
Output:
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
20
12. Program to check whether the given tree is a Binary Search
Tree or not.
class Node{
int data;
Node left,right;
Node(int n)
data=n;
left=right=null;
public class BinaryTree {
Node root;
boolean isBST() {
return isBSTUtil(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
// Returns true if the given tree is a BST and its values are >= min
and <= max.
boolean isBSTUtil(Node node, int min, int max)
// an empty tree is BST
if (node == null) return true;
// false if this node violates the min/max constraints
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
21
if (node.data < min || node.data > max) return false;
// Allow only distinct values
return (isBSTUtil(node.left, min, node.data-1) &&
isBSTUtil(node.right, node.data+1, max));
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
// create nodes of the tree
tree.root = new Node(7);
tree.root.left = new Node(4);
tree.root.right = new Node(9);
tree.root.left.left = new Node(2);
tree.root.left.right = new Node(5);
if (tree.isBST())
System.out.println("Given tree is a Binary Search Tree");
else
System.out.println("Given tree is not a Binary Search Tree");
Output:
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
22
13. Program to implement Heap.
import java.util.*;
class Heap
private int[] heapArray;
/** size of array **/
private int maxSize;
/** number of nodes in array **/
private int heapSize;
/** Constructor **/
public Heap(int mx)
maxSize = mx;
heapSize = 0;
heapArray = new int[maxSize];
/** Function to insert element **/
public boolean insert(int ele)
if (heapSize + 1 == maxSize)
return false;
heapArray[++heapSize] = ele;
int pos = heapSize;
while (pos != 1 && ele > heapArray[pos/2])
heapArray[pos] = heapArray[pos/2];
pos /=2;
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
23
}
heapArray[pos] = ele;
return true;
/** function to remove element **/
public int remove()
int parent, child;
int item, temp;
if (heapSize==0)
System.out.println("Heap empty!");
return 0;
else
item = heapArray[1];
temp = heapArray[heapSize--];
parent = 1;
child = 2;
while (child <= heapSize)
if (child < heapSize && heapArray[child] < heapArray[child +
1])
child++;
if (temp >= heapArray[child])
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
24
break;
heapArray[parent] = heapArray[child];
parent = child;
child *= 2;
heapArray[parent] = temp;
return item;
/** Function to print values **/
public void displayHeap()
/* Array format */
System.out.print("\nHeap array: ");
for(int i = 1; i <= heapSize; i++)
System.out.print(heapArray[i] +" ");
System.out.println("\n");
/** Class HeapTest **/
public class HeapTest
public static void main(String[] args)
Heap h = new Heap(10); //maxSize 10
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
25
h.remove();
h.insert(7);
h.insert(3);
h.insert(2);
h.insert(5);
h.insert(8);
h.displayHeap();
h.remove(); //delete element with maxKey
h.displayHeap();
Output:
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
26
14. Program to implement Depth First Search traversal of Graph.
import java.util.Stack;
import java.util.*;
public class DFSTraversal{
static void DFS(int[][] matrix, int source){
boolean[] visited = new boolean[matrix.length];
visited[source-1] = true;
Stack<Integer> stack = new Stack<>();
stack.push(source);
int i,x;
System.out.println("The depth first search order is");
System.out.println(source);
while(!stack.isEmpty()){
x = stack.pop();
for(i=0; i<matrix.length; i++){
if(matrix[x-1][i] == 1 && visited[i] == false){
stack.push(x);
visited[i] = true;
System.out.println(i+1);
x = i+1;
i = -1;
public static void main(String[] args) {
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
27
Scanner in = new Scanner(System.in);
System.out.println("Enter the number of vertices in the graph");
int vertices = in.nextInt();
int[][] matrix = new int[vertices][vertices];
System.out.println("Enter the adjacency matrix");
int i,j;
for(i=0; i<vertices; i++){
for(j=0; j<vertices; j++){
matrix[i][j] = in.nextInt();
System.out.println("Enter the source vertex");
int source = in.nextInt();
DFS(matrix,source);
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
28
15. Program to implement Breadth First Search traversal of Graph.
import java.util.LinkedList;
import java.util.Queue;
import java.util.*;
public class BFSTraversal {
// Function to perform breadth first search
static void BFS(int[][] matrix, int source){
boolean[] visited = new boolean[matrix.length];
visited[source-1] = true;
Queue<Integer> queue = new LinkedList<>();
queue.add(source);
System.out.println("The breadth first traversal order is");
while(!queue.isEmpty()){
System.out.println(queue.peek());
int x = queue.poll();
int i;
for(i=0; i<matrix.length;i++){
if(matrix[x-1][i] == 1 && visited[i] == false){
queue.add(i+1);
visited[i] = true;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
29
System.out.println("Enter the number of vertices in the graph");
int vertices = in.nextInt();
int[][] matrix = new int[vertices][vertices];
System.out.println("Enter the adjacency matrix");
int i,j;
for(i=0; i<vertices; i++){
for(j=0; j<vertices; j++){
matrix[i][j] = in.nextInt();
System.out.println("Enter the source vertex");
int source = in.nextInt();
BFS(matrix,source);
Output:
Lab Manual – Algorithms & Data Structures-1 (COMP 221)
30
