Algorithm Analysis: Time Complexity, Binomial Distribution, and Code

This assignment presents an analysis of algorithms, focusing on time complexity and the binomial distribution. The solution includes an evaluation of the time complexity of a printing algorithm, demonstrating its linear time complexity. Furthermore, it provides a Java code example to calculate binomial distributions, including methods for computing combinations and generating the distribution itself. The code handles potential issues with large numbers by using double-precision floating-point values and ensures accuracy in the calculations. The assignment showcases practical applications of theoretical concepts in computer science, offering insights into algorithm efficiency and statistical distributions.

Answer – 7
Studying the Print Algorithm, we see that,
 For evaluation, we will count the number of accesses to array P[i][j].
 Let there be two vertex, q and r. The path between q and r has worst case “n-1” edges (where n
is number of vertices in graph).
 For every n-1 edges P[i][j] is calculated 4 times, so worst case is 4 (n-1), which is linear
complexity. In overall complexity is O(n).
Answer – 4
Int bin2 (int n, int k){
Int B[0….k];
B[0] = 1;
For(int i=1; i<= n; i++){
For(int j = minimum(I,k); j>0;j--){
B[j] = B[j] + B[j-1]
}
}
Return B[k];
}
We don’t need to sore the 2-d values to compute single value. Just the previous row values will be
enough to proceed further.
Answer – 3
public class Util{
// find the binomial distribution
// ret[0] stores the number user given
// ret[1] stores the count of the corresponding number in ret[0] with the
// same index
// for some number, the count maybe 0.
// the parameter validation must be finished in advance

public static long[][] getBinomialDistribution(int min, int max, long total)
{
Random rand = new Random(System.currentTimeMillis());
int n = max - min;
long[][] ret = new long[2][n + 1];
int mean = (n + 1) / 2;
float p = 1;
if (n > 0) {
p = (float) mean / (float) n;
}
long count = 0;
for (int i = 0; i <= n; i++) {
double p_i = comb(n, i) * Math.pow(p, i)
* Math.pow((1 - p), (n - i));
long count_i = (long) (total * p_i);
ret[0][i] = i + min;
ret[1][i] = count_i;
count += count_i;
}
while (count < total) {
int i = rand.nextInt(n + 1);
ret[1][i]++;
count++;
}
return ret;
}
// finding the comb
// values must be store in double, as they can be large
public static double comb(int n, int k) {
double ret = 1;
while (k > 0) {
ret = ret * ((double) n / (double) k);
k--;
n--;
}
return ret;
}
}