COMSATS University Islamabad,

Abbottabad Campus
Department of Computer Science
Lab Assignment-02 – Fall-24
Class: BCS-4A Date: 1/1/2025
Subject: Data Structure and Algorithms Total Time Allowed: 60 minutes
Name: Tayyab Shahid Registration #SP23-BCS-052

(CLO-3)
Mar
ks (10)

Question-1: Write a Java program to implement the Interpolation Search algorithm. The program should
allow the user to input a sorted array of integers and a target value to search. Use the Interpolation Search
technique to find the position of the target value in the array. If the target value is found, display its index;
otherwise, indicate that the value is not present in the array.

Requirements:
• Input:

• A sorted array of integers.

• A target value to search within the array.

• Output:

• The index of the target value if found.

• A message indicating the target is not found if it does not exist in the array.

• Implementation:

• Use the Interpolation Search formula to find the target.

• Optimize the search by narrowing the search range based on key distribution.

• Validation:

• Handle cases where the array is empty or contains only one element.

• Ensure input is sorted before processing.

Program:
 import java.util.Scanner;

public class InterpolationSearch {

public static int interpolationSearch(int[] arr, int target) {

int low = 0, high = arr.length - 1;

while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low == high) {

if (arr[low] == target) return low;

return -1;

int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

if (arr[pos] == target)

return pos;

if (arr[pos] < target)

low = pos + 1;

else

high = pos - 1;

return -1;

}
 public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.println("Enter the number of elements in the array:");

int n = scanner.nextInt();

if (n <= 0) {

System.out.println("Array is empty or invalid.");

return;

int[] arr = new int[n];

System.out.println("Enter the sorted elements of the array:");

for (int i = 0; i < n; i++) {

arr[i] = scanner.nextInt();

System.out.println("Enter the target value to search:");

int target = scanner.nextInt();

int result = interpolationSearch(arr, target);

if (result != -1)
System.out.println("Target found at index: " + result);

else

System.out.println("Target not found in the array.");

 scanner.close();

Output:

Question-2: Write a Java program to implement the Radix Sort algorithm. The program should allow the
user to input an array of non-negative integers and sort the array in ascending order using the Radix Sort
technique. Display the sorted array as output.

Requirements:

• Input:

• An array of non-negative integers provided by the user.

• Output:

• The sorted array in ascending order.

• Implementation:

• Use the Radix Sort algorithm, which sorts numbers digit by digit starting from the least
significant digit (LSD).

• Validation:
 • Handle cases where the array is empty.

• Validate that input contains only non-negative integers.

Program:

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.println("Enter the number of elements in the array:");

int n = scanner.nextInt();

if (n <= 0) {

System.out.println("Array is empty or invalid.");

return;

int[] arr = new int[n];

System.out.println("Enter the elements of the array (non-negative integers):");

for (int i = 0; i < n; i++) {

arr[i] = scanner.nextInt();

if (arr[i] < 0) {

System.out.println("Invalid input: Array contains negative integers.");

return;

}
 }

RadixSort.radixSort(arr);

System.out.println("Sorted array:");

System.out.println(Arrays.toString(arr));

scanner.close();
}

// Radix Sort implementation

class RadixSort {

public static void radixSort(int[] arr) {

int max = getMax(arr);

for (int exp = 1; max / exp > 0; exp *= 10) {

countSort(arr, exp);

private static int getMax(int[] arr) {

int max = arr[0];

for (int num : arr) {

if (num > max) max = num;

return max;
 }

private static void countSort(int[] arr, int exp) {

int n = arr.length;

int[] output = new int[n];

int[] count = new int[10];

for (int i = 0; i < n; i++) {

count[(arr[i] / exp) % 10]++;

for (int i = 1; i < 10; i++) {

count[i] += count[i - 1];

for (int i = n - 1; i >= 0; i--) {

output[count[(arr[i] / exp) % 10] - 1] = arr[i];

count[(arr[i] / exp) % 10]--;

System.arraycopy(output, 0, arr, 0, n);

Output: