Algorithms Answers

Using JFLAP, create a PDA (pushdown automata) for the following two language(s):

L = {a^n b a^n | n > 0}
both are seperate
L = {a^i b^j c^k | i = j or i=k, i, j, k > 0}

Develop a nonrecursive algorithm for Algorithm 7-1, “Find Smallest Node
in a BST.”

1. Write an algorithm to add three numbers.

2. Write an algorithm to calculate the average of four numbers.

3. Write an algorithm that will read the two sides of a rectangle and calculate its area.

4. Write an algorithm to determine a student’s final grade and indicate whether it is passing or failing. The final grade is calculated as the average of four marks.

5. Write an algorithm for evaluation of equation:
Y = a (b - c)2 / d + 2

Prove or disprove the following: 

1. lg√n ∈ O(lg n) (√n means square root of n)

2. lg n ∈ O(lg√n) 

3. 2n+1 ∈ O(2n)


Prove the following using mathematical induction:
1. (ab)n = an bn for every natural number n
2. 13 +23+33+…+n3 = (1+2+3+…+n)2
3. 1+3+5+7+…+(2n-1) = n2

Prove that n + log2n = O(n) by showing that there exists a constant c > 0 such that n + log2n ≤ cn.
(note that log2n means (log n)2.)

1. Prove that n + log n = O(n) by showing that there exists a constant c > 0 such that n + log n ≤ cn.

Find the time complexity of the following algorithms in terms of Big O.
1) Time Complexity of a loop if the loop variables is divided / multiplied by a constant amount as follows:
for (int i = 1; i <=n; i *= c) {
// some O(1) expressions
}
2) Time Complexity of a loop if the loop variables is reduced / increased exponentially by a constant amount as follows:
// Here c is a constant greater than 1
for (int i = 2; i <=n; i = pow(i, c)) {
// some O(1) expressions
}
//Here fun is sqrt or cuberoot or any other constant root
for (int i = n; i > 0; i = fun(i)) {
// some O(1) expressions
}
3) What is the returned value of the following function?
int Fun(int n) {
int i, j, k = 0;
for (i = n/2; i <= n; i++)
for (j = 2; j <= n; j = j * 2)
k = k + n/2;
return k;
}

Find the time complexity of the following algorithms in terms of Big O.
1) A function (or set of statements) that doesn’t contain loop, recursion and call to any other non-constant time function.
2) A loop or recursion that runs a constant number of times, such as follows:
for (int i = 1; i <= c; i++) // Here c is a constant
{
// some O(1) expressions
}
3) A loop where the loop variables is incremented / decremented by a constant amount, as follows:
// Here c is a positive integer constant
for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}
4) Time complexity of nested loops as follows:
// Here c is a positive integer constant
for (int i = 1; i <=n; i += c) {
for (int j = 1; j <=n; j += c) {
// some O(1) expressions
}
}
//Or the following nested loop
for (int i = n; i > 0; i += c) {
for (int j = i+1; j <=n; j += c) {
// some O(1) expressions
}

Read 10 integers from the keyboard in the range 0 -100, and count how many of them are larger than 50, and display this result.