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:
