Exercise 1: Computing Binomial Coefficients The binomial coefficient is defined
ID: 3873002 • Letter: E
Question
Exercise 1: Computing Binomial Coefficients The binomial coefficient is defined as) Java to compute the binomial coefficient, given n and k n! , o k n. Implement the following method in public static long binomCoeff(int n, intk)f. . . ) Your method must compute the correct answer for any inputs in the range 0Sn 60, 0 Sks 60 for0 s k s n. Check that your code correctly computes(3)9132290782430712. Note that the largest positive integer that can be represented in Java (using primitive types) is a long type with value 263 1 and note that 60! is larger than this value. Useful identities to use for formulating a solution are n! t for0 sk sn You should aim to implement your method using no more than 8 Java statements or less (if), else, forwhile etc. each count as one statement). You should use an iterative, nota recursive, solution. Use only long variables in the implementation (not double or float). Q. What is the time complexity of your algorithm (in terms of n and/or k)?Explanation / Answer
Exercise-1)
class BinomCoefficient
{
// Returns value of Binomial Coefficient C(n, k)
static long binomCoeff(int n, int k)
{
int C[][] = new int[n+1][k+1];
int i, j;
// Calculate value of Binomial Coefficient in bottom up manner
for (i = 0; i <= n; i++)
{
for (j = 0; j <= min(i, k); j++)
{
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previosly stored values
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
return C[n][k];
}
// A utility function to return minimum of two integers
static int min(int a, int b)
{
return (a<b)? a: b;
}
/* Driver program to test above function*/
public static void main(String args[])
{
int n = 59, k = 30;
System.out.println("Value of C("+n+","+k+") is "+binomialCoeff(n, k));
}
}
------------------------------------------------------------------------------------------------------------------------------------------
Exercise-2)
class BinarySearch
{
// Returns index of key if it is present in a[], else
// return -1
int findIndexOf(int a[], int key)
{
int l = 0, r = a.length - 1;
while (l <= r)
{
int m = l + (r-l)/2;
// Check if key is present at mid
if (a[m] == key)
return m;
// If key greater, ignore left half
if (a[m] < key)
l = m + 1;
// If key is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, the element was not present
return -1;
}
-------------------------------------------------------------------------------------------------------------------------------------------
// Driver method to test above
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int a[] = {2, 3, 4, 10, 40};
int n = a.length;
int x = 10;
int result = ob.binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index "+result);
}
}
------------------------------------------------------------------------------------------------------------------------------------------------
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.