Data Structures Lab - Version 1.3 - Revision Summer 2023
Data Structures Lab - Version 1.3 - Revision Summer 2023
Data Structures Lab - Version 1.3 - Revision Summer 2023
PREPARED BY
Lab manual is prepared by Mr. Aqib Rehman under the supervision of Head of Department, Dr.
Muhammad Shaheen.
GENERAL INSTRUCTIONS
a. Students are required to maintain the lab manual with them till the end of the semester.
b. All readings, answers to questions and illustrations must be solved on the place provided. If more
space is required then additional sheets may be attached.
c. It is the responsibility of the student to have the manual graded before deadlines as given by the
instructor.
d. Loss of manual will result in re-submission of the complete manual.
e. Students are required to go through the experiment before coming to the lab session.
f. Students must bring the manual in each lab.
g. Keep the manual neat clean and presentable.
h. Plagiarism is strictly forbidden. No credit will be given if a lab session is plagiarised and no re-
submission will be entertained.
i. Marks will be deducted for late submission.
j. You need to submit the report even if you have demonstrated the exercises to the lab instructor or
shown them the lab report during the lab session.
VERSION HISTORY
Date Update By Details
Fall 2019 Version 1.0
Sep 2019 Aqib Rehman Version 1.1. Designed in Java language
Sep 2019 Aqib Rehman Version 1.2. Formating, Experiments are
added, Exercises are added
Fall 2019 Ms. Aania Majeed Version 1.3. Complex Problems added
Dr. Muhammad Asif
4 Array based 10
Queues
implementation
5 Circular and Priority Queues 10
11 Balanced Trees 10
Grand Total
LAB TASK 1 – Overview of Java Language and Measuring Execution Time of Java Program...5
LAB TASK 3 – Array based Stack implementation......................................................................23
LAB TASK 4 – Array based Queue implementation....................................................................31
LAB TASK 5 – Circular Queue and Implementation of Deque using circular array...................40
LAB TASK 6 – Singly Link List...................................................................................................52
LAB TASK 7 – Doubly Link List.................................................................................................63
LAB TASK 8 – SEMESTER PROJECT GUIDELINES..............................................................74
LAB TASK 9 – Binary Trees, Binary Tree Traversals and Level Order Traversal......................77
LAB TASK 10 – Binary Search Trees..........................................................................................90
LAB TASK 11 – Balanced Trees..................................................................................................96
LAB TASK 13 – Dictionary using Hashing and HashTable.......................................................104
LAB TASK 14 – Heap................................................................................................................113
LAB TASK 15 – Graphs using Adjacency list and Adjacency Matrix and Memory
Management118 LAB TASK 16 – SEMESTER PROJECT PRESENTATION........................128
Overview of Java
This section introduces the students to elementary Java. Java is a vast computer language and
programming environment, it is not possible to touch upon all Java-related issues. This section
introduces only those aspects of Java that are necessary for understanding the Java code offered
in this book. Java program examples presented in this section give you to implement data
structures.
What is an Algorithm?
An algorithm is a technique for solving a problem or performing an analysis. Algorithms act as
an accurate list of instructions that execute specified actions step by step in either hardware or
software-based practices. Algorithms are widely used throughout all regions of IT.
import java.lang.Math;
import java.util.Scanner;
class QuadraticEquation
{
double a, b, c; // coefficients
QuadraticEquation( double a, double b, double
c)
c); qe.roots();
}
}
Output:
7 Data Structure and Algorithms Lab Manual
a=0
b=4
c=1
One root = -0.25
a=1
b=4
c=4
Two roots are equal: -2.0
a=1
b=4
c=8
There are no real solutions
a=1
b=4
c=3
Prime numbers
A prime number is a positive integer that is exactly divisible only by 1 and itself. The first few
prime numbers are:
2 3 5 7 11 13 17 23 29 31 37…
Following up these suggestions, we know that apart from 2, we do not need to examine any of the
even numbers, and only first half of the numbers is enough for testing prime. That is, we can test for
mod operation with numbers, from 3 to n/2. Hence, the following set of numbers is sufficient to test
13 for prime.
3 4 5 6
import java.io.*;
class PrimeNumber
{
public void primes(int n)
{
int k, m;
System.out.print("Prime numbers up to " + n + ": 2 3");
for(m=3; m <= n; m = m+2)
{
boolean isPrime = false;
for(k=2; k <= m/2; k++)
{
if(m % k == 0) { isPrime = false; break;
} else isPrime = true;
}
if(isPrime) System.out.print(" " + m);
}
}
}
////////////////////////// PrimeNumberDemo.java /////////////////
class PrimeNumberDemo
{
public static void main(String[] args) throws IOException
{ PrimeNumber pn = new PrimeNumber();
BufferedReader kb = new
BufferedReader(new InputStreamReader(System.in));
System.out.print("Enter n: ");
int n = Integer.parseInt(kb.readLine());
pn.primes(n);
}
}
Output:
Enter n: 50
Prime numbers up to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Palindrome
“MADAM” is a palindrome.
A string is an array of characters. For example, the string “MADAM” is stored as follows: [0] [1] [2]
[3] [4]
M A D A M
In this case, "MADAM" is a string literal - a series of characters that is enclosed in double quotes.
The String class provides the method length(), which returns as an int value the number of characters
in the String object. The method of the String class
char charAt(int n)
returns the nth character in a string (where n must be less than string length);
If the first character is equal to the last character of the string, second character is equal to the second
one from the last character of the string, and so on, then the string is a palindrome.
Program 4: Palindrome
class Palindrome
{
public boolean isPalindrome(String str)
{
System.out.print("Given string: " + str);
int n = str.length();
boolean flag =
true;
for( int i=0; i < n/2; i++ )
if( str.charAt(i) != str.charAt(n-i-1) ) flag = false; return flag;
}
}
////////////////////////// PalindromeDemo.java ////////////////////
class PalindromeDemo
{
public static void main(String[] args)
{
Output:
Given string: MADAM is a palindrome.
class TimeTest1 {
public static void main(String[] args) {
long startTime =
long stopTime =
System.currentTimeMillis(); long
elapsedTime = stopTime - startTime;
System.out.println(elapsedTime);
}
}
Difference Between Linear Search and Binary Search
The major difference between linear search and binary search is that binary search takes less time to
search an element from the sorted list of elements. So it is inferred that efficiency of binary search
method is greater than linear search. Another difference between the two is that there is a prerequisite
for the binary search, i.e., the elements must be sorted while in linear search there is no such
prerequisite. Although both the searching methods use different techniques which are discussed below.
1. Linear search is iterative in nature and uses sequential approach. On the other hand, Binary
search implements divide and conquer approach.
2. The time complexity of linear search is O(N) while binary search has O(log2N).
3. The best case time in linear search is for the first element i.e., O(1). As against, in binary
search, it is for the middle element, i.e., O(1).
4. In the linear search, worst case for searching an element is N number of comparison. In
contrast, it is log2N number of comparison for binary search.
5. Linear search can be implemented in an array as well as in linked list whereas binary search
can not be implemented directly on linked list.
6. As we know Binary search requires the sorted array that is reason It requires processing to
insert at its proper place to maintain a sorted list. On the contrary linear search does not require
sorted elements, so elements are easily inserted at the end of the list.
7. Linear search is easy to use, and there is no need for any ordered elements. On the other
hand, Binary search algorithm is however tricky, and elements are necessarily arranged in order.
Both linear and binary search algorithms can be useful depending on the application. When an array is
the data structure and elements are arranged in rted order, then binary search is preferred for
quick searching. If linked list is the data structure regardless how the elements are arranged, linear
search is adopted due to unavailability of direct implementation of binary search algorithm.
Exercise 1: (5)
Calculate the elapsed time of Linear search and Binary Search.
import java.util.Arrays;
import java.util.Date;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}
while (true) {
System.out.println("Menu:");
System.out.println("1. Addition");
System.out.println("2. Subtraction");
System.out.println("3. Exit");
System.out.print("Enter your choice: ");
switch (choice) {
case 1:
performAddition(scanner);
break;
case 2:
performSubtraction(scanner);
break;
case 3:
System.out.println("Exiting...");
return;
default:
System.out.println("Invalid choice. Please try again.");
}
}
}
Arrays in Java
An array is a group of like-typed variables that are referred to by a common name.Arrays in Java work
differently than they do in C/C++. Following are some important point about Java arrays.
In Java all arrays are dynamically allocated. (discussed below)
Since arrays are objects in Java, we can find their length using member length. This is different
from C/C++ where we find length using sizeof.
A Java array variable can also be declared like other variables with [] after the data type.
The variables in the array are ordered and each have an index beginning from 0.
Java array can be also be used as a static field, a local variable or a method parameter.
The size of an array must be specified by an int value and not long or short.
The direct superclass of an array type is Object.
Every array type implements the interfaces Cloneable and java.io.Serializable.
Array can contains primitives data types as well as objects of a class depending on the definition of
array. In case of primitives data types, the actual values are stored in contiguous memory locations. In
case of objects of a class, the actual objects are stored in heap segment.
type var-name[];
OR
type[] var-name;
An array declaration has two components: the type and the name. type declares the element type of the
array. The element type determines the data type of each element that comprises the array. Like array of
int type, we can also create an array of other primitive data types like char, float, double.etc or user
defined data type (objects of a class). Thus, the element type for the array d etermines what type of data
the array will hold.
16 Data Structure and Algorithms Lab Manual
Example:
// both are valid declarations
int intArray[];
or int[] intArray;
byte byteArray[];
short shortsArray[];
boolean booleanArray[];
long longArray[];
float floatArray[];
double doubleArray[];
char charArray[];
Although the above first declaration establishes the fact that intArray is an array variable, no array
actually exists. It simply tells to the compiler that this (intArray) variable will hold an array of the
integer type. To link intArray with an actual, physical array of integers, you must allocate one
using new and assign it to intArray.
Instantiating an Array in Java
When an array is declared, only a reference of array is created. To actually create or give memory to
array, you create an array like this:The general form of new as it applies to one-dimensional arrays
appears as follows:
var-name = new type [size];
Here, type specifies the type of data being allocated, size specifies the number of elements in the
array, and var-name is the name of array variable that is linked to the array. That is, to use new to
allocate an array, you must specify the type and number of elements to allocate.
Example:
int intArray[]; //declaring array
intArray = new int[20]; // allocating memory to array
OR
int[] intArray = new int[20]; // combining both statements in
one Note :
1. The elements in the array allocated by new will automatically be initialized to zero (for
numeric types), false (for boolean), or null (for reference types).
2. Obtaining an array is a two-step process. First, you must declare a variable of the
desired array type. Second, you must allocate the memory that will hold the array, using
new, andassign it to the array variable. Thus, in Java all arrays are dynamically allocated.
Array Literal
In a situation, where the size of the array and variables of array are already known, array literals can
be used.
int[] intArray = new int[]{ 1,2,3,4,5,6,7,8,9,10 };
// Declaring array literal
17 Data Structure and Algorithms Lab Manual
The length of this array determines the length of the created array.
There is no need to write the new int[] part in the latest versions of
Java Accessing Java Array Elements using for Loop
Each element in the array is accessed via its index. The index begins with 0 and ends at (total array
size)-1. All the elements of array can be accessed using Java for Loop.
class GFG
{
public static void main (String[] args)
{
// declares an Array of
integers. int[] arr;
//so on...
arr[2] = 30;
arr[3] = 40;
arr[4] = 50;
Example
2
class SortNames
{
public void sort(String[] a)
{
int i, pass, n =
a.length;
String tmp;
for( pass = 0; pass < n; pass++ )
{
for( i = 0; i < n-pass-1; i++ )
if( ((Comparable)a[i]).compareTo(a[i+1]) > 0)
{
tmp = a[i]; // Swap a[i], a[i+1]
a[i] = a[i+1];
a[i+1] = tmp;
}
}
}
}
////////////////////////// SortNamesDemo.java ////////////////////
class SortNamesDemo
{
public static void main(String[] args)
{
SortNames sn = new SortNames();
String[] names =
{"Ramu", "John", "Anu", "Priya", "Basha", "Prem"};
int i;
System.out.println("Unsorted names:");
Output:
Unsorted names:
Ramu
John
Anu
Priya
Basha
Prem
Sorted names:
Anu
Basha
John
Prem
Priya
Ramu
Multidimensional Arrays
Multidimensional arrays are arrays of arrays with each element of the array holding the reference of
other array. These are also known as Jagged Arrays. A multidimensional array is created by
appending one set of square brackets ([]) per dimension.
Examples:
int[][] intArray = new int[10][20]; //a 2D array or
matrix int[][][] intArray = new int[10][20][10]; //a 3D
array Implementation
class multiDimensional
{
public static void main(String args[])
{
// declaring and initializing 2D array
int arr[][] = { {2,7,9},{3,6,1},{7,4,2} };
// printing 2D array
for (int i=0; i< 3 ; i+
+)
{
for (int j=0; j < 3 ; j++)
System.out.print(arr[i][j] + " ");
System.out.println();
}
}
}
class Test
{
// Driver method
public static void main(String args[])
{
int arr[] = m1();
Exercises
Exercise 1: (2)
Write the program to store the students in the array having size 5. Consider the below data members
for student. Populate the array by user values.
// Java program to illustrate creating an array of
// objects
import java.util.Scanner;
class Student {
String name;
int age;
double gpa;
System.out.println("\nStudent Details:");
for (int i = 0; i < students.length; i++) {
System.out.println((i + 1) + ". " + students[i].name + ", Age: " + students[i].age + ", GPA: " + students[i].gpa);
}
}
}
class BinarySearchDemo
{
static Object[] a = { "AP", "KA", "MH", "MP", "OR", "TN", "UP", "WB"}; static
Object key = "UP";
public static void main(String args[])
{
if( binarySearch() )
System.out.println(key + " found in the list"); else System.out.println(key + " not found in the list");
}
static boolean binarySearch()
{
int c, mid, low = 0, high = a.length-1; while( low <= high)
{
mid = (low + high)/2;
c = ((Comparable)key).compareTo(a[mid]);
if( c < 0) high = mid-1; else if( c > 0) low = mid+1;
else return true;
}
return false;
}
}
Out put:
Working:
Main Method:
The main method is the entry point of the program. It calls the binarySearch method and prints the result to the console. If the
binarySearch method returns true, it means the key was found in the array, and the program prints "UP found in the list".
Otherwise, it prints "UP not found in the list".
25 Data Structure and Algorithms Lab Manual
Binary Search Method:
The binarySearch method performs the actual binary search on the array a. Here's how it works:
If key is less than the element at mid, update high to mid - 1 to search in the lower half of the range.
If key is greater than the element at mid, update low to mid + 1 to search in the upper half of the range.
If key is equal to the element at mid, return true to indicate that the key was found.
If the loop completes without finding the key, return false to indicate that the key was not found.
In this specific example, the key "UP" is present in the array, so the binarySearch method returns true, and the program prints "UP
found in the list"
import java.util.Arrays;
// String array
String[] stringArray = {"apple", "banana", "cherry", "date", "fig"};
Exercise 4: (1)
Write a Java program to sum values of an array.
// Iterate through the array and add each element to the sum
for (int i = 0; i < numbers.length; i++) {
sum += numbers[i];
}
Exercise 5: (1)
Write a Java program to calculate the average value of array elements.
// Iterate through the array and add each element to the sum
for (int i = 0; i < numbers.length; i++) {
sum += numbers[i];
}
// Array of integers
int[] numbers = {1789, 2035, 1899, 1456, 2013};
Stack ADT
A Stack is an Abstract Data Type (ADT) used for storing the elements. The elements are stored
based on the principle of LIFO (Last In, First Out). In stack insertion and deletion of elements
take place at the same end (Top). The last element inserted will be the first to be retrieved.
• This end is called Top
• The other end is called Bottom
obj pop(): Delete an item from the top of the stack and returns object obj; an error occurs if
the stack is empty.
Input: None; Output: Object.
obj peek(): Returns the top object obj on the stack , without removing it; an error occurs if
the stack is empty.
Input: None; Output: Object.
boolean isUnderflow(): When stack contains equal number of elements as per its capacity and no
more elements can be added, the status of stack is known as overflow.
Input: None; Output: boolean (true or false).
Type Object may be any type that can be stored in the stack. The actual type of the object
will be provided by the user.
Data3
Data2
Data1 Bottom
Stack Implementation:
boolean isEmpty()
{
return (top < 0);
}
Stack()
{
top = -1;
}
boolean push(int x)
{
}
}
int pop()
{
if (top < 0) {
System.out.println("Stack Underflow");
return 0;
}
else
{ int x = a[top--];
return x;
}
}
int peek()
{
if (top < 0) {
System.out.println("Stack Underflow");
return 0;
}
else
{ int x = a[top];
return x;
}
}
}
// Driver
code class
Main {
public static void main(String args[])
{
Stack s = new
Stack(); s.push(10);
s.push(20);
s.push(30);
System.out.println(s.pop() + " Popped from stack");
}
}
Balancing of symbols
Infix to Postfix /Prefix conversion
Redo-undo features at many places like editors, photoshop.
Forward and backward feature in web browsers
Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram
problem.
Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen
problem and sudoku solver
In Graph Algorithms like Topological Sorting and Strongly Connected Components
Exercices:
import java.util.Stack;
public class DecimalToBinary {
public static void decimalToBinary(int decimalNumber) {
if (decimalNumber < 0) {
System.out.println("Invalid input. Please enter a non-negative integer.");
return;
}
while (!stack.isEmpty()) {
System.out.print(stack.pop());
}
System.out.println();
}
Write a program to compare opening and closing brackets in expression. This program takes an
expression in the form of string and scan it character by character. Finally the output of the program is
the valid or invalid expression.
Algorithm: To do this comparison a stack ADT can be used to keep track of the scope
delimiters encountered while scanning the expression.
• Whenever a scope “opener” is encountered, it can be “pushed” onto a stack
• Whenever a scope “ender” is encountered, the stack is examined:
– If the stack is “empty”, there is no matching scope “opener” and the expression is invalid.
– If the stack is not empty, we pop the stack and check if the “popped” item corresponds to
the scope ender
– If match occurs, we continue scanning the expression
• When end of the expression string is reached, the stack must be empty, otherwise one or
more opened scopes have not been closed and the expression is invalid
Queue ADT
In queue, insertion and deletion happen at the opposite ends, so implementation is not as simple
as stack.
To implement a queue using array, create an array arr of size n and take two
variables front and rear both of which will be initialized to 0 which means the queue is currently
empty. Element rear is the index upto which the elements are stored in the array and front is the
index of the first element of the array.
Dequeue: Removal of an element from the queue. An element can only be deleted when there is
at least an element to delete i.e. rear > 0. Now, element at arr[front] can be deleted but all the
remaining elements have to shifted to the left by one position in order for the dequeue operation
to delete the second element from the left on another dequeue operation.
Front: Get the front element from the queue i.e. arr[front] if queue is not empty.
Display: Print all element of the queue. If the queue is non-empty, traverse
and print all the elements from index front to rear.
Queue Implementation:
Queue(int c)
{
front = rear =
0; capacity = c;
queue = new int[capacity];
}
// decrement
rear rear--;
}
return;
}
// Driver code
public static void main(String[] args)
{
// Create a queue of capacity
4 Queue q = new Queue(4);
// print Queue
elements
q.queueDisplay();
// print Queue
elements
q.queueDisplay();
34 Data Structure and Algorithms Lab Manual
// insert element in the
queue q.queueEnqueue(60);
q.queueDequeue();
q.queueDequeue();
System.out.printf("\n\nafter two node deletion\n\n");
// print Queue
elements
q.queueDisplay();
Output:
Queue is Empty
20 <-- 30 <-- 40 <-- 50 <--
Queue is full
20 <-- 30 <-- 40 <-- 50 <--
Applications of Queue
Queue is useful in CPU scheduling, Disk Scheduling. When multiple processes require
CPU at the same time, various CPU scheduling algorithms are used which are implemented
using Queue data structure.
When data is transferred asynchronously between two processes.Queue is used for
synchronization. Examples : IO Buffers, pipes, file IO, etc.
In print spooling, documents are loaded into a buffer and then the printer pulls them off
the buffer at its own rate. Spooling also lets you place a number of print jobs on a queue
instead ofwaiting for each one to finish before specifying the next one.
Breadth First search in a Graph .It is an algorithm for traversing or searching graph
data structures. It starts at some arbitrary node of a graph and explores the neighbor nodes
first, before moving to the next level neighbors.This Algorithm uses Queue data structure.
Exercise 1: (4)
Write a menu driven program to perform different operations with queue such a Enqueue ( ),
Dequeue( ) and DisplayQueue( ).
Circular Queue is a linear data structure in which the operations are performed based on FIFO
(First In First Out) principle and the last position is connected back to the first position to make a
circle. It is also called ‘Ring Buffer’.
In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we
can not insert the next element even if there is a space in front of queue.
queue.
enQueue(value) This function is used to insert an element into the circular queue. In a circular queue,
the new element is always inserted at Rear position.
Steps:
1. Check whether queue is Full – Check ((rear == SIZE-1 && front == 0) || (rear == front-1)).
2. If it is full then display Queue is full. If queue is not full then, check if (rear == SIZE – 1
&& front != 0) if it is true then set rear=0 and insert element.
deQueue() This function is used to delete an element from the circular queue. In a circular queue, the
element is always deleted from front position.
Steps:
3. Check whether queue is Empty means check (front==-1).
4. If it is empty then display Queue is empty. If queue is not empty then step 3
5. Check if (front==rear) if it is true then set front=rear= -1 else check if (front==size-1), if it
is true then set front=0 and return the element.
Operations on Deque:
Deque.
For implementing deque, we need to keep track of two indices, front and rear. We enqueue(push)
an item at the rear or the front end of qedue and dequeue(pop) an item from both rear and front end.
Working
1. Create an empty array ‘arr’ of size ‘n’
initialize front = -1 , rear = 0
Inserting First element in deque, at either front or rear will lead to the same result.
// A structure to represent a
Deque class Deque
{
static final int MAX = 100;
int arr[];
int front;
int rear;
int size;
// Inserts an element at
front void insertfront(int
key)
{
// check whether Deque if full or
not if (isFull())
{
System.out.println("Overflow");
return;
}
dq.deleterear();
System.out.println("After delete rear element new rear become : " +
dq.getRear());
+dq.getFront()); dq.deletefront();
}
}
Output:
insert element at rear end : 5
insert element at rear end : 10
get rear element : 10
After delete rear element new rear become :
5 inserting element at front end
get front element : 15
After delete front element new front become : 5
Exercise: (10)
Run the given program and write down the output and explain the steps.
//Java program to find circular tour for a truck
// constructor
public petrolPump(int petrol, int distance)
// Return starting
point return start;
}
}
}
Output
Linked List
Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at
a contiguous location; the elements are linked using pointers.
In Java or C#, LinkedList can be represented as a class and a Node as a separate class. The LinkedList
class contains a reference of Node class type.
class LinkedList {
Node head; // head of the list
/* Linked list
Node*/ class Node {
int data;
Node next;
llist.printList();
}
}
/* Linked list
Node*/ class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
/* Linked list
Node*/ class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next =
null;
}
}
Output
Exercises
Exercise 1: (2)
Write a function to get Nth node in a Linked List
Exercise 3: (2)
Swap nodes in a linked list without swapping data
/* Given a node as prev_node, insert a new node after the given node
*/ public void InsertAfter(Node prev_Node, int new_data)
{
/* 2. allocate node
* 3. put in the data */
Node new_node = new Node(new_data);
// This function prints contents of linked list starting from the given
node public void printlist(Node node)
{
Node last = null;
System.out.println("Traversal in forward
Direction"); while (node != null) {
System.out.print(node.data + "
"); last = node;
node = node.next;
}
System.out.println();
System.out.println("Traversal in reverse
Output:
// Base case
if (head == null || del == null) {
return;
}
// Driver Code
public static void main(String[] args)
{
// Start with the empty list
DLL dll = new DLL();
Output:
Original Linked list 10 8 4
2 Modified Linked list 8
Exercises
Exercise 1: (2)
Delete all the nodes from a doubly linked list that are smaller than a given value
Exercise 3: (2)
Delete a Node from linked list without head pointer
This project can demonstrate the working of contact book applications and also teach you about data structures like
arrays, linked lists, stacks, and queues. Typically, phone book management encompasses searching, sorting, and
deleting operations. A distinctive feature of the search queries here is that the user sees suggestions from the
contact list after entering each character. You can read the source-code of freely available projects and replicate the
same to develop your skills.
This project demonstrates how to address the book programs’ function. It also teaches you about queuing, stacking,
linking lists, and arrays. Usually, this project’s directory includes certain actions like categorising, scanning, and
removing. Subsequently, the client shows recommendations from the address book after typing each character. This
is the web searches’ unique facet. You can inspect the code of extensively used DSA projects in C++ and
applications and ultimately duplicate them. This helps you to advance your data science career.
Date
Group Members: List of Roll number and Names
System introduction: what is the system about?
Problem Statement: what is the possible problem area that you will attempt to implement?
*Semester Project Report Template is attached with this lab. Please format your report
accordingly.
GROUP MEMBERS:
NAME/ROLL NO. :
NAME/ROLL NO. :
NAME/ROLL NO. :
NAME/ROLL NO. :
SUBMITTED TO:
DATED:
For every group project, evaluation will be done on the following criteria:
Project Idea
Code Demonstration
(Is it consistent with the proposed design?)
Interface Bonus
Project Report
(is compiling, formatting, correctness and
completeness in accordance with the given
project report template?)*
Slideshow Presentation
Node Code
/* Class containing left and right child of
current node and key value*/
class Node
{
int key;
Node left, right;
public Node(int
item)
{
key = item;
left = right = null;
// Constructors
BinaryTree(int key)
{
root = new Node(key);
}
BinaryTree()
{
root = null;
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*create root*/
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new
Node(4);
}
}
// constructor
Node(int key){
this.key = key;
left = null;
right = null;
}
}
public class GFG {
/* A binary tree node has key, pointer
to left child and a pointer to right child
*/ static Node root;
static Node temp = root;
/* Inorder traversal of a binary
tree*/ static void inorder(Node
temp)
{
if (temp == null)
return;
inorder(temp.left);
System.out.print(temp.key+" ");
inorder(temp.right);
}
if (temp.right == null) {
temp.right = new
Node(key); break;
} else
q.add(temp.right);
}
}
// Driver code
public static void main(String args[])
{
root = new Node(10);
root.left = new Node(11);
root.left.left = new
Node(7); root.right = new
Node(9);
root.right.left = new Node(15);
root.right.right = new
Node(8);
Output:
Inorder traversal before insertion: 7 11 10 15 9 8
Inorder traversal after insertion: 7 11 12 10 15 9 8
class Node
{ Object data;
Node left;
Node right;
Node( Object d ) // constructor
{ data = d; }
}
class BinaryTree
{
Object tree[];
int maxSize;
java.util.Stack<Node> stk = new java.util.Stack<Node>();
p.left = buildTree(2*index+1);
p.right =
buildTree(2*index+2);
}
return p;
}
/* Recursive methods - Binary tree traversals */ public void
inorder(Node p) {
if( p != null )
{
inorder(p.left);
System.out.print(p.data + "
"); inorder(p.right);
}
}
public void preorder(Node p)
{
if( p != null )
{
System.out.print(p.data + " ");
86 Data Structure and Algorithms Lab Manual
preorder(p.left);
preorder(p.right);
}
}
public void postorder(Node p)
{
if( p != null )
{
postorder(p.left);
postorder(p.right);
System.out.print(p.data + "
");
}
}
/* Non-recursive methods - Binary tree traversals */ public void
preorderIterative(Node p) {
if(p == null )
{ System.out.println("Tree is empty");
return;
}
stk.push(p);
while( !stk.isEmpty() )
{
p = stk.pop();
if( p != null )
{
System.out.print(p.data + "
"); stk.push(p.right);
stk.push(p.left);
}
}
}
public void inorderIterative(Node p)
{
if(p == null )
{ System.out.println("Tree is empty"); return;
}
while( !stk.isEmpty() || p != null )
{
if( p != null )
{ stk.push(p); // push left-most path onto stack p =
p.left;
}
else
{
p = stk.pop(); // assign popped node to p System.out.print(p.data
+ " "); // print node data p = p.right; // move p to right subtree
}
}
87 Data Structure and Algorithms Lab Manual
}
}
88 Data Structure and Algorithms Lab Manual
public void postorderIterative(Node p)
{
if(p == null )
{ System.out.println("Tree is empty"); return;
}
Node tmp = p;
while( p != null
)
{
while( p.left != null )
{ stk.push(p); p = p.left;
}
while( p != null && (p.right == null || p.right == tmp ))
{ System.out.print(p.data + " "); // print node data tmp = p;
if( stk.isEmpty() )
return;
p = stk.pop();
}
stk.push(p);
p = p.right;
}
}
} // end of BinaryTree class
//////////////////////// BinaryTreeDemo.java //////////////////////
class BinaryTreeDemo
{
public static void main(String args[])
{
Object arr[] = {'E', 'C', 'G', 'A', 'D', 'F', 'H', null,'B', null,
null, null, null, null, null, null, null, null, null};
BinaryTree t = new BinaryTree( arr, arr.length );
}
89 Data Structure and Algorithms Lab Manual
System.out.print("\n postorder: ");
t.postorderIterative(root);
}
90 Data Structure and Algorithms Lab Manual
}
Output:
Recursive Binary Tree
Traversals: inorder: A B C D E F
G H preorder: E C A B D G F H
postorder: B A D C F H G E
Non-recursive Binary Tree
Traversals: inorder: A B C D E F G H
preorder: E C A B D G F H
postorder: B A D C F H G
E
Traverse a binary tree level by level. That is, the root is visited first, then the immediate
children of the root (from left to right), then grandchildren of the root (from left to right), and
so on. The algorithm uses a queue to keep track of the children of a node until it is time to
visit them. This algorithm is also known as breadth-first traversal.
1. Initialize a queue.
2. Insert the root into the queue.
3. Repeat steps 4 to 7 until the queue is empty.
4. Delete the node from the queue.
5. Process the node being deleted.
6. If the left child of node exists (is not null), insert it into the queue.
7. If the right child of node exists (is not null), insert it into the queue
new java.util.LinkedList<Node>();
BinaryTree( Object a[], int n ) // constructor { maxSize =
n;
tree = new Object[maxSize];
for( int i=0; i<maxSize; i++
)
tree[i] = a[i];
}
public Node buildTree( int index )
{ Node p = null;
if( tree[index] != null )
{ p = new Node(tree[index]);
p.left = buildTree(2*index+1);
p.right =
buildTree(2*index+2);
}
return p;
}
"); t.levelorder(root);
}
}
Output:
Level Order Tree Traversal: E C G A D F H B
Exersises
Exercise 1: (10)
Write a program which should implement a binary tree using a static array of size 10. Elements of this
array of integer type, user will provide values as input for elements of this array. Your program should
allow searching of a value specified by user in tree and it will also provide deletion of a value specified
by user.
45
25 65
15 30 55 75
10 20 50 60 80
class BSTNode
{
int data;
BSTNode left;
BSTNode right;
BSTNode( int d ) { data = d; }// constructor
{
parent = inorderSucc; inorderSucc
= inorderSucc.left;
}
p.data = inorderSucc.data;
p = inorderSucc;
} // case-
if(p.left == null && p.right == null) 1
{
if( parent.left == p ) parent.left = null;
else parent.right = null;
}
if(p.left == null && p.right != null) // case-2(a)
{
if(parent.left == p) parent.left =
p.right; else parent.right = p.right;
} // case-
if(p.left != null && p.right == 2(b)
null)
{
if(parent.left == p) parent.left =
p.left; else parent.right = p.left;
}
return root;
}
// 'p' starts
public void inorder(BSTNode with root
p)
{ if( p != null )
{ inorder(p.left);
System.out.print(p.data + "
"); inorder(p.right);
}
}
public void preorder(BSTNode p)
{ if( p != null )
{ System.out.print(p.data + " ");
preorder(p.left);
preorder(p.right);
91 Data Structure and Algorithms Lab Manual
}
}
public void postorder(BSTNode p)
Output:
Exersise 1 [5]
Write a program which should implement a binary search tree containing floating point values as its
elements. Program should allow user to insert a value in tree and program should also perform pre
order, post order and in order traversal of this tree. Program should also count the number of nodes
present in the tree.
2.3
2.1 3.4
1.9 5.6
1.5
You can base your project on these alternatives and explore how they can outperform other widely-
used BSTs in different scenarios. For instance, splay trees can prove faster than red-black trees under
the conditions of serious temporal locality.
Moreover, such data structures are easy to accomplish in C language. You can also attempt to bind it
with Ruby and a convenient API. Go for an interface that allows you to specify ‘lambda’ as your
ordering function and your subtree memoizing function. All in all, you can expect reduction-memoizing
BSTs to be self-balancing BSTs with a dash of additional book-keeping.
Dynamic coding will need cognitive memorisation for its implementation. Each vertex in a reducing BST
can memorise its sub–trees’ functionality. For example, a BST of persons is categorised by their age.
This DSA topics based project idea allows the kid node to store every individual’s maximum salary. This
framework can be used to answer the questions like “what’s the income limit of persons aged 25 to
30?”
Balanaced Tree
A B-tree of order m is an m-way tree in
which All leaf nodes are on the same level.
All nodes, except the root and the leaves, have between [m/2] and m children.
The nonleaf nodes store up to m-1 keys to guide the searching; and these keys partition the keys
in the children in the fashion of a search tree.
The root is either a leaf or has between two and m children.
If a node has ‘d’ number of children, then it must have d-1 number of keys.
Program B-Tree
class BTree
{
final int MAX =
4; final int MIN =
2;
); if ( pushup )
{
node.count = 1;
node.key[1] = i.m;
node.child[0] = root;
node.child[1] = c;
root = node;
}
}
/*
* New key is inserted into subtree to which current node points.
* If pushup becomes true, then height of the tree grows.
*/
boolean pushDown( int val, BTNode node, Ref p, BTNode c )
{
Ref k = new Ref();
if ( node == null )
{
p.m = val;
c = null;
return true;
}
else
{
if ( searchNode( val, node, k ) ) System.out.println("Key
already exists.");
if ( pushDown( val, node.child[k.m], p, c ) )
{
int i;
if ( root != null )
{
for ( i = 0; i < root.count; i++ )
{
display( root.child[i] );
System.out.print( root.key[i+1] + " "
);
}
display( root.child[i] );
}
}
} // end of BTree class
////////////////////////// BTreeDemo.java /////////////////////////////
class BTreeDemo
{
public static void main( String[] args )
{
BTree bt = new BTree();
/*
* Refer Textbook, the section 13.3 B-Trees,
* inserting into a B-Tree
* Figure 13.30: Building a B-tree of order 5
*/
int[] arr = { 11, 23, 21, 12, 31, 18, 25, 35, 29, 20, 45, 27, 42, 55, 15, 33,
36, 47, 50, 39 };
for ( int i = 0; i < arr.length; i++
) bt.insertTree( arr[i] );
System.out.println("B-Tree of order 5:");
bt.displayTree();
}
}
Exersise [1o]
Write a deletion method
Dictionary
An ADT that supports the operations insert, delete, and search is called a dictionary. Dictionaries are
found applications in the design of numerous algorithms. A dictionary is a collection of pairs of key and
element. No two pairs in a dictionary have the same key.
Consider a database of books maintained in a library system. When a user wants to check whether a
particular book is available, a search operation is called for. If the book is available and is issued to the
user, a delete operation can be performed to remove this book from the set of available books. When the
user returns the book, it can be inserted back into the set.
It is essential that we are able to support the above-mentioned operations as efficiently as possible since
these operations are performed quite frequently. A number of data structures have been developed to
realize a dictionary. These can be broadly divided into comparison methods and direct access methods.
Hashing is an example of the latter. Comparison methods fit into binary search trees.
Program Dictionary operations using Hash tables
class Entry
{ public String key; // word
public String element; // word meaning
public Entry(String k, String e) // constructor
{
key = k;
element = e;
}
}
class HashTable
{
Entry[] hashArray; // array holds hash table
int size; // table size
// current number of items in
int count; the table
public HashTable(int s) // constructor
{
size = s;
count =
0;
hashArray = new Entry[size];
if(hashVal < 0 )
hashVal = hashVal + size;
return hashVal;
}
public void insert(String theKey, String str) // insert a record {
if( !isFull() )
{
int hashVal = hashFunc(theKey); // hash the key
// until empty cell or null,
while(hashArray[hashVal] != null
)
++hashVal; // go to next cell
hashVal
%= size; // wraparound if necessary
}
hashArray[hashVal] = new Entry(theKey,
}
}
public boolean isEmpty() // returns true, if table is empty {
return count == 0;
}
public boolean isFull() // returns true, if table is full {
// Search an item
String word =
"wish";
Entry item = ht.search(word);
if( item != null )
System.out.println("found: " + item.key + "\t" + item.element); else
System.out.println(word + " not found");
// Delete an item word =
"hope";
item = ht.delete(word); if( item !=
null )
System.out.println("deleted: " + item.key + "\t" + item.element);
else System.out.println(word + " not found - no deletion");
// Current number of items in the table
System.out.println("size: " +
ht.currentSize());
}
}
Output:
<< Dictionary Table
>> insert put in
help lend a hand
man gentleman
watch observe
format arrangement
run sprint
wish desire
arrange put together
hope expect
import java.util.*;
class HashtableDemo
{ public static void main(String[] args)
{
Hashtable<String, String> htab = new Hashtable<String, String>();
// Insert the following items
htab.put("man", "gentleman");
htab.put("watch", "observe");
htab.put("hope", "expect");
htab.put("arrange", "put together");
htab.put("run", "sprint");
htab.put("wish", "desire");
htab.put("help", "lend a hand");
htab.put("insert", "put in");
htab.put("count", "add up");
htab.put("format", "arrangement");
System.out.println(htab); // Display the table items
System.out.println("remove(arrange): " +
htab.remove("arrange")); System.out.println("remove(help): " +
htab.remove("help"));
// returns a set containing all the pairs (key,
value). System.out.println(htab.entrySet());
}
}
Output:
{ arrange=put together, man=gentleman, wish=desire, run=sprint, help=lend a hand,
count=add up, watch=observe, hope=expect, format=arrangement, insert=put in }
get(hope): expect
remove(arrange): put together
remove(help): lend a hand
[ man=gentleman, wish=desire, run=sprint, count=add up, watch=observe, hope=expect,
format=arrangement, insert=put in ]
Exercises
108 Data Structure and Algorithms Lab Manual
108 Data Structure and Algorithms Lab Manual
Exersise 1 [5]
Given an array of n integers. The task is to find the first element that occurs k number of times.
If no element occurs k times the print -1. The distribution of integer elements could be in any
range.
Heap ADT
Linked structures are not the only way in which you can represent trees. If you take the binary tree
shown below and copy its contents into an array in level order, you produce the following array.
Index Entry
93
0 93
1 82
2 64
82 64
3 27
4 75
5 39
27 75 39 18 6 18
Examining the relationship between positions in the tree and entries in the array, you see that if an
element is stored in entry N in the array, then the elementÕs left child is stored in entry 2N + 1, its right
child is stored in entry 2N + 2, and its parent is stored in entry (N 1) / 2. These mappings make it easy to
move through the tree stepping from parent to child (or vice versa).
You could use these mappings to support an array-based implementation of the Binary Search Tree
ADT. However, the result would be a tree representation in which large areas of the array are left unused
(as indicated by the dashes in the following array).
92
13 Ñ
14 92
72
72 34
26 66 9
The fact that the tree is complete means that a heap can be stored in level order in an array without
introducing gaps (unused areas) in the middle. The result is a compact representation in which you can
easily move up and down the branches in a heap.
Structure
The elements form a complete binary tree. This is a max-heap. For each element E in the tree, all of
EÕs descendants have priorities that are less than or equal to EÕs priority.
HeapData removeMax ( )
Precondition:
Heap is not
empty.
Postcondition:
Removes the element with the highest priority (the root) from a heap and returns it. Replaces the
root element with the bottom rightmost element and moves this element downward until the
properties that deÞne a heap are restored. Note that (as in insert above) repeatedly swapping array
elements is not an efÞcient method for restoring the heap.
void clear ( )
Precondition:
None.
Postcondition:
Removes all the elements in a heap.
boolean isEmpty (
) Precondition:
None.
Postcondition:
Returns true if a heap is empty. Otherwise, returns false.
boolean isFull (
) Precondition:
None.
Postcondition:
Returns true if a heap is full. Otherwise, returns false.
void showStructure (
) Precondition:
None.
Postcondition:
Outputs the priorities of the elements in a heap in both array and tree form. The tree is out-put
with its branches oriented from left (root) to right (leaves)Ñthat is, the tree is output rotated
counterclockwise 90 degrees from its conventional orientation. If the heap is empty, outputs
ÒEmpty heapÓ. Note that this operation is intended for testing/debugging purposes only.
Exersise 01 [4]
Write a program which should implement a max heap tree containing floating point values as its
elements. Program should allow user to insert a value in tree and program should perform search a value
input by user to check whether it exists in tree or not?
Heap insertion time (average case insertion time for binary heap data
structures )
119 Data Structure and Algorithms Lab Manual
According to some online sources, it is constant time, while others imply that it is log(n) time. But
Bollobas and Simon give a numerically-backed answer in their paper entitled, “Repeated random
insertion into a priority queue.” First, they assume a scenario where you want to insert n elements into
an empty heap. There can be ‘n!’ possible orders for the same. Then, they adopt the average cost
approach to prove that the insertion time is bound by a constant of 1.7645.
When looking for Data Structures tasks in this project idea, you will face challenges that are addressed
using novel methods. One of the interesting research subjects is the mean response insertion time for the
sequential heap DS.
Inserting ‘n’ components into an empty heap will yield ‘n!’ arrangements which you can use in suitable
DSA projects in C++. Subsequently, you can implement the estimated cost approach to specify that the
inserting period is limited by a fixed constant.
Optimal treaps with priority-changing parameters
Treaps are a combination of BSTs and heaps. These randomized data structures involve assigning
specific priorities to the nodes. You can go for a project that optimizes a set of parameters under
different settings. For instance, you can set higher preferences for nodes that are accessed more
frequently than others. Here, each access will set off a two-fold process:
Choosing a random number
Replacing the node’s priority with that number if it is found to be higher than the previous priority
As a result of this modification, the tree will lose its random shape. It is likely that the frequently-
accessed nodes would now be near the tree’s root, hence delivering faster searches. So, experiment with
this data structure and try to base your argument on evidence.
At the end of the project, you can either make an original discovery or even conclude that changing the
priority of the node does not deliver much speed. It will be a relevant and useful exercise, nevertheless.
Constructing a heap involves building an ordered binary tree and letting it fulfill the “heap” property.
But if it is done using a single element, it would appear like a line. This is because in the BST, the right
child should be greater or equal to its parent, and the left child should be less than its parent. However,
for a heap, every parent must either be all larger or all smaller than its children.
The numbers show the data structure’s heap arrangement (organized in max-heap order). The alphabets
show the tree portion. Now comes the time to use the unique property of treap data structure in DSA
projects in C++. This treap has only one arrangement irrespective of the order by which the elements
were chosen to build the tree.
You can use a random heap weight to make the second key more useful. Hence, now the tree’s structure
will completely depend on the randomized weight offered to the heap values. In the file structure mini
project topics, we obtain randomized heap priorities by ascertaining that you assign these randomly.
Graph Traversals
A primary problem concerning the graphs is the reachability. A number of graph problems involve
traversal of a graph. Traversal of a graph means visiting each of its nodes exactly once. This is
accomplished by visiting the nodes in a systematic manner. Two commonly used techniques of
graph traversal are depth-first search (DFS) and breadth-first search (BFS). These algorithms work
for both directed and undirected graphs.
Depth-First Search
Depth-first search is a generalization of the preorder traversal of a tree. DFS can serve as a structure
around which many other efficient graph algorithms can be built.
As an example of dfs, suppose in the graph of the following figure, we start at node A. A complete
program listing is given in Program 31(a).
A A B D E X A B C D E
A 0 1 0 1 1
B A C D X
B 1 0 1 1 0
B D
C B D E X
E C 0 1 0 1 1
D 1 1 1 0 0
D A B C X
C E E 1 0 1 0 0
Undirected C X A Adjacency
Graph matrix
Adjacency list
{ size = n;
while( w != null)
{ v = w.label;
if( mark[v] == 0 ) dfs(v); w =
w.next;
}
}
}
Breadth-First Search
Another systematic way of visiting the nodes is called breadth- first search (bfs). The approach is
called “breadth-first” because from each node v that we visit we search as broadly as possible by
next visiting all nodes adjacent to v.
The breadthFirstSearch algorithm inserts a node into a queue, which we assume is initially empty.
Every entry in the array mark is assumed to be initialized to the value unvisited. If the graph is not
connected, bfs must be called on a node of each connected component. Note that in bfs we must
mark a node visited before inserting it into the queue, to avoid placing it on the queue more than
once. The algorithm terminates when the queue becomes empty.
We assume the graph is represented by an adjacency list and is globally available. The algorithm
depends on the availability of an implementation of a queue of integers (here, a simple queue is
assumed; not circular queue). Three methods relating to queue: qinsert(), qdelete(), and isEmpty() are
to be properly defined before the method for bfs is defined.
Program
class Node
{ int label; // vertex label
// next node
Node next; in list
Node( int b ) // constructor
{ label = b; }
}
class Graph
{ int size; Node adjList[];
int mark[];
Graph(int n) // constructor
{ size = n;
adjList = new
Node[size]; mark = new
int[size];
}
public void createAdjList(int a[][]) // create adjacent lists
{ Node p; int i, k;
for( i = 0; i < size; i++ )
{ p = adjList[i] = new Node(i); for( k = 0; k
< size; k++ ) { if( a[i][k] == 1 )
{ p.next = new Node(k);
p = p.next;
}
} // end of inner for-loop
} // end of outer for-loop
} // end of createAdjList()
public void bfs(int head)
{ int v; Node adj;
Queue q = new Queue(size);
124 Data Structure and Algorithms Lab Manual
v = head;
mark[v] = 1;
System.out.print(v + " ");
q.qinsert(v); // while(queue not
while( !q.IsEmpty() empty)
)
{
adj = adj.next;
}
}
}
} // end of Graph class
class Queue
{ private int maxSize; // max queue size
// que is an array
private int[] que; of integers
private int front;
private int rear; // count of items in
private int count; queue
public Queue(int s) // constructor
{ maxSize = s;
que = new int[maxSize]; front
= rear = -1;
}
public void qinsert(int item)
{ if( rear == maxSize-1 ) System.out.println("Queue is
Full");
else { rear = rear + 1;
que[rear] = item;
if( front == -1 ) front = 0;
}
}
public int qdelete()
{ int item;
if( IsEmpty() )
{ System.out.println("\n Queue is
Empty"); return(-1);
}
item = que[front];
if( front == rear ) front = rear = -
1; else front = front+1;
return(item);
Output
01342
For starters, you will need a data structure similar to binary trees. Now, suppose that you have a standard 8 X 8
chessboard, and you want to show the knight’s movements in a game. As you may know, a knight’s basic move in
chess is two forward steps and one sidestep. Facing in any direction and given enough turns, it can move from any
square on the board to any other square.
If you want to know the simplest way your knight can move from one square (or node) to another in a two-
dimensional setup, you will first have to build a function like the one below.
Most data structures are designed to store and access objects of uniform size. A typical example would
be an integer stored in a list or a queue. Some applications require the ability to store variable-length
records, such as a string of arbitrary length. One solution is to store in list or queue a bunch of pointers
to strings, where each pointer is pointing to space of whatever size is necessary to old that string. This is
fine for data structures stored in main memory. But if the collection of strings is meant to be stored on
disk, then we might need to worry about how exactly these strings are stored. And even when stored in
main memory, something has to figure out where there are available bytes to hold the string. In a
language like C++ or Java, programmers can allocate space as necessary (either explicitly with new or
implicitly with a variable declaration). Where does this space come from? This section discusses
memory management techniques for the general problem of handling space requests of variable size.
The basic model for memory management is that we have a (large) block of contiguous memory
locations, which we will call the memory pool. Periodically, memory requests are issued for some
amount of space in the pool. A memory manager has the job of finding a contiguous block of locations
of at least the requested size from somewhere within the memory pool. Honoring such a request is
called memory allocation. The memory manager will typically return some piece of information that the
requestor can hold on to so that later it can recover the data that were just stored by the memory
manager. This piece of information is called a handle. At some point, space that has been requested
might no longer be needed, and this space can be returned to the memory manager so that it can be
reused. This is called a memory deallocation. We can define an ADT for a simple memory manager for
storing variable length arrays of integers as follows.
The user of the MemManager ADT provides a pointer (in parameter info) to space that holds some
message to be stored or retrieved. This is similar to the C++ basic file read/write methods. The
fundamental idea is that the client gives messages to the memory manager for safe keeping. The
memory manager returns a receipt for the message in the form of a MemHandleobject. The client holds
129 Data Structure and Algorithms Lab Manual
the MemHandle until it wishes to get the message back.
Method insert lets the client tell the memory manager the length and contents of the message to be
stored. This ADT assumes that the memory manager will remember the length of the message associated
When all inserts and releases follow a simple pattern, such as last requested, first released (stack order),
or first requested, first released (queue order), memory management is fairly easy. We are concerned
here with the general case where blocks of any size might be requested and released in any order. This is
known as dynamic memory allocation. One example of dynamic memory allocation is managing free
store for a compiler's runtime environment, such as the system-level new and delete operations in C++.
Another example is managing main memory in a multitasking operating system. Here, a program might
require a certain amount of space, and the memory manager must keep track of which programs are
using which parts of the main memory. Yet another example is the file manager for a disk drive. When a
disk file is created, expanded, or deleted, the file manager must allocate or deallocate disk space.
A block of memory or disk space managed in this way is sometimes referred to as a heap. The term
"heap" is being used here in a different way than the heap data structure typically used to implement a
priority queue. Here "heap" refers to the memory controlled by a dynamic memory management
scheme.
Exersises
Exersise [1o]
Given two four digit prime numbers, suppose 1033 and 8179, we need to find the shortest path from
1033 to 8179 by altering only single digit at a time such that every number that we get after changing a
digit is prime. For example a solution is 1033, 1733, 3733, 3739, 3779, 8779, 8179
Examples:
Input : 1033 8179
Output :6
Objectives
Learn to implement the real problem using Java.
Introduction: Present your semester project on a projector in class for final evaluation.
Submit the project report to the instructor.
For every group project, evaluation will be done on the following criteria:
Project Idea
Code Demonstration
(Is it consistent with the proposed design?)
Interface Bonus
Project Report
(is compiling, formatting, correctness and
completeness in accordance with the given
project report template?)*
Slideshow Presentation