Google Search
Tuesday, July 14, 2009
OOP
Monday, July 13, 2009
PROGRAMMING IN C++
  Ans: Analysis of the source program: In compiling, analysis consists of three phases: --
- Linear analysis (Lexical Analysis)
 
- Hierarchical analysis (Syntax Analysis)
 - Semantic  analysis
 
Linear (Lexical)  analysis: In a compiler, linear analysis is called lexical analysis or  scanning. In this case, the stream of characters which make the source program  is read from left to right and generates the tokens which are sequences of  characters having a collective meaning.
Example: In lexical analysis, the characters in the  assignment statement
                                               position:=  initial + rate * 60
would be grouped into the following token ---
- The identifier position
 - The assignment symbol :=
 - The identifier initial
 - The plus sign
 - The identifier rate
 - The multiplication sign
 - The number 60
 
The blanks separating the characters of these tokens would  normally be eliminated during lexical analysis.
Hierarchical analysis / Parsing / Syntax  analysis: Hierarchical analysis is called parsing or syntax analysis.  In this case the tokens of the source program are grouped hierarchically into  grammatical parses that are used by the compiler to synthesize output. Usually,  the grammatical phrases of the source program are represented by a parse tree  as follows: --
The hierarchical structure of a program is usually expressed  by recursive rules. The rules of expression are as follows:--
- Any identification is an expression.
 - Any number is an expression
 - If expression1 and expression2 are expressions then so are
 
expression1 +  expression2
expression1 *  expression2
(expression1)
Semantic analysis: The semantic analysis phase checks the source program for semantic errors and  gathers type information for the subsequent code – generation phase. It uses  the hierarchical structure determined by the syntax analysis phase to identify  the operators and operands of expressions and statements. An important  component of semantic analysis is type checking.
Q. What is symbol table? What are the functions of symbol table?
Ans: Symbol table: A symbol table is  a data structure containing a record for each identifier with fields for the  attributes of the identifier. It is generally used to store information about  various source language constructs. The information is collected by the  analysis phases of the compiler and used by the synthesis phases to generate the  target code.
Q. Derive the parse tree from the statement “position: = initial + rate  * 60”.
Ans: At first the defined statement  should be grouped into tokens as above and then derive the parse tree as  follows: --

some questions
14. Write and explain the algorithm for greedy strategies for the knapsack problem.
15. Write the algorithm for BFS and DFS.
16. Describe the problem of OBST as dynamic programming.
17. What is the bounding function for subset problem?
18. Describe the travelling salespersons problem.
19. Describe the sum of subset problem.
20. Describe the 8 queen’s problem using backtracking method.
21. What do you know by graph coloring? Give the algorithm for graph coloring using backtracking method.
22. Write down and explain the algorithm for finding all m-colorings of a graph.
23. Define explicit and implicit constrains.
24. Differentiate between backtracking and branch & bound algorithm techniques.
25. What do you mean by LC search?
