Programming and data structure miscellaneous
- A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array f[0...m] with all elements initialized to 0.
(a) Fill in the boxes with expressions/statements to make fib() store and reuse computed Fibonacci values. Write the box number and the corresponding contents in your answer book.
(b) What is the time complexity of the resulting program when computing fib(n)?
-
View Hint View Answer Discuss in Forum
(a) (1) f[n]! = 0
or
Expression like f(n)3 0 etc.
(2) f[n]
(3) f[n] = t
(b) O(n) or (n + 1)
Alternately 0 (n3) in the log-cost model.Correct Option: A
(a) (1) f[n]! = 0
or
Expression like f(n)3 0 etc.
(2) f[n]
(3) f[n] = t
(b) O(n) or (n + 1)
Alternately 0 (n3) in the log-cost model.
- Suppose you are given arrays p[1 ...N] and q[1...N] both uninitialized that is, each location may contain an arbitrary value), and a variable count, initialized to 0. Consider the following procedures set and iset :
Set (i) {
count = count + 1;
q [count] = i;
p[i] = count;
}
is_set(i) {
if (p[i] ≤ 0 or p[i] > count)
return false;
if (q[p[i]] ≠ i)
return false;
return true;
}
(a) Suppose we make the following sequence of calls: set (7); set (3); set(9); After these quence of calls, what is the value of count, and what do q[1], q[2], q[3], p[7], p[3] and p[9] contain?
(b) Complete the following statement “The first count elements of ................ contain values i such that set (....................) has been called”.
(c) Show that if set (i) has not been called for some i, then regardless of what p[i] contains, is_set (i) will return false.
-
View Hint View Answer Discuss in Forum
(a) Count = 3
q[1] = 7 q[2] = 3, q[3] = 9
p[7] = 1 p[3] = 2, p[9] = 3
(b) The first count elements of q contain values (i) such that set (i) has been called.
(c) Suppose p[i] has a value < = 0 or > count, then to set (i) return false.
Otherwise consider q[p[i]]. Using (b), q[p[i]] contains a value (i) such that set (i) has been called. Since set (i) has not been called, q[p[i]] cannot be equal to (i) and is set (i) returns false.Correct Option: D
(a) Count = 3
q[1] = 7 q[2] = 3, q[3] = 9
p[7] = 1 p[3] = 2, p[9] = 3
(b) The first count elements of q contain values (i) such that set (i) has been called.
(c) Suppose p[i] has a value < = 0 or > count, then to set (i) return false.
Otherwise consider q[p[i]]. Using (b), q[p[i]] contains a value (i) such that set (i) has been called. Since set (i) has not been called, q[p[i]] cannot be equal to (i) and is set (i) returns false.
- Suppose you are given an array s[1....n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 ≤ k ≤ n :
reverse (s, 1, k);
reverse (s, k + 1, n);
reverse (s, 1, n);
-
View Hint View Answer Discuss in Forum
From the given conditions it can be clearly concluded that, the given sequence rotates s left by k positions.
Correct Option: A
From the given conditions it can be clearly concluded that, the given sequence rotates s left by k positions.
- The following C declarations
struct node {
int i:
float j;
}
struct node * s [10];
define s to be
-
View Hint View Answer Discuss in Forum
From the given declaration, it is obtained that s is an array denoted by s[10], containing 10 elements which are pointers indicated by the symbol, *, to structure of type node as defined by struct node statement.
Correct Option: A
From the given declaration, it is obtained that s is an array denoted by s[10], containing 10 elements which are pointers indicated by the symbol, *, to structure of type node as defined by struct node statement.
- Following declaration of a two-dimensional array in C.
Char a [100] [100];
Assuming that the main memory is byte addressable and that the array is stored starting from memory address 0, the address of a [40] [50] is
-
View Hint View Answer Discuss in Forum
Given is a [40] [50].
In a [40] [50],
Row = 40
Column = 50
The address is 4050.Correct Option: B
Given is a [40] [50].
In a [40] [50],
Row = 40
Column = 50
The address is 4050.
