Search Previous Year Questions

Concept:

Data independence is defined as a property of DBMS that helps you to change the database schema at one level of a database system without requiring to higher level.

Explanation:

Database has 3 levels:

1. Physical level

2. Conceptual level

3. External level

Two types of data independence

a) logical data independence b) physical data independence

Logical data independence:

Logical data is data about database. It is a kind of mechanism which liberalizes itself from actual data stored on the disk. It is the ability to change the conceptual scheme without changing external view or APIs.

Any change made will be absorbed by the mapping between external and conceptual levels.

Physical data independence:

It is mainly concerned with the storage of the data. A change in the physical level usually does not need change at application program level.

A clustered index is an ordered file with two fields, the first field is the same as the clustering field is called monkey, and the second is the block pointer.

It is created on a data file whose file records are physically ordered on a non-key field which does not have a distinct value for each record that field is called the clustering field.

Some important points:

1. Index entry is created for each distinct value of a clustering field

2. block pointer points to the first block in which key is available.

3. type of index is sparse index

9’s complement can be find out by subtracting the given number from 9.

Subtract each and every digit of a given number by digit 9.

i.e. 999999 – 139452 = 860547

A pointer in C language is an address which is a numeric value. We can perform arithmetic operations on a pointer just as on a numeric value. But there are some restrictions in case of pointers:

Valid pointer operations are:

1. assignment of pointers of same type

2. adding or subtracting a pointer or an int

3. subtracting or comparing two pointers to members of same array

4. assigning or comparing to zero

We cannot add two pointers. Because if we add two pointers, then in case of array it can go out of the scope.

Consider all the options one by one:

1. P[2][5]

It represents the element present in 2^nd row and 5^th column.

2. ((P+2) + 5)

*(P+2) ---- it leads to enter 2^nd row

*(P+2)+5 ------- will give address of element present at 5^th column of 2^nd row.

((P+2) + 5) ------- it will represent at 5^th column of 2^nd row.

3. *(P + 2 + 5)

*(P+7) ------- will return starting address of 7^th row.

4. *(P [2] + 5)

It will also return the element present at 5^th column of 2^nd row.

Conflict equivalent: Two schedules are said to be conflict equivalent when one can be transformed to another by swapping non – conflicting operations. Two schedules are conflict equivalent if the order of any two conflicting operations is same in both the schedules.

Example:

View equivalent: Two schedules are said to be view equivalent if they satisfy these conditions:

1)  Initial read: Initial read of each data item must match in both schedules.

2. Final write: it means if a data item X is last written by transaction T1 in schedule S1 then in S2, the last write operation on X should be performed by the transaction T1.

3. Update read: If in schedule S1, the transaction T1 is reading a data item updated by T2 then in schedule S2, T1 should read the value after the write operation of T2 on same data item.

A binomial coefficient ⁿC_k gives us the number of ways that k objects can be chose among n objects. WE have to find k element subset from n element set.

To calculate the value of binomial coefficient we call it recursively as :

ⁿC_k = ^n-1C_k-1 + ^n-1C_k for n> k> 0

ⁿC₀ = ⁿC_n = 1            (Base case)

It is computed by constructing a table.

Cost of the algorithm is the cost of filling the table.  Because k< = n, this sum is to be splitted into two parts.

T(n,k) = sum for upper triangle + sum for lower triangle

\(= \mathop \sum \limits_{i = 1}^k \mathop \sum \limits_{j = 1}^k 1 + \mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = 1}^k 1\)

\(= \mathop \sum \limits_{i = 1}^k \left( {i - 1} \right) + \mathop \sum \limits_{i = 1}^n k\)

= (k-1)k/2 + k (n-k) = nk

So, time complexity to compute the binomial coefficient is : Θ(nk)

Concept:

A greedy approach tries to find a localized optimum solution, which may eventually lead to globally optimized solutions. It also makes the choice that seems to be the best at that moment.

Some of the problems which use a greedy approach:

• Traveling salesman problem
• Prim’s algorithm (Minimum spanning tree)
• Huffman code
• Graph – map colouring
• Fractional knapsack problem
• Job scheduling problem

Explanation:

For 0-1 knapsack, dynamic programming approach is used. It cannot be solved using greedy approach.

In 0-1 knapsack, items cannot be broken which means you should take the item as whole or should leave it.

The relation returned by the division operator between two relations A and B are those tuples from relation A which are associated to every B’s tuple.

R:

S:

Now check which values of A in S is associated with B in R.

a1 is associated with [b1, b2, b4]

a2 is associated with [b1, b3, b4]

a3 is associated with [b1, b2, b3, b4]

Now, [b1, b4] are the common elements that are associated with values of A in S.

T = R/S

T:

A counter is a device which tells about the number of times an event has occurred. Two types of counters are: Asynchronous counter and synchronous counter

Asynchronous counter: in this different flip- flops have different clock cycles. It is also known as ripple counter. Also known as parallel counter. Asynchronous counter operates in a fixed count sequence. Example of asynchronous counter: ripple counter etc.

Synchronous counter: All flip flops are triggered with same clock simultaneously. These types of counters are faster than asynchronous.  These are also known as serial counter. Examples of synchronous counter: ring counter, Johnson counter etc.