Google Search

Tuesday, July 14, 2009

OOP

Q.9: Distinguish between the following terms:
a. Object and classes
b. Data abstraction and data encapsulation
c. Inheritance and polymorphism
d. Dynamic binding and message passing
Ans: (a) Object: Objects are the basic runtime entities in an object oriented programming. An object is an instance of a class. It can be uniquely identified by its name and it defines a state which is represented by the values of its attributes at a particular time.
The state of the object changes according to the methods which are applied to it. We refer to these possible sequences of state changes as the behavior of the object.
Class: A class is the implementation of an abstract data type (ADT). It defines attributes and methods which implement the data structure and operations of the ADT, respectively. Instances of classes are called objects. Consequently classes define properties and behaviors of sets of object. Thus a class is a collection of objects of similar type and objects are variables of the type class.
(b) Data abstraction: Abstraction refers to the act representing essential features without including the background details or explanations. Classes use the concept of abstraction and are defined as a list of abstract attributes.
Data encapsulation: The wrapping up of data and functions into a single unit is known as encapsulation. The data is not accessible to the outside world and only those functions which are wrapped in the class can access it. These functions provide the interface between the objects data and the program. This insulation of the data from direct access by the program is called data hiding or information hiding. As a result data become secured. Thus the encapsulation reduces complexity.
(c) Inheritance: Inheritance is the process by which objects of one class acquire the properties of objects of another class.
Inheritance is the mechanism which allows a class A to inherit properties of a class B. We say ``A inherits from B''. Objects of class A thus have access to attributes and methods of class B without the need to redefine them.
The concept of inheritance provides the idea of reusability. This means that we can add additional features to an existence class without modifying it.
Polymorphism: Polymorphism means the ability to take more than one form. An operation may exhibit different behaviors in different instances. The behaviors depend upon the types and number of data used in the operation. The process of making an operator exhibit different behaviors in different instances is known as operator overloading.
(d) Dynamic binding: Binding refers to the linking of a procedure call to the code to be executed in response to the call. Dynamic binding / late binding means that the code associated with a given procedure call is not known until the time of the call of the run time. It is associated with polymorphism and inheritance.
Message passing: A message for an object is a request for execution of a procedure and therefore will invoke a function in the receiving object that generates the desired result. Message passing involves specifying the name of the object, the name of the function and the information to be sent.
Example:
Q.10: What kinds of things can become objects in OOP?
Ans: Object: Objects are the basic runtime entities in an object oriented programming. An object is an instance of a class. It can be uniquely identified by its name and it defines a state which is represented by the values of its attributes at a particular time.
The state of the object changes according to the methods which are applied to it. We refer to these possible sequences of state changes as the behavior of the object.

Monday, July 13, 2009

PROGRAMMING IN C++

Q. What are the phases of analysis and describe them.

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

13. What is dynamic programming? What is the difference between greedy method and dynamic programming?
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?

Friday, July 10, 2009