Question 2: Levenshtein
Take the recursive Java program Levenshtein.java and convert it to the equivalent C program.
Tip: You have explicit permission to copy/paste the main method for this question, replacing instances of System.out.println with printf, where appropriate.
Notes
Warnings
The code you write should compile with clang -Wall without any warnings. A 1 point penalty will be applied to your score for each warning that is emitted by the compiler.
Levenshtein.java
public class Levenshtein { private static int testsFailed = 0; private static int testsExecuted = 0; public static void main( String[] args ) { System.out.println( "Testing typical cases.\n" ); testDistance( "kitten", "kitten", 0 ); testDistance( "kitten", "sitting", 3 ); testDistance( "kitten", "mittens", 2 ); testDistance( "balloon", "saloon", 2 ); testDistance( "hello", "doggo", 4 ); testDistance( "\t\thi", "\t\t\t\thi", 2 ); System.out.println( "\nTesting empty/edge cases.\n" ); testDistance( "", "", 0 ); testDistance( "hello", "", 5 ); testDistance( "", "doggo", 5 ); testDistance( "a", "b", 1 ); testDistance( "b", "b", 0 ); testDistance( " ", " ", 0 ); System.out.println( "\nThis might take a while...\n" ); testDistance( "12345678901", "123456789012", 1 ); // how many chars are we looking at? System.out.println( "\n******These tests will be opposite in the C version******\n" ); System.out.println( "\n******These tests **should** FAIL in the C version*******\n" ); testDistance( "kitten", "mitten\0s", 3 ); // ???? testDistance( "\0totally", "\0different", 9 ); System.out.println( "\nTotal number of tests executed: " + testsExecuted ); System.out.println( "Number of tests passed: " + (testsExecuted - testsFailed) ); System.out.println( "Number of tests failed: " + testsFailed ); } public static void testDistance( String s, String t, int expected ) { int distance = levenshtein( s, t ); if ( distance == expected ) { System.out.println( "Passed! You can get from '" + s + "' to '" + t + "' in " + expected + " moves." ); } else { System.out.println( "FAILED: I thought it would take " + expected + " moves, but apparently it takes " + distance + " moves to get from '" + s + "' to '" + t + "'." ); testsFailed++; } testsExecuted++; } public static int levenshtein( String s, String t ) { int cost; int distance; String deleteS; String deleteT; if (s.length() == 0) { distance = t.length(); } else if (t.length() == 0) { distance = s.length(); } else { if (s.charAt(0) == t.charAt(0)) { cost = 0; } else { cost = 1; } deleteS = s.substring(1); deleteT = t.substring(1); assert(deleteS.length() == s.length() - 1); assert(deleteT.length() == t.length() - 1); assert(s.endsWith(deleteS)); assert(t.endsWith(deleteT)); distance = minimum(new int[] { levenshtein(deleteS, t) + 1, levenshtein(s, deleteT) + 1, levenshtein(deleteS, deleteT) + cost }); } return distance; } public static int minimum( int minimum[] ) { int min = 0; assert( minimum.length > 0 ); if ( minimum.length > 0 ) { min = minimum[0]; for ( int i = 1; i < minimum.length; i++ ) { if ( minimum[i] < min ) { min = minimum[i]; } } } return min; } }
Working code implemented in C and appropriate comments provided for better understanding:
Source code for levenshtein.c:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define DIST_SIZE 3 //Defines the size of the array dist[]
initalized in levenshtein()
static int testsExecuted = 0;
static int testsFailed = 0;
static int minimum(int m[],int sizeDist)
//recieves a array of ints to compensate for java's varargs
//returns the minimum int of all the values in m[]
{
int min = 0;
assert(sizeDist > 0);
if(sizeDist > 0)
{
min = m[0];
for(int i = 1; i <sizeDist; i++)
{
if(m[i] < min)
{
min = m[i];
}
}
}
return min;
}
static void substring(char a[],char b[],int pos)
//recieves two strings from levenshtein()
//makes b[] into a substring of a[], from position 1 in a[] to the
end of a[]
//equivalent to Java's String method substring(int)
//only works when pos is 1, specific to the java version substring
input
//does not return anything
{
while(a[pos] != '\0') //start at the position given from
levenstein()
{
b[pos-1] = a[pos]; //since we want b[] to start at 0, pos - 1
pos++;
}
b[pos-1] = '\0'; //have to add in the null terminator at the end of
the substring b[]
}
static int lengthString(char a[])
//gets the length of a given string
//does ot include the null terminator
//was using strlen at first, but since strlen returns a long
it...
//...didnt work very well with the majority of other types
(int)
{
int count = 0;
while(a[count] != '\0')
{
count++;
}
return count;
}
#define T 1; //Define True = 1
#define F 0; //Define False= 0
static int endsWith(char a[], char b[])
//checks if the arrays are equal
//equivalent to java's endsWith() method
{
int i = 0;
int equals = T;
while((a[i+1] != '\0') && (b[i] != '\0'))
{
if(a[i+1] != b[i]) //a[i+1] is used because b[] is (at this point)
a...
{ //...substring of a[], which holds on less value than
a[]...
equals = F; //...compensating for int i being at the start of
b[]
}
i++;
}
return equals;
}
static int levenshtein(char s[],char t[])
//recieves strings s[] and t[] from testDistance() to compute
moves
{
int cost;
int distance;
char deleteS[strlen(s)];
char deleteT[strlen(t)];
if(strlen(s) == 0)
{
distance = (int)strlen(t);
}
else if(strlen(t) == 0)
{
distance = (int)strlen(s);
}
else
{
if(s[0] == t[0])
{
cost = 0;
}
else
{
cost = 1;
}
substring(s,deleteS,1); //substring is called here with pos =
1
substring(t,deleteT,1); //substring is called here with pos =
1
int ds = lengthString(deleteS); //ds stands for deleteSLength
int dt = lengthString(deleteT); //dt stands for deleteTLength
int sLenght = lengthString(s);
int tLenght = lengthString(t);
assert(ds == (sLenght-1)); //checking deleteSLength is s[] length
minus 1
assert(dt == (tLenght-1)); //checking deleteTLength is t[] length
minus 1
assert(endsWith(s,deleteS)); //endsWith check function called
here
assert(endsWith(t,deleteT)); //endsWith check function called
here
int d0 = levenshtein(deleteS, t) + 1; //I put each recursion call
into its own...
int d1 = levenshtein(s, deleteT) + 1; //...variable for more
organization and...
int d2 = levenshtein(deleteS, deleteT) + cost; //... easier
debugging
int dist[] = {d0,d1,d2};
distance = minimum(dist,DIST_SIZE);
}
return distance;
}
static void testDistance(char s[],char t[], int expected)
{
int distance = levenshtein(s, t);
if(distance == expected)
{
printf("Passed! You can get from '%s' to '%s' in %d
moves.",s,t,expected);
printf("\n");
}
else
{
printf("Failed: i thought it would take %d moves, but apparently it
takes %d moves to get from '%s' to
'%s'.",expected,distance,s,t);
printf("\n");
testsFailed++;
}
testsExecuted++;
}
int main()
{
printf("Testing typical cases.\n" );
testDistance( "kitten", "kitten", 0 );
testDistance( "kitten", "sitting", 3 );
testDistance( "kitten", "mittens", 2 );
testDistance( "balloon", "saloon", 2 );
testDistance( "hello", "doggo", 4 );
testDistance( "\t\thi", "\t\t\t\thi", 2 );
printf( "\nTesting empty/edge cases.\n" );
testDistance( "", "", 0 );
testDistance( "hello", "", 5 );
testDistance( "", "doggo", 5 );
testDistance( "a", "b", 1 );
testDistance( "b", "b", 0 );
testDistance( " ", " ", 0 );
printf( "\nThis might take a while...\n" );
testDistance( "12345678901", "123456789012", 1 ); // how many chars
are we looking at?
printf( "\nThese tests will not succeed in the C version\n"
);
testDistance( "kitten", "mitten\0s", 3 ); // ????
testDistance( "\0totally", "\0different", 9 );
printf( "\nTotal number of tests executed: %d",testsExecuted
);
printf("\n");
printf( "Number of tests passed: %d", testsExecuted -
testsFailed);
printf("\n");
printf("Number of tests failed: %d",testsFailed);
printf("\n");
printf("Program completed normally.\n");
return 0;
}
Output Screenshots:
Hope it helps, if you like the answer give it a thumbs up. Thank you.
Question 2: Levenshtein Take the recursive Java program Levenshtein.java and convert it to the equivalent C...
(20 pts) Fill in the missing code: This recursive method returns “even” if the length of a give String is even, and “odd” if the length of the String is odd. public static String foo(String s) { if (s.length() ==0) return “even”; else if (s.length() = = 1) return “odd”; else //your code goes here } (40 pts) You coded the following in the file Test.java : System.out.println( foo(5)); //more code here public static int foo(int n)...
need help editing or rewriting java code, I have this program running that creates random numbers and finds min, max, median ect. from a group of numbers,array. I need to use a data class and a constructor to run the code instead of how I have it written right now. this is an example of what i'm being asked for. This is my code: import java.util.Random; import java.util.Scanner; public class RandomArray { // method to find the minimum number in...
How can I make this program sort strings that are in a text file and not have the user type them in? I need this done by 5:00 AM EST tommorow please. import java.util.*; public class MergeDemo { public static void main(String args[]) { Scanner input=new Scanner(System.in); System.out.print("How many lines to be sorted:"); int size=input.nextInt(); String[] lines=new String[size]; lines[0]=input.nextLine(); System.out.println("please enter lines..."); for(int i=0;i { lines[i]=input.nextLine(); } System.out.println(); System.out.println("Lines Before Sorting:"); System.out.println(Arrays.toString(lines)); mergeSort(lines); System.out.println(); System.out.println("Lines after Sorting:"); System.out.println(Arrays.toString(lines)); } public...
Java class quiz need help~ This is the Backwards.java code. public class Backwards { /** * Program starts with this method. * * @param args A String to be printed backwards */ public static void main(String[] args) { if (args.length == 0) { System.out.println("ERROR: Enter a String on commandline."); } else { String word = args[0]; String backwards = iterativeBack(word); // A (return address) System.out.println("Iterative solution: " + backwards); backwards = recursiveBack(word); // B (return address) System.out.println("\n\nRecursive solution: " +...
10. What prints when the following code is executed? public static void main (String args) "Cattywampus"; for (int i-s.length )-1 i> 0 i-2) if (s.charAt (i)a') System.out.print(""); ] else if (s.charAt (i)'t') System.out.print (s.charAt (i-2)) i+ti else System. out. print (s . charAt (İ) ) ; if (i<2) System.out.print ("y"); System.out.println () 10. What prints when the following code is executed? public static void main (String args) "Cattywampus"; for (int i-s.length )-1 i> 0 i-2) if (s.charAt (i)a') System.out.print(""); ]...
Explain this java code, please. import java.util.Scanner; public class Program11 { public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); final int maxSize = 128; String[] titles = new String[maxSize]; int[] lengths = new int[maxSize]; int numDVDs = 0; String op; op = menu(stdIn); System.out.println(); while (!op.equalsIgnoreCase("q")) { if (op.equalsIgnoreCase("a")) { if (numDVDs < maxSize) numDVDs = addDVD(titles, lengths, numDVDs, stdIn); } else if (op.equalsIgnoreCase("t")) searchByTitle(titles, lengths, numDVDs, stdIn); else if (op.equalsIgnoreCase("l")) searchByLength(titles, lengths, numDVDs, stdIn); System.out.println('\n');...
Complete java program below. Complete non-recursive version nthFibonacciWithLoop() method. Complete recursive version nthFibonacciWithRecursion() method. public class Fibonacci { // Fib(N): N N = 0 or N = 1 // Fib(N-1) + Fib(N-2) N > 1 // For example, // Fib(0) = 0 // Fib(1) = 1 // Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1 // Fib(3) = Fib(2) + Fib(1) = Fib(2) + 1 = (Fib(1) + Fib(0)) + 1 = 1 + 0 + 1...
Help with a question in Java: What is the output from the following program? public class Methods2 { public static void main(String[] args) { for (int i = 0; i < 3; i++) { for (int j = 0; j <= i; j++){ System.out.print(fun(i, j) + "\t"); } System.out.println(); } } static long fun(int n, int k) { long p = 1; while (k > 0){ p *= n; } return p; } }
JAVA Write a method that accepts a String as an argument. The method should use recursion to display each individual character in the String. Then, modify the method you just wrote so it displays the String backwards. The following code does not correctly display the String backwards. It merely moves the first character of the String to the end: public static void displayCharacter(String s) { if(s.length() == 0) return; else ...
JAVA HELP: Directions Write a program that will create an array of random numbers and output the values. Then output the values in the array backwards. Here is my code, I am having a problem with the second method. import java.util.Scanner; import java.util.Random; public class ArrayBackwards { public static void main(String[] args) { genrate(); print(); } public static void generate() { Scanner scanner = new Scanner(System.in); System.out.println("Seed:"); int seed = scanner.nextInt(); System.out.println("Length"); int length = scanner.nextInt(); Random random...