Algorithm Questions part - I
Explain the function of KWIC_Create?
Answer: This algorithm analyses the input phrases and creates the three arrays needed in procedure KWIC_GEN.
What is sub matrix?
Answer: Sub Matrix is a matrix in which you have given an n*n square matrix where each element is either 0 or 1...you have to find the square sub_matrix with the largest length such that all the elements along the border of that square sub_matrix matrix is 1
To calculate distance between two text strings
Give an algorithm that calculates the distance between two text strings (only operations you can have are: delete, add, and change, one by one)
Answer: Let's think about the string as a vector with coordinates represented by each character ASCII value, i.e.
1st string (str1): (x1, x2, ..., xm)
where
x1 = str1[0], x2 = str1[1], ..., xm = str1[m-1]
2nd string (str2): (y1, y2, ..., yn)
y1 == str2[0], y2 == str2[1], ..., yn=str2[n-1]
Assume that m
In this case the distance beween str1 and str2:
D(str1, str2) = [(x1-y1)^2 + (x2-y2)^2 + ... + (xm-ym)^2 + y(m+1)^2 + ....
+ y(n-1)^2 + yn^2]^(1/2)
Name any three skills which are very important in order to work with generating functions.
Answer: 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
Implement an algorithm that takes two strings as input, and returns the intersection of the two, with each letter represented at most once. Speed it up and test it.
Answer: Assuming that the two strings are not sorted, but they could be sorted by ASCII coding or other means.
Let A and B denote two strings.
If the strings are not sorted, then the search of A[i], 0 <= i < |A|, will take |B| unit of time long. Which means this algorithm cannot be faster than O(|A| * |B| )
However, by using an appropriate sorting algorithm, (e.g: quick sort, built-in in C) the search time could be reduced dramatically.
To find the intersection, one begins by comparing the head elements of the two strings. Here is the pseudo code.
i = 0;
j = 0;
k = 0;
while( i < |A| && j < |B| )
{
if( A[i] == B[i] )
{
Results[k] = A[i];
++k;
advance(A, i);
advance(B, j);
}
// Assuming the strings are sorted in incrementing order
if( A[i] > B[i] )
{
advance(B, j);
}
else /* B[i] > A[i] */
{
advance(B, i);
}
}
return Results
void advance(string& Str, int& idx)
{
/* Just to advance the pointer beyond the consecutive repeated letters. */
while( Str[idx] == Str[idx+1] ) idx++;
}
In this algorithm I proposed, running time is O( |A| + |B| + |A| log |A| + |B| log |B| ),
or O( n log n), somewhere around that.
If you still want an even faster algorithm, use a hash.
Hash A into a map, and then search for B.
Depending on the hash function and table size, if the collision was minimized, the running time could be as good as O ( |A| + |B| )
The only concern is the insertion time when hashing A into the map. Probably a bookkeeping variable is required somewhere for the look-up of letters in B, but that's a secondary concern.
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?
Answer: 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.
Algorithm Questions part - II
What is the general strategy for Markov Algorithm?
Answer: 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.
How can you traverse a matrix of m lines and n columns in a zig-zag way?
m = 3, n = 4
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
Output: a11 a21 a12 a31 a22 a13 a32 a23 a14 a33 a24 a34
Answer: If space is not limited, we can use a open hash table.
1. the hash key will be the i + j (col + row).
2. We firstly insert each matrix element in a column, eg. 11, 21,31,12,....... for 3x4 matrix in the example
3. where there is same hash key, the element is added as a queue
4. in 2nd example, the hash table will look like:
     2: a11
     3: a21, a12
     4: a31, a22, a13
     5: a32, a23, a14
     6: a33, a24
     7: a34
After the hash table, the solution is obvious now. We can simply read the table from key 2 - 7 in order. The elements have already ordered as well. To build this hash table, we only need
O(n) time which is a good linear speed.
What are the two ways through which the Markov algorithm terminates?
Answer: 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.
In other word we have one more solution
#include
#include
using namespace std;
int main(int argc, char *argv[])
{
int m, n;
cout << "Enter height of matrix" << endl;
cin >> m;
cout << "Enter width of matrix" << endl;
cin >> n;
int i = 1;
int j = 1;
while( (j + i ) <= (m + n) )
{
while ( j > 0 && i > 0 && j <= n && i <= m)
{
cout << "a" << i << j << " ";
i -= 1;
j += 1;
}
i += j;
j = 1;
if( i >= m )
{
j += i - m;
i = m;
}
}
system("PAUSE");
return EXIT_SUCCESS;
}
it's only that I used a while loop instead of a for loop. (loops.)
Either way, this algorithm runs in O (m * n), I really doubt that there exists any method that runs faster.
As per hash table or other external storage or even recursion, I don't think they are cheaper than simply using two variables... (j and i )
Write an algorithm to find the minimum of numbers where N is any arbitrary natural number. N is given to you by the user as the first value.
Answer: Algorithm smallest number
Input: N, any arbitrary natural number within which the smallest number should be found
Output: Smallest number
Min <- I0
While I < N do
if I < Min then min <- I
Increment I by 1
Loop
return Min
Define string in an algorithmic notation and an example to support it?
Answer: 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.’.
Algorithm Questions part - III
Define and state the importance of sub algorithm in computation and its relation ship with main algorithm?
Answer: A sub algorithm is an independent component of an algorithm and for this reason is defined separately from the main algorithm. The purpose of a sub algorithm is to perform some computation when required, under control of the main algorithm. This computation may be performed on zero or more parameters passed by the calling routine.
How can we multiply an integer by 7 by using bitwise operators?
Answer: 7 = 1+2+4, so we can do one left shift and then one more left shift and add these two numbers to the original number to get multiplied answer.
There are numbers from 1 to N in an array. Out of these, one of the numbers gets duplicated and one is missing. The task is to find out the duplicate number. Conditions: you have to do it in O (n) time without using any auxiliary space (array, bit sets, maps etc..).
Answer: Use one for loop to sort the array the running-time would be O(n) and after the for loop finished, use another for loop to test the item who have the same value as the previous one or post one, the worst O of the second loop is O(n) so together, they are still O(n).
Give the difference of format between an algorithm and a sub algorithm?
Answer: 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
How can we create different functionality to objects of a same class?
Answer: What is the necessity for doing it? If you want an object to have all the features of a class + something more or something less, all you need to do is create another class inheriting the other. To incorporate this we have inheritance, isn’t it? I don't think you can incorporate any further functionality to an object apart from the ones defined in the class.
How do display the output as reverse of input, like input is "This is a hat" and the output should be "hat a is this"?
Answer: This is a simple program to reverse the string entered. The string will be reversed till enter key is pressed.
void main()
{
char c;
if((c = getchar()) != 'n')
{
main();
}
putchar(c);
}
What is the general algorithm model for any recursive procedure?
Answer: 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.
a(x) + a(y) = M Given a1, a2, .... a(n) integers & M, return true or false if there exist a(x) + a(y) = M
Once you're done, do it using a hash table.
Answer: actually using a hash there is a better solution. You initiate the hash with all values from a. and then you go over a again and check if the complementary of a[j] ie M-a[j] is in the hash. This way the complexity is O(n) and not O(M+n)
You are almost there.
consider the following algorithm
for( i = 0 ; i < n ++ i)
{
diff = M - a(i);
if ( search( a(i), hash ) ) /* see if a(i) is in the hash table */
{
return true; /* if found, return true */
}
else
{
insert( diff, hash); /* if not found, insert the complementary of a(i) in the table */
}
}
so that you only have to go through list a() once to accomplish the task.
If the list contains the objective, you don't even have to see the end of the a list ;)
Algorithm Questions part - IV
What is the difference between instance (per object) and static (shared by all objects) in report while declaring global variable?
Answer: In case of instance per object every instance has its own memory space but in case of static variable every instance access same memory space for that variable.
What are the arguments present in pattern matching algorithms?
Answer: These are the following arguments which are present in pattern matching
Algorithms.
1) Subject,
2) Pattern
3) Cursor
4) MATCH_STR
5) REPLACE_STR
6) REPLACE_FLAG
What is the difference in Searching and Sorting?
Answer: Searching is to search the element in the given list, whereas Sorting is to arrange the given list in a particular order (ascending or descending order)
Explain the function SUB in algorithmic notation?
Answer: In the algorithmic notation rather than using special marker symbols, generally people use the cursor position plus a substring length to isolate a substring. The name of the function is SUB.
SUB returns a value the sub string of SUBJECT that is specified by the parameters i and j and an assumed value of j.
Given a system of N equations whose coefficient matrix A is triangular and is stored in a vector R and the right hand side vector B, this algorithm obtains the solution vector X. Sum is a temporary variable. I am M are integer variables. How to follow the algorithm?
Answer: The algorithm is easy to follow. X1 is first computed from the first equation and then substituted in the second to obtain X2 and so on.
Another common application is one in which most of the elements of a large matrix are zeros. In such a case, only the non zero elements need to be stored along with their row and column sub scripts.
Define and describe an iterative process with general steps of flow chart?
Answer: There are four parts in the iterative process they are
Initialization: -The decision parameter is used to determine when to exit from the loop.
Decision: -The decision parameter is used to determine whether to remain in the loop or not.
Computation: - The required computation is performed in this part.
Update: - The decision parameter is updated and a transfer to the next iteration results.
State recursion and its different types?
Answer: Recursion is the name given to the technique of defining a set or a process in terms of itself. There are essentially two types of recursion. The first type concerns recursively defined function and the second type of recursion is the recursive use of a procedure.
How can an inductive definition be realized?
Answer: An inductive definition of a set can be realized by using a given finite set of elements A and the following three clauses.
1) Basis Clause
2) Inductive clause
3) External clause
Explain about procedural body and computation boxes?
Answer: The procedural body contains two computation boxes namely, the partial and final computational boxes. The partial computation box is combined with the procedure call box. The test box determines whether the argument value is that for which explicit definition of the process is given.
Explain the depth of recursion?
Answer: This is another recursion procedure which is the number of times the procedure is called recursively in the process of enlarging a given argument or arguments. Usually this quantity is not obvious except in the case of extremely simple recursive functions, such as FACTORIAL (N), for which the depth is N.
State the problems which differentiate between recursive procedure and non-recursive procedure?
Answer: A recursive procedure can be called from within or outside itself, and to ensure its proper functioning, it has to save in same order the return address so that it return to the proper location will result when the return to a calling statement is made. The procedure must also save the formal parameters, local variables etc.
0 comments:
Post a Comment