1. How to find median of a BST?

Find the no. of elements on the left side.
If it is n-1 the root is the median.
If it is more than n-1, then it has already been found in the left subtree.
Else it should be in the right subtree.

2. Define string in an algorithmic notation and an example to support it?

In the algorithmic notation, a string is expressed as any sequence of characters enclosed in single quote marks.
E.g. a single quote contained within a string is represented by two single quotes. Therefore, the string “It is John`s program.” is represented as ‘IT IS JOHN”S PROGRAM.'.

3. What are the two ways through which the Markov algorithm terminates?

A Markov algorithm terminates in one of the two ways.
1) The last production is not applicable
2) A terminal production is applicable
A terminal production is a statement of the form x map to y., where x and y represent the strings in V* and the symbol “.” Immediately follows the consequences.

4. What is the general strategy for Markov Algorithm?

The general strategy in a Markov Algorithm is to take as input a string x and, through a number of steps in the algorithm, transform x to an output string y. this transformation process is generally performed in computers for text editing or program compilation.

5. The most basic tool used to express generating functions in closed form is the closed form expression for the geometric series, which is an expression of the form a+ar+ar2+-------+arn. It can either be terminated or extended indefinitely. What are the restrictions for this geometric series?

If a and r represents numbers, r must not equal1 in the finite case.In the infinite case the absolute value of r must be less than 1.These restrictions don't come into play with Generating functions.

6. Name any three skills which are very important in order to work with generating functions.

The three most important skills which are used extensively while working with generating functions are
1)Manipulate summation expressions and their indices.
2)Solve algebraic equations and manipulate algebraic expressions, including partial function decompositions.
3)Identify sequences with their generating functions

7. Explain about the algorithm ORD_WORDS?

This algorithm constructs the vectors TITLE, KEYWORD and T_INDEX.

8. Explain the function of KWIC_Create?

This algorithm analyses the input phrases and creates the three arrays needed in procedure KWIC_GEN.

9. What is the general algorithm model for any recursive procedure?

Prologue: -Saves the parameters, local variables and returns addresses.
Body: -If the best criterion has been reached: then perform the final computation and go to step3, otherwise, perform the partial computation and go to step1.
Restore the most recently saved parameters, local variables and return address. Go to this return addresses.

10. Give the difference of format between an algorithm and a sub algorithm?

The format used is the same as for algorithms except that a return statement replaces an exit statement and a list of parameters follows the sub algorithms name. Although sub algorithms may invoke each other and that a sub algorithm may also invoke itself recursively

Download Interview PDF