Express T(n) in terms of the harmonic number H_n = $$\sum\limits_{t = 1}^n {1/i,n \ge 1} $$ where T(n) satisfies the recurrence relation, T(n) = $${{n + 1} \over 2}$$ T(n-1) + 1, for $$n \ge 2$$ and T(1) = 1 What is the the asymptotic behavior of T(n) as a function of n?

Match the pairs in the following:

List - I

(a) Straseen's matrix multiplication algorithm
(b) Kruskal's minimum spanning tree algorithm
(c) Bioconnected components algorithm
(d) Floyd's shortest path algorithm

List - II

(p) Greedy method
(q) Dynamic programming
(r) Divide and Conquer
(s) Depth first search

Match the pairs in the following:

List - I

(a) Heap construction
(b) Constructing hash table witn linear probing
(c) AVL Tree construction
(d) Digital tree construction

List - II

(p) $$\Omega \left( {n\log _{10}^n} \right)$$
(q) O(n)
(r) O(n²)
(s) $$\Omega \left( {n\log _2^n} \right)$$

Match the following:

List - I

(a) Lexical Analysis
(b) Code Optimization
(c) Code Generation
(d) Abelian Group

List - II

(p) DAG's
(q) Syntax trees
(r) Push Down automata
(s) Finite automata

Match the followings:

Group-I

(a) Pointer data type
(b) Activation Record
(c) Repeat -Until
(d) Coercion

Group-II

(p) Type Conversion
(q) Dynamic Data Structure
(r) Recursion
(s) Nondeterministic loop

A block -set associative cache memory consists of $$128$$ blocks divided into four block sets. The main memory consists of $$16,384$$ blocks and each blocks contains $$256$$ eight bit words.

(i) How many bits are required for addressing the main memory?

(ii) How many bits are needed to represent the TAG, SET and WORD fields?

State the Both's algorithm for multiplication of two numbers, Draw a block diagram for the implementation of the Booth's algorithm for determining the product of two $$8-$$bit signed numbers.

Fill in the blanks:
In the two bit full-adder/sub tractor unit shown in Fig., when the switch is in position $$2.$$ $$.....$$ using $$.....$$ arithmetic.

For the synchronous counter shown in fig. write the truth table of $${Q_0},\,\,{Q_1}$$ and $${Q_2}$$ after each pulse starting from $${Q_0} = {Q_1} = {Q_2} = 0$$ and determine the counting sequenced also the modulus of the counter

What is the modules of the counter with initial state $${Q_2}\,{Q_1}\,{Q_0} = 000$$

Two $$NAND$$ gates having open collector outputs are tied together as shown in fig. The logic function $$Y,$$ implemented by the circuit is.

Consider the number given by the decimal expression.
$${16^3} \times 9 + {16^2} \times 7 + 16 \times 5 + 3$$

The number of $$1's$$ in the unsigned binary representation of the number is _______.

Find the minimum product of sums of the following expression
$$f = ABC + \overline A \,\overline B \,\overline C .$$

Show with the help of a block diagram represent Boolean function:
$$f=AB+BC+CA$$ can be realized using only $$4:1$$ multiplexer.

A graph is planar if and only if,

Indicate which of the following well-formed formula are valid:

State whether the following statements are TRUE or FALSE with reason.
The Link-load -and-go loading scheme required less storange space than the Link-and-go loading scheme.

Match the pairs in the following Question.
$$\eqalign{ & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,List:\,{\rm I} \cr & \left( A \right)\,\,Criotical\,\,region \cr & \left( B \right)\,\,Wait/Signal \cr & \left( C \right)\,\,Working\,\,set \cr & \left( D \right)\,\,Deadlock \cr & \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,List:\,{\rm I}{\rm I} \cr & \left( p \right)\,\,Hoare's\,\,monitor \cr & \left( q \right)\,\,Mutual\,\,exclusion \cr & \left( r \right)\,\,\Pr inciple\,\,of\,\,locality \cr & \left( s \right)\,\,Circular\,\,Wait \cr} $$

Under paged memory management scheme simple lock and key memory protection arrangement may still be required if the $$........$$ processors do not have address mapping hardware.

State whether the following statements are TRUE or FALSE with reason. Transferring data in blocks from the main memory to the cache memory enables an interleaved main memory unit to operate unit at its maximum speed.

In a two -level virtual memory, the memory access time for main memory, $${t_M} = {10^{ - 8}}\sec $$ and the memory access time for the secondary memory, tag $$ = {10^{ - 3}}.$$ What must be the hit ratio, $$H$$ such that the access efficiency is within $$80$$ percent of its maximum value?

State whether the following statement are TRUE or FALSE with reason. The data transfer between memory and $${\rm I}/O$$ devices using programmed $${\rm I}/O$$ is fasterthan interrrupt-driven $${\rm I}/O$$.

A certain moving arm disk-storage device has the following specifications:
Number of tracks per surface $$=4004$$
Track storage capacity $$=130030$$ bytes
Disk speed $$=3600$$ rpm
Average seek time $$=30$$ m secs.
Estimate the average latency the disk storage capacity and the data transfer rate.

Assuming the current disk cylinder to be $$50$$ and the sequence for the cylinders to be
$$1, 36, 49, 65, 53, 1, 2, 3, 20, 55, 16, 65$$ and $$78$$ find the sequences of servicing using
(i) shortest-seek time first $$(SSTF)$$
(ii) elevator disk scheduling polices.

The highest-response ratio next scheduling policy favours $$.......$$ jobs, but it also limits the waiting time of $$ .....$$ jobs.

Semaphore operations are atomic because they are implemented within the OS

Match the pairs in the following:

List - I

(A) Small talk
(B) LISP
(C) Prolog
(D) VAL

List - II

(p) Logic programming
(q) Data flow programming
(r) Functional programming
(s) Object-Oriented programming

It is decidable whether:

Recursive languages are:

Let $${R_1}$$ and $${R_2}$$ be regular sets defined over the alphabet $$\sum \, $$ then:

State whether the following statement is TRUE / FALSE.

All subjects of regular sets are regular.

State whether the following statement is TRUE / FALSE.

A minimal $$DFA$$ that is equivalent to an $$NFDA$$ with $$n$$ modes has always 2ⁿ states

State whether the following statement is TRUE / FALSE.

Regularity is preserved under the operation of string reversal.

State whether the following statement is TRUE / FALSE.

A is recursive if both a and its complement are accepted by Turing Machine M accepts.

State whether the following statement is TRUE / FALSE.

The intersection of two $$CFL's$$ is also $$CFL.$$

State whether the following statement is TRUE / FALSE. The problem is to whether a Turing Machine M accepts input $$w$$ is un-decidable.