Please help
Question 1
In computer science, a program is called ____ if it is impossible to solve it with a polynomial-time algorithm.
(A) intractable
(B) complex
(C) greedy
(D) transposable
When searching an array with 1,048,576 elements, how many comparisons will there be (at most) using binary search?
A) 8
B) 11
C) 21
D) 33
Which of the following problems has been proven not to have a polynomial-time solution?
A) Halting problem
B) chained matrix multiplication problem
C) sorting problem
D) shortest paths problem
Algorithms with time complexities such as n and 100n are called ____ algorithms.
A) linear-time
B) simple
C) first-order
D) one-to-one
It takes about ____ bits to encode a positive integer x in binary.
A) [lg x]
B) [lg x] + 1
C) x
D) x2
Question 2
Analyze the following algorithm S and provide its worst case time complexity measures.
Data is a global array of n elements of type keytype. Initial call to S is made:
S(0, n)
public static void S (index i, index j) {
index p;
if (j > i) {
p = subAlgoS (i, j);
S (i, p - 1);
S (p + 1, j);
}
}
public static void subAlgoS (index i, index j) {
index x, y, p;
keytype z;
z = Data[i];
y = i;
for (x = i + 1; x <= j; x++)
if (Data[x] < z) {
y++;
exchange Data[x] and Data[y];
}
p = y;
exchange Data[i] and Data[p];
return p;
}
Try to estimate average case performance and comment on the space complexity of the algorithm.
Question 3: Find the Big-Theta Complexity measures of the following recurrence relations:
T(n) = T(n/2) + 3n2 and T(1) = 5
T(n) = 4 T(n-1) + n4 + 2100 and T(1) = 100
Question 4: (20 points) Complete the following statements. Wherever applicable, assume the problem refers to which is a proper binary tree.
A tree T with 8 internal nodes will have __ external nodes, and __ total nodes.
The maximum number of external nodes in a tree with height of 5 will be __ and the maximum number of total nodes will be ____.
If a tree has 65 nodes altogether (i.e. total of internal and external nodes), its minimum and maximum height will be between min =___and max = ___.
Total number of nodes in a proper binary tree is always an (____ / odd) number.
If an expression tree contains 4 operators, it will contain_____ operands.
If an expression tree contains 4 operands, the number of possible expression tree topologies will be ______.
The height of the root node in a binary tree is ______.