Question

need help to write the main method as the template

import java.util.*;

public class oBST {

static float optimalBST(String words[], float freq[], int n) {

//2D dp matrix

float dp[][] = new float[n + 1][n + 1];

int root[][] = new int[n+1][n+1];

// For a single word, cost is equal to frequency of the word

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

dp[i][i] = freq[i];

// Now consider for size 2, 3, ... .

for (int L = 2; L <= n; L++) {

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

// Get column number j from row number i and size L

int j = i + L - 1;

dp[i][j] = Integer.MAX_VALUE;

for (int r = i; r <= j; r++) {

// c = cost when words[r] becomes root of this subtree

float c = ((r > i) ? dp[i][r - 1] : 0)

+ ((r < j) ? dp[r + 1][j] : 0) + sum(freq, i, j);

if (c < dp[i][j]){

dp[i][j] = c;

root[i][j] = r;

}

}

}

}

// Print computed matrices

System.out.println("*******Cost matrices******\n");

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

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

System.out.print(dp[i][j]+" ");

}

System.out.print("\n");

}

//print the root matrices

System.out.println("\n\n******Root matrices*****\n");

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

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

System.out.print(root[i][j]+" ");

}

System.out.print("\n");

}

//return the optimal cost

return dp[0][n - 1];

}

// function to get sum of freq[i] to freq[j]

static float sum(float freq[], int i, int j) {

float s = 0;

for (int k = i; k <= j; k++) {

if (k >= freq.length)

continue;

s += freq[k];

}

return s;

}

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

int n = sc.nextInt();

String words[]=new String[n];

float freq[]=new float[n];

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

words[i]=sc.next();

freq[i]=sc.nextFloat();

}

System.out.println("\ncost is "

+ optimalBST(words, freq, n));

sc.close();

}

}

Your main method should be as follow: public static void main(String args[]) throws Exception Xxxxxp4 obst = new xxxxxp4 0; // xxxxx is the first 5 characters of your last name System.out.print("\n\tProgram to compute average number of comparisons for an" + "n\tOptimal Binary Search Tree (obst) using dynamic programming.' + "\n\tPrepared by Last: , First: + "\n\tStudent ID: Date: // read input obst.readinput(); // read input method is written below (next page) // Compute 3 matrices: avg, w and root obst.compute(); // Print 3 matrices: avg, w and root obst.printmatrices(); // Print obst tree level by level by using queue data structure obst.printree();

Answer 1

Copy the code to an IDE and do the required changes:

import java.util.*; public class sometp4 { static float optimalBST(String[] words, float[] freq, int n) { //2D dp matrix float[][] dp = new float[n + 1][n + 1]; int[][] root = new int[n + 1][n + 1]; // For a single word, cost is equal to frequency of the word for (int i = 0; i < n; i++) dp[i][i] = freq[i]; // Now consider for size 2, 3, ... . for (int L = 2; L <= n; L++) { for (int i = 0; i <= n - L + 1; i++) { // Get column number j from row number i and size L int j = i + L - 1; dp[i][j] = Integer.MAX_VALUE; for (int r = i; r <= j; r++) { // c = cost when words[r] becomes root of this subtree float c = ((r > i) ? dp[i][r - 1] : 0) + ((r < j) ? dp[r + 1][j] : 0) + sum(freq, i, j); if (c < dp[i][j]) { dp[i][j] = c; root[i][j] = r; } } } } // Print computed matrices System.out.println("*******Cost matrices******\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(dp[i][j] + " "); } System.out.print("\n"); } //print the root matrices System.out.println("\n\n******Root matrices*****\n"); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(root[i][j] + " "); } System.out.print("\n"); } //return the optimal cost return dp[0][n - 1]; } // function to get sum of freq[i] to freq[j] static float sum(float[] freq, int i, int j) { float s = 0; for (int k = i; k <= j; k++) { if (k >= freq.length) continue; s += freq[k]; } return s; } public static void main(String[] args) throws Exception{ //Suppose your name is 'someone sometitle' sometp4 obst = new sometp4(); System.out.println("\n\tProgram to compute average number of comparisons for an" + "\n\tOptimal Binary Search Tree (obst) using dynamic programming." + "\n\tPrepared By: sometitle, someone" + "\n\tStudent ID: x123456 Date: 01\\01\\1970"); obst.readinput(); obst.compute(); obst.printmatrices(); obst.printree(); //Perform the below tasks in desired methods created below Scanner sc = new Scanner(System.in); int n = sc.nextInt(); String[] words = new String[n]; float[] freq = new float[n]; for (int i = 0; i < n; i++) { words[i] = sc.next(); freq[i] = sc.nextFloat(); } System.out.println("\ncost is " + optimalBST(words, freq, n)); sc.close(); } private void printree() { } private void printmatrices() { } private void compute() { } private void readinput() { } }