Question

write a C program on BFS and DFS?

Answer 1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

#include<stdio.h>

void DFS(int);

int G[10][10],visited[10],n;    //n is no of vertices and graph is sorted in array G[10][10]

void main()

{

    int i,j;

    printf("Enter number of vertices:");

  

    scanf("%d",&n);

    //read the adjecency matrix

    printf("\nEnter adjecency matrix of the graph:");

  

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

       for(j=0;j<n;j++)

            scanf("%d",&G[i][j]);

    //visited is initialized to zero

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

        visited[i]=0;

    DFS(0);

}

void DFS(int i)

{

    int j;

    printf("\n%d",i);

    visited[i]=1;

    

    for(j=0;j<n;j++)

       if(!visited[j]&&G[i][j]==1)

            DFS(j);

}

Answer 2

import java.io.File;

import java.util.ArrayList;

import java.util.Scanner;

public class AppsFileProcessor {

public static void main(String[] args) throws Exception {

File file = new File("MobileAppData.txt");

Scanner sc = new Scanner(file);

if (sc.hasNextLine()) sc.nextLine();

ArrayList<MobileApp> appList = new ArrayList<>();

while (sc.hasNextLine()) {

String line = sc.nextLine().trim();

if (line.isEmpty()) continue;

String name = line.split("/")[0];

String pricePart = line.split("Price@")[1].split("/")[0];

double price = Double.parseDouble(pricePart);

String scorePart = line.split("Score=")[1].split("/")[0];

int score = Integer.parseInt(scorePart);

String subsPart = line.split("Subscribers=")[1].replace("k", "");

int subscribers = Integer.parseInt(subsPart) * 1000;

MobileApp app = new MobileApp(name, price, score, subscribers);

appList.add(app);

}

sc.close();

for (MobileApp app : appList) {

System.out.println(app);

}

}

import java.io.File;

import java.io.PrintWriter;

import java.util.Scanner;

public class GradesFileProcessor {

public static void main(String[] args) throws Exception {

File inputFile = new File("grades.txt");

Scanner fileScanner = new Scanner(inputFile);

PrintWriter writer = new PrintWriter("grades_stats.txt");

double classSum = 0;

int studentCount = 0;

while (fileScanner.hasNextLine()) {

String line = fileScanner.nextLine().trim();

if (line.isEmpty()) continue;

String[] parts = line.split(" ");

int exam1 = Integer.parseInt(parts[0]);

int exam2 = Integer.parseInt(parts[1]);

int exam3 = Integer.parseInt(parts[2]);

double avg = (exam1 + exam2 + exam3) / 3.0;

classSum += avg;

studentCount++;

char letter = getLetterGrade(avg);

writer.printf("%d %d %d %.2f (%s)\n", exam1, exam2, exam3, avg, letter);

}

double classAvg = classSum / studentCount;

writer.printf("Class average = %.2f\n", classAvg);

fileScanner.close();

writer.close();

System.out.println("Done! Check grades_stats.txt");

}

private static char getLetterGrade(double grade) {

assert grade >= 0.0 && grade <= 100.0 : "invalid grade!";

if (grade >= 90) return 'A';

if (grade >= 80) return 'B';

if (grade >= 70) return 'C';

if (grade >= 60) return 'D';

return 'F';

}

Answer 3

public class Complex implements BasicInterface<Complex>, Comparable<Complex> {

private double real;

private double im;

public Complex(double real, double im) {

this.real = real;

this.im = im;

}

public double getReal() { return real; }

public void setReal(double real) { this.real = real; }

public double getIm() { return im; }

public void setIm(double im) { this.im = im; }

public double magnitude() {

return Math.sqrt(real * real + im * im);

}@Override

public Complex add(Complex a) {

return new Complex(this.real + a.real, this.im + a.im);

}

@Override

public Complex divideByInt(int n) {

return new Complex(this.real / n, this.im / n);

}

@Override

public int compareTo(Complex other) {

double mag1 = this.magnitude();

double mag2 = other.magnitude();

if (mag1 > mag2) return 1;

if (mag1 < mag2) return -1;

return 0;

}

@Override

public String toString() {

return String.format("%.2f + %.2fi", real, im);

}

}

Comments

public class Fraction implements BasicInterface<Fraction>, Comparable<Fraction> {

private int num;

private int den;



public Fraction(int num, int den) {

if (den == 0) {

throw new IllegalArgumentException("Denominator cannot be zero");

}

this.num = num;

this.den = den;

reduce();

}



public int getNum() { return num; }

public void setNum(int num) {

this.num = num;

reduce();

}



public int getDen() { return den; }

public void setDen(int den) {

if (den == 0) {

throw new IllegalArgumentException("Denominator cannot be zero");

}

this.den = den;

reduce();

}



private int gcd(int a, int b) {

a = Math.abs(a);

b = Math.abs(b);

while (b != 0) {

int temp = b;

b = a % b;

a = temp;

}

return a;

}



private void reduce() {

int gcd = gcd(num, den);

num /= gcd;

den /= gcd;

if (den < 0) {

num = -num;

den = -den;

}

}



@Override

public Fraction add(Fraction a) {

int newNum = this.num * a.den + a.num * this.den;

int newDen = this.den * a.den;

return new Fraction(newNum, newDen);

}



@Override

public Fraction divideByInt(int n) {

return new Fraction(this.num, this.den * n);

}



@Override

public int compareTo(Fraction other) {

double val1 = (double) this.num / this.den;

double val2 = (double) other.num / other.den;

if (val1 > val2) return 1;

if (val1 < val2) return -1;

return 0;

}



@Override

public String toString() {

return num + "/" + den;

}

---

import java.util.Scanner;

public class ImageProcessing {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = getValidDimension(scanner);
        int[][] image = new int[n][n];
        
        System.out.println("Enter the pixel values (0-255) for the " + n + "x" + n + " image:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                image[i][j] = getValidPixelValue(scanner, i, j);
            }
        }

        int contrastDegree = getValidContrastDegree(scanner);
        int[][] processedImage = enhanceContrast(image, contrastDegree);

        System.out.println("Original Image:");
        printImage(image);
        System.out.println("Processed Image:");
        printImage(processedImage);
        System.out.println("\nVerifying that image was not mutated:");
        printImage(image);
        
        scanner.close();
    }

    private static int[][] enhanceContrast(int[][] image, int degree) {
         int n = image.length;
         int[][] enhancedImage = new int[n][n];
         
         for (int i = 0; i < n; i++) {
             for (int j = 0; j < n; j++) {
                 int pixel = image[i][j];
                 
                 if (pixel > 128) {
                     enhancedImage[i][j] = Math.min(255, pixel + degree);
                 }
                 else {
                     enhancedImage[i][j] = Math.max(0, pixel - degree);
                 }
             }
         }
         
         return enhancedImage;
     }


    private static int getValidDimension(Scanner scanner) {
        int n = 0;
        boolean valid = false;
        
        while (!valid) {
            System.out.print("Enter the dimension N of the NxN image: ");
            
            if (scanner.hasNextInt()) {
                n = scanner.nextInt();
                if (n > 0) {
                    valid = true;
                } else {
                    System.out.println("Invalid input. Please enter a positive integer.");
                }
            } else {
                System.out.println("Invalid input. Please enter an integer.");
                scanner.next();
            }
        }
        
        return n;
    }

    private static int getValidPixelValue(Scanner scanner, int row, int col) {
        int pixelValue = 0;
        boolean valid = false;
        
        while (!valid) {
            System.out.print("Enter pixel value for [" + row + "][" + col + "] (0-255): ");
            
            if (scanner.hasNextInt()) {
                pixelValue = scanner.nextInt();
                if (pixelValue >= 0 && pixelValue <= 255) {
                    valid = true;
                }
                else {
                    System.out.println("Invalid pixel value. Please enter a value between 0 and 255.");
                }
            }
            else {
                System.out.println("Invalid input. Please enter an integer.");
                scanner.next();
            }
        }
        
        return pixelValue;
    }

    private static int getValidContrastDegree(Scanner scanner) {
        int degree = 0;
        boolean valid = false;
        
        while (!valid) {
            System.out.print("Enter the contrast degree (positive integer): ");
            
            if (scanner.hasNextInt()) {
                degree = scanner.nextInt();
                if (degree >= 0) {
                    valid = true;
                }
                else {
                    System.out.println("Please enter a non-negative integer.");
                }
            }
            else {
                System.out.println("Invalid input. Please enter an integer.");
                scanner.next();
            }
        }
        
        return degree;
    }

    private static void printImage(int[][] image) {
        int n = image.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(image[i][j] + " ");
            }
            System.out.println();
        }
    }
}

---

public class Problem3 {
    public static boolean isPalindrome(String s) {
        if (s == null || s.length() <= 1)
            return true;
        
        
        if (s.charAt(0) != s.charAt(s.length() - 1))
            return false;
        
        
        return isPalindrome(s.substring(1, s.length() - 1));
    }
    public static boolean isPalindromeEfficient(String s) {
        if (s == null)
            return true;
        return palindromeHelper(s, 0, s.length() - 1);
    }
    
    private static boolean palindromeHelper(String s, int left, int right) {
        if (left >= right)
            return true;
        if (s.charAt(left) != s.charAt(right))
            return false;
       
        return palindromeHelper(s, left + 1, right - 1);
    }

---

public class Problem4 {
    public static long Fibonacci_R(int n) {
        if (n < 0)
            throw new IllegalArgumentException();
        if (n == 0 || n == 1)
            return n;
        return Fibonacci_R(n - 1) + Fibonacci_R(n - 2);
    }
    
    public static long Fibonacci_I(int n) {
        if (n < 0)
            throw new IllegalArgumentException();
        if (n == 0 || n == 1)
            return n;
        
        long prev = 0;
        long curr = 1;
        
        for (int i = 2; i <= n; i++) {
            long next = prev + curr;
            prev = curr;
            curr = next;
        }
        return curr;
    }
    
    public static long Fibonacci_IA(int n) {
        if (n < 0)
            throw new IllegalArgumentException();
        if (n == 0 || n == 1)
            return n;
        
        long[] fib = new long[n + 1];
        fib[0] = 0;
        fib[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[n];
    }
    
    public static long Fibonacci_RM(int n) {
        if (n < 0)
            throw new IllegalArgumentException();
        
        long[] memo = new long[n + 1];
        for (int i = 0; i <= n; i++) {
            memo[i] = -1;
        }
        return fibMemoHelper(n, memo);
    }
    
    private static long fibMemoHelper(int n, long[] memo) {
        if (n == 0 || n == 1)
            return n;
        
       
        if (memo[n] != -1)
            return memo[n];
        
        
        memo[n] = fibMemoHelper(n - 1, memo) + fibMemoHelper(n - 2, memo);
        return memo[n];
    }