SDE

Software Design Engineering

Coupling/Cohesion

 Software Design

• Software design is a creative process, just like designing anything else
  
• To see a wrong design, we can check with the requirements in the analysis model
  
• To see a bad design, we need to assess the design model and analyse the components, whether the performance can be improved by changing the modules or the interfaces

         In Analysing the software Design many factors are used, such as Coupling, Cohesion, Factoring, System Shape, etc.

 Coupling

• The degree of interdependence between two modules”
  
• We aim to minimise coupling - to make modules as independent as possible
  ​Low coupling can be achieve by:
• eliminating unnecessary relationships
• reducing the number of necessary relationships
• easeing the ‘tightness’ of necessary relationships

Types of Coupling

• Data coupling       (Most Required)   
                             
• Stamp coupling
   
• Control coupling
   
• Hybrid coupling
   
• Common coupling
   
• Content coupling  (Least Required)

Data Coupling 

• Modules communicate by parameters
   
• Each parameter is an elementary piece of data
   
• Each parameter is necessary to the communication
   
• Nothing extra is needed

Data coupling problems

• Too many parameters - makes the interface difficult to understand and possible error to occur
   
• Tramp data - data ‘traveling’ across modules before being used

Stamp coupling

• A composite data is passed between modules
   
• Internal structure contains data not used
   
• Bundling - grouping of unrelated data into an artificial structure

Control coupling

• A module controls the logic of another module through the parameter
   
• Controlling module needs to know how the other module works - not flexible!

Hybrid coupling

• A subset of data used as control
   
• Example: account numbers 00001 to 99999
  ​
• If 90000 - 90999, send mail to area code of last 3 digit (000 - 999)

Common coupling

• Use of global data as communication between modules
   
• Dangers of
• ripple effect
   
• inflexibility
   
• difficult to understand the use of data

Content coupling

• A module refers to the inside of another module
   
• Branch into another module
   
• Refers to data within another module
   
• Changes the internal workings of another module
   
• Mostly by low-level languages

 

Cohesion

• “The measure of the strength of functional relatedness of elements within a module”
   
• Elements: instructions, groups of instructions, data definition, call of another module
                                                                                                 ​
• We aim for strongly cohesive modules
  ​
• Everything in module should be related to one another - focus on the task
   
• Strong cohesion will reduce relations between modules - minimise coupling

      Types of Cohesion

• Functional cohesion (Most Required)
   
• Sequential cohesion
   
• Communicational cohesion
   
• Procedural cohesion
   
• Temporal cohesion
   
• Logical cohesion
   
• Coincidental cohesion (Least Required)

Functional cohesion

• All elements contribute to the execution of one and only one problem-related task
   
• Focussed - strong, single-minded purpose
   
• No elements doing unrelated activities
  ​
• Examples of functional cohesive modules:
• Compute cosine of angle
   
• Read transaction record
   
• Assign seat to airline passenger

Sequential cohesion

• Elements are involved in activities such that output data from one activity becomes input data to the next
   
• Usually has good coupling and is easily maintained
   
• Not so readily reusable because activities that will not in general be useful together
   
• Example of Sequential Cohesion
   
• module format and cross-validate record
   
•    use raw record
   
•     format raw record
   
•    cross-validate fields in raw record
   
•    return formatted cross-validated record

                 end module

Communicational Cohesion

• Elements contribute to activities that use the same input or output data
   
• Not flexible, for example, if we need to focus on some activities and not the others
   
• Possible links that cause activities to affect each other
   
• Better to split to functional cohesive ones
   
• Example of Communicational Cohesion
   
• module determine customer details
   
•    use customer account no
   
•    find customer name
   
•    find customer loan balance
   
•    return customer name, loan balance

end module

 

Procedural cohesion

• Elements are related only by sequence, otherwise the activities are unrelated
   
• Similar to sequential cohesion, except for the fact that elements are unrelated
   
• Commonly found at the top of hierarchy, such as the main program module
   
• Example of Procedural Cohesion
• module write read and edit something
•    use out record
   
•    write out record
   
•    read in record
   
•    pad numeric fields with zeros
   
•    return in record

         end module

Temporal cohesion

• Elements are involved in activities that are related in time
   
• Commonly found in initialisation and termination modules
   
• Elements are basically unrelated, so the module will be difficult to reuse
   
• Good practice is to initialise as late as possible and terminate as early as possible
   
• Example of Temporal Cohesion
• module initialise
•    set counter to 0
   
•    open student file 
   
•    clear error message variable
   
•    initialise array

       end module

 

Logical cohesion

• Elements contribute to activities of the same general category (type)
   
• For example, a report module, display module or I/O module
   
• Usually have control coupling, since one of the activities will be selected
   
• Example of Logical Cohesion
• module display record

      use record-type, record

      if record-type is student then

             display student record

      else if record-type is staff then

             display staff record

end module

 

Coincidental cohesion

• Elements contribute to activities with no meaningful relationship to one another
   
• Similar to logical cohesion, except the activities may not even be the same type
   
• Mixture of activities - like ‘rojak’!
   
• Difficult to understand and maintain, with strong possibilities of causing ‘side effects’ every time the module is modified
• Example of Coincidental Cohesion

module miscellaneous functions

   use customer record

   display customer record

   calculate total sales

   read transaction record

   return transaction record

end module

 

Determining Module Cohesion

 

 

Other Design Factors to Consider

• Factoring: reduce module size, clarifying system,minimise duplication of code, separating work from management, creating useful modules, simplifying
   
• System Shape (Structure)
   
• Redundancy
   
• Fan-in/Fan-out
   
• Restrictivity/Generality

DBMS

DBMS Notes Series-1

Hello Friends!

Let's discuss questions on DBMS from previous year papers. To begin with, some of the multiple choice type questions are listed below:

Q. Location transparency allows :
 I. Users to treat the data as if it is done at one location.
 II. Programmers to treat the data as if it is at one location.
 III. Managers to treat the data as if it is at one location.
 Which one of the following is correct ?
 (A) I, II and III (B) I and II only (C) II and III only (D) II only

The right answer is (A). 
Reason: Location transparency means the location of data must not matter to the person who accesses/manipulates the data. This is a feature of distributed databases, which applies to every kind of database user. According to a definition on Wikipedia, "The location of a resource doesn't matter to either the software developers or the end-users. This creates the illusion that the entire system is located in a single computer, which greatly simplifies software development."

The I and II are database users. The III is a component of distributed databases. Database Manager components are responsible for providing seamless data access to users without regards to its location. Hence, this covers all 3 choices.

Q. Which of the following is correct?
I. Two phase locking is an optimistic protocol.
II. Two phase locking is pessimistic protocol
III. Time stamping is an optimistic protocol.
IV. Time stamping is pessimistic protocol.

(A) I and III (B) II and IV (C) I and IV (D) II and III

The right answer is (D).
Reason: Optimistic Vs. Pessimistic approach: The optimistic concurrency control approach doesn't actually lock anything. It is based on the assumption that conflicts of database operations are very less. Means, when when oner transaction is executing, other transactions will not access the same data item being accessed by the executing one. It lets transactions run to completion and only checks for conflicts when they are about to commit. Thus, a transaction is executed without any restrictions until it is committed.

The pessimistic approach believes that some other transaction might try to access the same piece of data. So, in order to prevent any conflict, a transaction will first acquire all the required locks, then perform all the operations. It has two phases:
1. Growing Phase, where a transaction must first acquire all the locks.
2. Shrinking Phase, where a transaction releases all the locks one-by-one.(It cannot issue lock requests here.)

Q. Data warehousing refers to
(A) storing data offline at a separate site (B) backing up data regularly
(C) is related to data mining (D) uses tape as opposed to disk

The right answer is (C)

Reason: NOT A because: Not all data of Data warehouse stored offline as it depends on nature and usage of data.

NOT B because: A data warehouse typically stores a lot of historical data, that is often not subject to change. Data that does not change only needs to be backed up once.

NOT D because: Data may be stored using a proper mix of disks, tapes, or near-line storage.

Common data warehouse models include a data warehouse that is subject oriented, time variant, non-volatile, and integrated.

Q. The "PROJECT' operator of a relational algebra creates a new table that has always

(A) More columns than columns in original table

(B) More rows than original table

(C) Same number of rows as the original table

(D) Same number of columns as the original table

The right answer is (A) 

Reason: The number of tuples in the result of PROJECT  <list> (R) is always less or equal to the number of tuples in R.

Now, a few questions with descriptive answers:

Q. Show that 2-phase locking ensures serializability?

A. In databases and transaction processing two-phase locking, (2PL) is a concurrency control method that guarantees serializability. A transaction is said to follow the two-phase locking protocol if all locking operations (read_lock, write_lock) precede the first unlock operation in the transaction. Such a transaction can be divided into two phases:

Phase 1: Growing Phase
i)  transaction may obtain locks
ii)  transaction may not release locks

Phase 2: Shrinking Phase
i)  transaction may release locks
ii)  transaction may not obtain locks

If lock conversion is allowed, then upgrading of locks (from read-locked to write-locked) must be done during the expanding phase, and downgrading of locks (from write-locked to read-locked) must be done in the shrinking phase. Hence, a read_lock(X) operation that downgrades an already held write lock on X can appear only in the shrinking phase.

The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points  (i.e. the point where a transaction acquired its final lock). Two-phase locking does not ensure freedom from deadlocks.

Q. How to determine candidate key(s) for a relation?

A. Finding candidate keys is just as simple as applying some algorithm here and there.
In the first example, there are five attributes:
W H O S E
WH -> S
HOS -> E
Steps:
1. Find the attributes that are neither on the left and right side
> (none)
2. Find attributes that are only on the right side
> E
3. Find attributes that are only on the left side
> WHO
4. Combine the attributes on step 1 and 3
> since step 1 has no attributes, it’s just WHO
5. Test if the closures of attributes on step 4 are all the attributes
> in this case, it is true. Because with WH we can get S, and by HOS, we can get E.
So we have only one candidate key that is WHO.

Q. What are steps of a Database design?

A. Major Steps in Database Design are:

1. Requirements Analysis: Talk to the potential users! Understand what data is to be stored, and what operations and requirements are desired.
2. Conceptual Database Design: Develop a high-level description of the data and constraints (we will use the ER data model)
3. Logical Database Design: Convert the conceptual model to a schema in the chosen data model of the DBMS. For a relational database, this means converting the conceptual to a relational schema (logical schema).
4. Schema Refinement: Look for potential problems in the original choice of schema and try to redesign.
5. Physical Database Design: Direct the DBMS into choice of underlying data layout (e.g., indexes and clustering) in hopes of optimizing the performance.
6. Applications and Security Design: It defines how the underlying database will interact with surrounding applications.

Q. Differentiate b/w Specialisation and Generalisation in ER Model?

A. Specialisation:
Top-down design process; we designate subgroupings within an entity set that are distinctive from other entities in the set.
These subgroupings become lower-level entity sets that have attributes or participate in relationships that do not apply to the higher-level entity set.
Depicted by a triangle component labeled ISA (E.g. customer “is a” person).
Attribute inheritance – a lower-level entity set inherits all the attributes and relationship participation of the higher-level entity set to which it is linked.

Generalisation:
A bottom-up design process – combine a number of entity sets that share the same features into a higher-level entity set.
Specialization and generalization are simple inversions of each other; they are represented in an E-R diagram in the same way.
The terms specialization and generalization are used interchangeably.

Grammars

TYPES OF GRAMMAR

A grammar G is 4-tuple or quadruple G=(V,T,P,S) where
V is set of variables or non-terminals.
T is set of terminals.
P is set of productions.
S is the start symbol.
Each production is of the form α -> β where α is a non empty string of terminals and/or non-terminals and β is string of terminals and/or non-terminals including the null string. This grammar is also called as phase-structure grammar.

CHOMSKY HIERARCHY

Phase-structure grammars may be classified according to their productions. The following table would help you understand with the classifications.

S.no	TYPE	NAME	PRODUCTION RULE	RESTRICTION	LANGUAGE GENERATED	MACHINE WHICH RECOGNISES
1	Type 0 grammar	Unrestricted grammar	α -> β	No restriction on length of α and β.α cannot be epsilon	type o language or recursively enumerable language	Turing machine
2	Type 1 grammar	Context sensitive grammar	α -> β	Length of β must be atleast as much as the length of α	Type 1 language or context sensitive language	Linear Bounded automata
3	Type 2 grammar	Context free grammar	A->α	The symbol epsilon can appear on the right side of any production.	type 2 language or context free language	Pushdown automaton
4	Type 3 grammar	Regular grammar	A->wB and/or A->w		Regular language	Finite state automaton

Following are the questions from previous NET exams on the above topic.

DECEMBER 2006
JUNE 2005
JUNE 2010
32. Which of the following is the most general phase-structure grammar?
A)Regular B)Context-sensitive
C)Context free
D)Syntax tree or D) None of these
Ans:-B
Explanation:- The above question has appeared in more than 3 previous papers. The right answer is Context-sensitive grammar.
DECEMBER 2007
3) A context free grammar is :
A)type 0
B)type 1
C)type 2
Ans:- C

DECEMBER 2009
34). Context free grammar(CFG) can be recognised by
A)Finite state automaton
B)2-way linear bounded automata
C)Push down automata
D)Both B & C
Ans:- C

JUNE 2013 - PAPER III - QNo. 39
Match the following :
a. Context sensitive language     i. Deterministic finite automation
b. Regular grammar      ii. Recursive enumerable
c. Context free grammar     iii. Recursive language
d. Unrestricted grammar     iv. Pushdown automation

Ans:-

Unrestricted grammar is Recursive enumerable which is also type 0.
Context free grammar is recognised by pushdown automation
Regular grammar is recognised by Deterministic finite automation
Context sensitive language would be recursive language which is also type 1 grammar.
Choose the appropriate option by looking at the answer.

KNAP

KNAPSACK PROBLEM

JUNE 2014 - PAPER III Q.No 62

62. Consider the fractional knapsack instance n=4, (p1,p2,p3,p4) = (10,10,12,18)
(w1,w2,w3,w4)=(2,4,6,9) and M=15. The maximum profit is given by,
(Assume p and w denotes profit and weights of objects respectively).
(A)40
(B)38
(C)32
(D)30
Ans:-B

Explanation:-
Knapsack problem can be solved either using Greedy approach or through Dynamic programming. I am going to be explaining using the former. It has been proved that for the knapsack problem using greedy method we always get the optimal solution provided the objects are arranged in decreasing order of pi/wi. So, before solving the problem, let us arrange all the objects in decreasing order of pi/wi.
Capacity of the knapsack M = 15
Number of objects = 4
Profits(p1,p2,p3,p4)=(10,10,12,18)
Weights(w1,w2,w3,w4)=(2,4,6,9)
To get the solution arrange objects in decreasing order of profit/weights as shown below.
p1/w1=10/2 =5

p2/w2=10/4=2.5

p3/w3=12/6=2

p4/w4=18/9=2

Arrange in decreasing order of pi/wi, we get

Object	Weight	Profit	Pi/wi
1	2	10	5
2	4	10	2.5
3	6	12	2
4	9	18	2

The fractions of the objects selected and the profit we get can be computed as shown below:

Remaining Capacity	Object selected	Weight of the object	Fraction of the object selected
15	1	2	1 full unit
15-2=13	2	4	1 full unit
13-4=9	3	6	1 full unit
9-6=3	4	9	3/9 or 1/3 fraction of unit

So, the solution vector will be=(1,1,1,1/3)
Profits=1 X 10 + 1 X 10 + 1 X 12 + 1/3 X 18
Profits=10+10+12+6
Profits=20+18
=38
So the correct answer will be 38. The maximum profit is given by option (B) which is 38. Solve the following problem and see.

I. Obtain the optimal solution for the knapsack problem given the following: M=40,n=3, (p1,p2,p3)=(30,40,35) and (w1,w2,w3)=(20,25,10).

. The answer for the above problem is 82.5

DPD

Dependency Preservation Decomposition

December 2010 - Question No 17
The dependency preservation decomposition is a property to decompose database schema D, in which each functional dependency X → Y specified in F,

(A) appeared directly in one of the relation schemas Ri in the decomposed D.
(B) could be inferred from dependencies that appear in some Ri.
(C) both (A) and (B)
(D) None of these

Explanation:- The question itself requires a bit of explanation. It is not enough if you just know what is the right answer but you must also know why it is the right answer. The explanation would be a bit lengthy. Let us first dissect the question and explain some terms in terms of DBMS.
Decomposition - This means replacing a relation with a collection of smaller relations.

Relation - Relation is known as Table.

Relation Schema - This is known as Table definition. Relation Schema for a "student" relation can be shown in the following way:
Student(FirstName,LastName,DOB,Gender,Course,Regno,Address)

Definition of Dependency preservation decomposition:-
Each FD specified in F either appears directly in one of the relations in the decomposition, or be inferred from FDs that appear in some relation.

Let us consider an example for Dependency preservation

Let R be a relation R(A B C D)
Let there be 3 functional dependencies.
FD1: A->B
FD2: B->C
FD3: C->D
Let the relation R be decomposed into two more relations.
R1(A B C)  :  R2(C D)
Let us first consider the relation R1(A B C). Here between A and B the functional dependency FD1 is preserved. Between B and C, FD2 is preserved.
Let us now consider the second relation R2(C D). Between C and D the FD, FD3 is preserved. So in the two relations R1 and R2, all the 3 functional dependencies are preserved.

Let us consider an example for Non-dependency preservation

Let R be a relation R(A B C D) Let there be again 3 functional dependencies.
FD1:A->B
FD2:B->C
FD3:C->D
Let the relation be decomposed into two more relations>
R1(A C D) R2(B C)
Let us first consider the relation R1(A C D). There is no FD between A and C. There is a FD3 between C and D.
Now let us consider the second relation R2(B C). There is FD2 between B and C.
So, the two relations only support only FD's FD2 and FD3. FD1 is not supported. So these relations does not preserve dependency.
Generally there are three desirable properties of a decomposition.

1. Lossless
2. Dependency preservation
3. Minimal redundancy

The above question was based on dependency preservation decomposition. This example has been taken from the dependency preservation presentation by Jason Allen. The explanation is quite good there.

SUMMARY:-

The dependency preservation decomposition is a property to be considered for decomposing a relation into two or more smaller relations. The functional dependency X->Y specified in F can appear directly in one of the relation schemas Ri in the decomposed D or it could be inferred from dependencies that appear in some Ri. So the answer for this question is C.

Ans:-C

DBMS

DBMS

In DBMS, there could be a question on different steps in normalization and what is achieved at the end of every step in it.You need to be knowing the following things very clearly and without any ambiguity.The question would be based on these terms.

A table is in 1NF if there and no duplicate rows in the table. Each cell is single-valued.

A table is in 2NF if it is in 1NF and if all non-key attributes are dependent on all of the key. A table is in 2NF if it is in 1NF and if it has no partial dependencies

A table is in 3NF if it is in 2NF and if it has no transitive dependencies

A table is in BCNF if it is in 3NF and if every determinant is a candiate key.

A table is in 4NF if it is in BCNF and it it has no multi-valued dependencies.

A table is in 5NF if it is in 4NF and it has no join dependency.

Superkey,Candidate key,Primary key

A superkey is any set of attributes such that the values of the attributes(taken together)uniquely identify one entity in the entity set.

A candidate key is a minimal superkey.

A primary key is one of the candidate keys, designated by the Database designer.

INFIX EXPRESSION TO POSTFIX EXPRESSION

CONVERSION OF INFIX EXPRESSION TO POSTFIX EXPRESSION

The conventional method of representing an arithmetic expression is known as infix because the operand is placed in between the operands. If the operator is placed before the operands then this notation is called prefix or Polish notation. If the operator is placed after the operand then this notation is called postfix or reverse polish notation. So now we have three ways to represent an arithmetic expression.
Infix:   A+B

Prefix:   +AB

Postfix:   AB+


Now, let us see how to convert an infix expression to postfix expression. The rules of parenthesis and precedence would be followed in the following way. If there are parenthesis in the expression, then the portion inside the parenthesis will be converted first. After this the operations are converted according to their precedence. (* and / first, followed by + and -). If there are operators of equal precedence then the operator which is on the left is converted first. In order to understand this with an example, let us solve an example from June 2014, Paper III, Question No. 41.
JUNE 2014 - PAPER III - Q.No 41
41. The reverse polish notation equivalent to the infix expression

((A + B) * C + D) / (E + F + G)

(A) A B + C * D + E F + G + /

(B) A B + C D * + E F + G + /

(C) A B + C * D + E F G + +/

(D) A B + C * D + E + F G + /


Ans:-A
Explanation:-

First, always the expression given within parenthesis is converted first. Since there are 2 expressions with the parenthesis, I am going with the expression (E + F + G) first, although the order does not matter.

In the expression (E + F + G), there are 3 operands E,F and G and two operators, both being +. Since both the operators are the same, the expression is going to be evaluated from left to right. So E + F is considered first and converted into postfix form which is EF+. So, the expression becomes,

( ( A + B ) * C + D) / ([E F +] + G)

Any expression converted into postfix form is going to be written in square brackets.

( ( A + B ) * C + D) / [ E F + G + ]
. Here EF+ is one operand, G is another operand and + is the operator.

The next expression to be converted into postfix is ( A + B).

( [ A B + ] * C + D) / [ E F + G + ]

Now, the expression which is enclosed in parenthesis is evaluated and so, we get

( [ [ A B + ] C * ] + D) / [ E F + G + ]

[ A B + C * D + ] / [ E F + G + ]

[ A B + C * D + ] [ E F + G + ] /

So, the final postfix expression is A B + C * D + E F + G + /. This answer is available in option A. So option A is the correct answer.

PROPERTIES OF BINARY TREES

There are some basic properties of binary trees. It is better to know all of them and how to apply.For easier understanding I am giving it in a tabular form.

1.	Maximum number of nodes on any level i is	2i
2.	Maximum number of nodes possible in a binary tree of height h is	2h-1
3.	Minimum number of nodes possible in a binary tree of height h is equal to	h
4.	If a binary tree contains n nodes, then its maximum height possible is	n
5.	If a binary tree contains n nodes, then its minimum height possible is	log2(n+1)
6.	In a non empty binary tree, if n is the total number of nodes and e is the total number of edges, then	e=n-1
7.	In a full binary tree of height k, there are	2k-1 internal nodes
8.	A strictly binary tree with n leaf nodes always has	2n - 1 nodes

JUNE 2007 - PAPER II Q.No 3

The maximum number of nodes in a binary tree of depth 10 is :
(A). 1024
(B). 2¹⁰-1
(C). 1000
(D). None of the above
Ans:- B
Explanation:-
According to property 2, the maximum number of nodes in a binary tree of height or depth h is 2^h-1

DECEMBER 2007 - PAPER II Q.No 23

The height of a binary tree with 'n' nodes in the worst case is

(A). 0(log n)
(B). O(n)
(C). Ω(n log n)
(D). Ω(n²)
Ans:- B
Explanation:-
Big omega notation is used for representing the best case. Big oh notation is used for representing the worst case. It is a measure of the longest amount of time it could possibly take for any algorithm to complete. Since we are representing the height of a binary tree, it would be the maximum height possible in a tree with 'n' nodes and it is O(n). So, the correct answer is B.

JUNE 2009 - PAPER II Q.No. 27

In a full binary tree of height k, there are ____________internal nodes.

(A). 2^k-1
(B). 2^k-1
(C). 2^k
(D). 2^k+1

Ans:-A
Explanation:-
Refer to the following diagram to understand the explanation. A full binary tree is one which has all the levels have maximum number of nodes in a tree.

DECEMBER 2009 - PAPER II Q.No 21

If the number of leaves in a strictly binary tree is an odd number, then what can you say with full conviction about total number of nodes in the tree?.
(A). It is an odd number.
(B). It is an even number.
(C). It cannot be equal to the number of leaves
(D). It is always greater than twice the number of leaves

Ans:-A
Explanation:-
A binary tree is a strictly binary tree if each node in the tree is either a leaf node or has exactly two children. There is no node with one child. According to its property, a strictly binary tree with n leaf nodes always has 2n-1 nodes. Let us consider n to be an odd number and give it a value of 3. So, the number of nodes in the tree would be 2n - 1 which is 2 X 3 -1 = 5. So that is also an odd number. So, the answer is A.

JUNE 2010 - PAPER II Q.No 23

In a complete binary tree of n nodes, how far are the two most distant nodes?.Assume each edge in the path count as 1.
(A). About log₂n
(B). About 2log₂n
(C). About nlog₂n
(D). About 2n

Ans:-A
Explanation:-
The height h of a complete binary tree with n nodes is at the most O(log₂n).

DECEMBER 2011 - PAPER II Q.No. 50

The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to

(A) 2⁰+2¹+......+2^h
(B) 2⁰+2¹+......+2^h-1
(C) 2⁰+2¹+......+2^h+1
(D) 2¹+......+2^h+1

Ans:-A
Explanation:-
Count the number of nodes in each level, starting with the root, assuming that each level has the maximum number of nodes.
n=1+2+4+....2^h-1+2^h

Data Structures

This particular question is not clear for few readers. So, I am taking it up once again.
25. Which of the following can be the sequence of nodes examined in binary search tree while searching for key 88 ?

(A) 90, 40, 65, 50, 88
(B) 90, 110, 80, 85, 88
(C) 190, 60, 90, 85, 88
(D) 65, 140, 80, 70, 88


Ans:- B
Explanation:-
I am taking the liberty of retaining an explanation given for a similar question from yahoo answers.

Best Answer: For a binary search tree, the entire tree is sorted such that for any node, every node to the left is less than the current node value and every node to the right is more than the current node value.
When walking a BST tree, you "zero in" on the value by following the correct nodes down the tree. Ideally you work closer and closer to your answer, kind of like the "guess the number" game where you give "nope, more!" and "nope, less!" hints.
a) 2, 399, 387, 219, 266, 382, 381, 278, 363
This sequence is possible.
b) 935, 278, 347, 621, 299, 392, 358, 363
This sequence is not possible. Since 621 is to the right of 347, every other node under 621 must ALSO be to the right of 347. 299 is not -- so this is an impossible walk. Basically, once you pass 347, 299 is swinging too far in the opposite direction.
c) 924, 220, 911, 244, 898, 258, 362, 363
This sequence is possible.
d) 925, 202, 911, 240, 912, 245, 363
Not possible -- 240 is to the left of 911, so every other node must also be less than 911 (but still may be to the right of 240). 912 is not to the left of 911.
e) 2, 252, 401, 398, 330, 344, 397, 363 This sequence is possible. Just barely though -- 397 is to the left of 398 but just barely!
I am taking the example b which explains why a particular sequence is not possible. Since 621 is to the right of 347, every other node under 621 must ALSO be to the right of 347.
Let us apply the same rule to all the sequences given above for us in the question.
The first sequence is 90,40,65,50,88. Do not consider any particular element as the root. But start analysing the numbers from first. 90 is the first number. 40 is the second one. So, 40 will be to the left of 90, since it is less than 90. Since 40 is to the left of 90, all numbers following 40 also should be to the left of 90, which is true in this sequence. 65,50, and 88 will be to the left of 90. So this sequence is possible.
Let us consider the second sequence which is 90,110,80,85,88. Again 90 is the first number. 110 will be to its right since it is greater than 90. So all the numbers following 110 also should be to the right of 90,but 80,85 and 88 fall to its left. So, this sequence is not possible.
Let us consider the third sequence which is 190,60,90,85,88. So, 190 is the first number. 60 is to its left. So all the other numbers following 60 should be to the left of 190, which is holding good here. 90,85 and 88 will be to the left of 190. So, this sequence is possible.
Let us consider the fourth sequence which is 65,140,80,70,88. 65 is the first number. 140 will be to its right. All the numbers following 140 should be to the right of 65 which is true. 80,70 and 88 will be to the right of 65 as well.
So, the correct answer is option B and not C.
Thank you all, for bringing this question for discussion as we have zeroed in on the right answer.