Explore topic-wise InterviewSolutions in .

Correct option is (d) 2^55

The explanation is: Depth-first SEARCH (DFS) algorithm of a binary tree, is a trivial example of short-circuiting. We can have a standard RECURSIVE algorithm in CASE of DFS. Now, a perfect binary tree of HEIGHT h has 2^h+1 Null pointers as children.

h = 54

2^54+1

2^55.

The correct option is (a) corecursive function

Easiest explanation: The generatively recursive functions or corecursive functions is defined as generation of the NEW data at each step that is successive APPROXIMATION in Regula Falsi method. In terms of loop variants, there is no such loop variant, and termination DEPENDS on error of approximation.

Correct choice is (B) Tower of Hanoi

To explain: We can have recurrence RELATION for tower of hanoi and that is hn = 2 hn-1 + 1h1 = 1, for n NUMBER of disks in one peg.

The correct option is (a) Structurally recursive function

To explain I would say: A structurally recursive function has a characteristic that the argument to each recursive call is the content of a FIELD of the ORIGINAL input. This recursion function includes mostly all TREE traversals which includes binary tree creation and search, XML processing ETC.

The CORRECT choice is (a) indirect recursion

To EXPLAIN: When a function is not called by itself but by ANOTHER function which it has called either directly or INDIRECTLY is termed as Indirect recursion. Mutual recursion is a more symmetric term of Indirect recursion.

Right OPTION is (C) multiple recursion

Best explanation: A recursion which consists of multiple self-references and requires exponential time and space is called multiple recursion. Multiple recursions include TREE traversal of a graph, such as in a depth-first search. However, SINGLE recursion is more efficient than multiple recursion.

Right CHOICE is (b) 2

Explanation: There are TWO types of self-referential definitions and these are inductive and coinductive definitions. An inductively defined recursive data definition MUST have to SPECIFY how to CONSTRUCT instances of the data. For example, linked lists are defined as an inductively recursive data definition.

Right OPTION is (a) Bellman equation

The best I can explain: DYNAMIC programming can LEAD to recursive optimization that can restate a multistep optimization problem in its recursive form. The Bellman equation that writes the VALUE of the optimization problem at an earlier time in terms of its value at a LATER time is the result of dynamic programming.

Correct ANSWER is (d) P(n)

The best I can EXPLAIN: By induction, we can prove that P(n) is TRUE.

Correct answer is (a) P(3)

To EXPLAIN: By induction we can PROVE that P(3)is TRUE but we can’t CONCLUDE about P(2), p(6) and P(4).

The CORRECT OPTION is (a) 27

The explanation is: We can form 27 cent of postage with NINE 3-cent stamp and 20-cent postage can be formed by using two 10-cent STAMPS.

Right ANSWER is (b) False

Easiest EXPLANATION: By USING two 4-cent stamp and one 11-cent stamp, 27-cent POSTAGE is PRODUCED.

The CORRECT answer is (d) 10

Explanation: We can FORM 30 CENT of POSTAGE with two 4-cent stamp and two 11-cent stamp.

Right answer is (a) True

The best explanation: We can form 8 cent of POSTAGE with one 3-cent STAMP and one 5-cent stamp. P(10) is true because we can form it using two 5-cent STAMPS.

Correct CHOICE is (b) 10

Easy EXPLANATION: A simple polygon with n sides can be triangulated into n-2 TRIANGLES, where n > 2.

Right choice is (a) True

The EXPLANATION: By USING STRONG INDUCTION.

Correct choice is (b) P(K) = m^(k) + 5

The BEST I can explain: By the principle of mathematical induction, if a statement is true for any number m = k, then for its successor m = k + 1, the statement also satisfies, PROVIDED the statement is true for m = 1. So, the required answer is p(k) = m^k + 5.

Right choice is (a) 64 > 9

The BEST explanation: Statement By PRINCIPLE of MATHEMATICAL induction, for n=2 the base case of the inequation 4^n+1 > (n+1)^2 should be 64 > 9 and it is TRUE.

The correct answer is (b) \(\frac{p*(p + 1)*(2p + 1)}{6}\)

The best explanation: By PRINCIPLE of mathematical INDUCTION, we now ASSUME that p (b) is true 1^2 + 2^2 + 3^2 + … + b^2 = \(\frac{b (b + 1) (2b + 1)}{6}\)

so to prove P(b+1): 1^2 + 2^2 + 3^2 + … + b^2 + (b + 1)^2 = \(\frac{b (b + 1) (2b + 1)}{6}\) + (b + 1)^2

By induction ASSUMPTION it is shown that 1^2 + 2^2 + 3^2 + … + b^2 + (b + 1)^2 = \(\frac{(b + 1) [(b + 2) (2b + 3)]}{6}\). Hence it is proved that 1^2 + 2^2 + 3^2 + … + p^2 = \(\frac{p*(p + 1)*(2p + 1)}{6}\).

Right choice is (a) m^2+3

To EXPLAIN: The REQUIRED answer is m^2+3. Now, by induction assumption, we have to PROVE 2+4+6+…+4(k+1) = (k+1)^2+3also can be TRUE, 2+4+6+…+4(k+1) = 2+4+6+⋯+(4k+4) and by the subsequent steps, we can prove that (m+1)^2+3 also holds for m=k. So, it is proved.

The correct choice is (a) induction hypothesis

Best explanation: The hypothesis of Step is a must for MATHEMATICAL induction that is the statement is true for n = k, where n and k are any NATURAL NUMBERS, which is also called induction assumption or induction hypothesis.

The correct option is (C) 343 > 27

For explanation I would SAY: By the principle of MATHEMATICAL induction, we have 7^3 > 3^3 ⇒ 343 > 27 as a BASE case and it is true for n = 3.