Search Previous Year Questions

Algorithm for conversion from prefix to infix:

STEP 1:

Start scanning the expression from RHS. Push the operators on the top of the stack by ensuring that only high priority operator can be pushed over a low priority operator.

STEP 2:

If a low priority operator is encountered in expression and if top of stack is high priority operator, then pop it and after that push low priority operator on the top of stack.

STEP 3:

Print each operand.

Given expression is : a/b – c + d * e – a * c

⇒ /ab-c+de-ac

⇒ -/abc+de-ac 

⇒ +-/abcde-ac

⇒ +-/abcde-ac

⇒ +-/abc*de-*ac

⇒ -+-/abcdeac

(X’)’ = X → involution law.

X + Y)’=X’.Y’ → De Morgan Law

X(X+Y) = X + XY = X → Absorption law

X + YZ = (X +Y) (X+Z) → Distributive law

Simple attribute:

These are atomic values which cannot be divided further.

Composite attribute:

These are made up of more than one simple attribute.

Single valued:

These attributes contain only single value.

Key – attribute:

Attribute that uniquely identifies an entity among entity set. Here, enrolment number can be considered as composite, single- valued and key attribute.

Travelling salesman problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

To calculate the cost of TSP using dynamic programming algorithm, there are some recursive relation in terms of sub problems.

Recurrence relation for this problem:

C(S,j)=minC(S−{j},i)+d(i,j)where i∈S and i≠j

C(S,j)=minC(s−{j},i)+d(i,j) where i∈ S and i≠j

In case of dynamic programming approach, there are at most 2ⁿ.n subproblems and each problem takes linear time to solve.

So, overall time complexity for this is O(2ⁿ.n²).

But we have to find the every case time complexity which will be: O(2ⁿ.n)

Let G be a graph with k components. Let n_i  be the number of vertices in the i^th component., where 1<=i<=k, then the number of edges in the graph is equal to the sum of the edges in each of its components. Thus, G has the maximum number of edges if each component is a complete graph.

Hence, the maximum possible number of edges in the graph is \(\mathop \sum \limits_{i = 1}^k \frac{{{n_i}\left( {{n_i} - 1} \right)}}{2}\)

After expanding, the maximum number of edges: \(\frac{{\left( {n - k} \right)\left( {n - k + 1} \right)}}{2}\)

Example:

n = 6 and k = 3

maximum number of edges = 6

Using Formula:

\(\frac{{\left( {n - k} \right)\left( {n - k + 1} \right)}}{2} = \frac{(6 -3)(6-3+1)}{2}= 6\)

Concept:

Address line: An address line is basically refers to a physical connection between a CPU/Chipset and memory. They specify which addresses to access in memory. When there are k address lines, then 2^k memory word can be accessed.

Data line: Data lines provides the information to be stored in memory. It represents the number of bits in the word.

Calculation:

Here, it is given that memory unit size = 96 K × 16

Where, 96 K represents the number of words.

16 represents the number of bits per word.

As, 96 > 128 so, we have to take 128 i.e. 2⁷.

Number of words = 96 K = 2⁷ × 2¹⁰ = 2 ¹⁷

It means address line to access those words are 17.

Number of input – output data lines = number of bits in a word = 16

Let us consider a full binary tree with 3 levels:

Here, at level 0 we have only 1 node.

At level 1, maximum 2 nodes are possible.

At level 2, maximum 4 nodes are possible.

i.e. for every level k, there are no more than 2^k nodes possible.

Also, total nodes in the tree are 7. With 3 levels, maximum 7 nodes are possible.

i.e. with h levels maximum 2^h-1 nodes are possible.

Here, we have given n nodes, and we have to find the number of levels.

Number of levels is at least \(\left\lceil {{{\log }_2}\left( {N; + ;1} \right)} \right\rceil \)

IP address is an address having information about how to reach a specific host. The 32 bit IP address is divided into five sub classes. These are:

1. Class A

2. Class B

3. Class C

4. Class D

5. Class E

Class D and E are reserved for multicast and experimental purposes.

IPv4 addresses are divided into two parts: a) Network ID b) Host ID

Concept:

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Spanning tree doesn’t have cycles and it cannot be disconnected.

Formula:

Number of spanning trees possible with n nodes = n^n-2

Calculation:

Here, number of vertices are 4.

So, number of spanning trees possible = 4^4-2 = 4² = 16

Type 3 grammar: These generate regular languages. These languages are accepted by a finite state automaton. Type 3 is the most restricted form of grammar.

Type 2 grammars: These grammars generate the context-free languages. These are accepted by pushdown automata. In type 2, the Left-hand side of the production must have only one variable. Grammar production is in the form of α → β where |α| = 1 for type 2 grammar. No restriction on β.

Type 1 grammar: This type of grammar generates context-sensitive language. These languages are accepted by linear bounded automata. Grammar production is in the form of α → β where |α| ≤ |β| or α → λ

Type 0 grammar: These are Turing recognizable language. These languages are also called recursively enumerable languages.

Production is of the form of α → β where α is (V + T)⁺  and β is (V + T)*, V is variable and T is terminal.