CST 370: Design and Analysis of Algorithms

Course Description

Students learn important data structures in computer science and acquire fundamental algorithm design techniques to get the efficient solutions to several computing problems from various disciplines. Topics include the analysis of algorithm efficiency, hash, heap, graph, tree, sorting and searching, brute force, divide-and-conquer, decrease-and-conquer, transform-and-conquer, dynamic programming, and greedy programming.

/*
 * INSTRUCTION:
 *     This is a Java starting code for hw6_1.
 *     When you finish the development, download this file.
 *     Note that the current filename is "Main.java".
 *     But rename it to "Main_hw6_1.java".
 *     After that, upload the renamed file on Canvas.
 */

// Finish the head comment with Abstract, Name, and Date.
/*
 * Title: Main_hw6_1.java
 * Abstract: Finds maximum number of coins collect and prints the backtracked path
 * Name: Yavik Kapadia
 * Date: 12/13/2022
 */
import java.util.Scanner;
import java.util.ArrayList;
import java.lang.StringBuilder;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = input.nextInt();
            }
        }
        robotCoinCollection(matrix);
        
       }

    public static void robotCoinCollection(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] dp = new int[n][m];
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + matrix[i][0];
        }
        for (int j = 1; j < m; j++) {
            dp[0][j] = dp[0][j - 1] + matrix[0][j];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
            }
        }
        System.out.println("Max coins:" + dp[n - 1][m - 1]);
        // print the path
        int i = n - 1;
        int j = m - 1;
        ArrayList<String> path = new ArrayList<>();
        while (i != 0 || j != 0) {
           // except for last coordinate
           int temp_i = i + 1;
           int temp_j = j + 1;
            path.add("(" + temp_i + "," + temp_j + ")");
            if (i == 0) {
                j--;
            } else if (j == 0) {
                i--;
            } else {
                if (dp[i - 1][j] > dp[i][j - 1]) {
                    i--;
                } else {
                    j--;
                }
            }
        }
        path.add("(1,1)");
        StringBuilder sb = new StringBuilder();
        for (int k = path.size() - 1; k >= 0; k--) {
            if(k == 0) {
                sb.append(path.get(k));
            } else {
                sb.append(path.get(k) + "->");
            } 
        }

        System.out.println("Path:" + sb.toString());
    }

    
}

/*
 * INSTRUCTION:
 *     This is a Java starting code for hw6_2.
 *     When you finish the development, download this file.
 *     Note that the current filename is "Main.java".
 *     But rename it to "Main_hw6_2.java".
 *     After that, upload the renamed file on Canvas.
 */

// Finish the head comment with Abstract, Name, and Date.
/*
 * Title: Main_hw6_2.java
 * Abstract: Finds shorts path pairs utilizing Floyd algo
 * Name: Yavik Kapadia
 * Date: 12/13/2022
 */
import java.util.*;


class Main {
  public static final int INF = 999999;

  // a function that implements Floyds Algorithm
  public static void floydsAlgorithm(int graph[][], int vertecies) {
        int dist[][] = new int [vertecies][vertecies];
        int i, j, k;

        for (i = 0; i < vertecies; i++)
            for (j = 0; j < vertecies; j++)
                dist[i][j] = graph[i][j];

        for (k = 0; k < vertecies; k++) {
            for (i = 0; i < vertecies; i++) {
                for (j = 0; j < vertecies; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        displayMatrix(dist, vertecies);
    }

    private static void displayMatrix(int graph[][], int vertecies) {
        for (int i = 0; i < vertecies; ++i) {
            for (int j = 0; j < vertecies; ++j) {
                if(graph[i][j] == INF){
                    graph[i][j] = -1;
                }
                if(j < vertecies - 1){
                    System.out.print(graph[i][j] + " ");
                }
                else{    
                    System.out.print(graph[i][j]);
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int vertecies = in.nextInt(); // user input number of vertecies
        int graph[][] = new int [vertecies][vertecies]; // holds the graph
            
        // reads in the graph row by row
        for (int i = 0; i < vertecies; i++) {
            for (int j = 0; j < vertecies; j++) {
                int input = in.nextInt();
                // if the input is -1, set it to the max value
                if(input == -1){
                  input = INF;
                }
                graph[i][j] = input; // user input
            }
        }
        in.close();

        floydsAlgorithm(graph, vertecies); // calling method
    }
}