Consider the following C functions:

int f1(int n){
 if(n == 0 || n == 1){
    return n;
 }
 return (2 * f1(n - 1) + 3 * f1(n - 2));
}
int f2(int n){
 int i;
 int X[N], Y[N], Z[N];
 X[0] = Y[0] = Z[0] = 0;
 X[1] = 1; Y[1] = 2; Z[1] = 3;
 for(i = 2; i <= n; i++){
  X[i] = Y[i - 1] + Z[i - 2];
  Y[i] = 2 * X[i];
  Z[i] = 3 * X[i];
 }
 return X[n];
}

f1(8) and f2(8) return the values

The subset-sum problem is defined as follows:
Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.

1.   f(int Y[10], int x) {
2.     int i, j, k;
3.     i = 0; j = 9;
4.     do {
5.             k =  (i + j) /2;
6.             if( Y[k] < x)  i = k; else j = k;
7.         } while(Y[k] != x && i < j);
8.     if(Y[k] == x) printf ("x is in the array ") ;
9.     else printf (" x is not in the array ") ;
10.  }

The correction needed in the program to make it work properly is

Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.

1.   f(int Y[10], int x) {
2.     int i, j, k;
3.     i = 0; j = 9;
4.     do {
5.             k =  (i + j) /2;
6.             if( Y[k] < x)  i = k; else j = k;
7.         } while(Y[k] != x && i < j);
8.     if(Y[k] == x) printf ("x is in the array ") ;
9.     else printf (" x is not in the array ") ;
10.  }

On which of the following contents of Y and x does the program fail?

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁ ,a₂ ,a₃ ,…,a_n} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a₁ ,a₂ ,…,a_i} whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁ ,a₂ ,a₃ ,…,a_n} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a₁ ,a₂ ,…,a_i} whose elements sum to j.
Which of the following is valid for 2 <= i <= n and ai <= j <= W?

Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

Consider the following C functions:

int f1(int n){
 if(n == 0 || n == 1){
    return n;
 }
 return (2 * f1(n - 1) + 3 * f1(n - 2));
}
int f2(int n){
 int i;
 int X[N], Y[N], Z[N];
 X[0] = Y[0] = Z[0] = 0;
 X[1] = 1; Y[1] = 2; Z[1] = 3;
 for(i = 2; i <= n; i++){
  X[i] = Y[i - 1] + Z[i - 2];
  Y[i] = 2 * X[i];
  Z[i] = 3 * X[i];
 }
 return X[n];
}

The returning time of f1(n) and f2(n) are

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

Consider the following functions: F(n) = 2ⁿ
G(n) = n!
H(n) = n^logn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

You are given the post order traversal, P, of a binary search tree on the n element, 1,2,....,n. You have to determine the unique binary search tree that has P as its post order traversal. What is the time complexity of the most efficient algorithm for doing this?

Which of the following describes a handle (as applicable to LR-parsing) appropriately?

Which of the following are true?

I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation

II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions

III. Recursion in programming languages cannot be implemented with dynamic storage allocation

IV. Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records

V. Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records

An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if

Some code optimizations are carried out on the intermediate code because

The total number of keys required for a set of n individuals to be able to communicate with each other using secret key and public key crypto-systems, respectively are:

A computer on a 10 Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2 Mbps. It is initially filled to capacity with 16 Megabits. What is the maximum duration for which the computer can transmit at the full 10 Mbps?

A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a socket( ), a bind( ) and a listen( ) system call in that order, following which it is preempted. Subsequently, the client process P executes a socket( ) system call followed by connect( ) system call to connect to the server process S. The server process has not executed any accept( ) system call. Which one of the following events could take place?

In the slow start phase of the TCP congestion control algorithm, the size of the congestion window

Which of the following system calls results in the sending of SYN packets?

What is the maximum size of data that the application layer can pass on to the TCP layer below?

If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet?

The use of multiple register windows with overlap causes a reduction in the number of memory accesses for
$$1.\,\,\,\,$$ Function locals and parameters
$$2.\,\,\,\,$$ Register saves and restores
$$3.\,\,\,\,$$ Instruction fetches

For all delayed conditional branch instructions, irrespective of whether the condition evaluate true or false,

Which of the following is/are true of the auto increment addressing mode?
$$1.$$ It is useful in creating self relocating code
$$2.$$ If it is included in an Instruction Set Architecture, then an additional $$ALU$$ is required for effective address calculation
$$3.$$ The amount of increment depends on the size of the data item accessed.

Which of the following must be true for the $$RFE$$ (Return From Exception) instruction on a general purpose processor?
$$1.$$ It must be a trap instruction
$$2.$$ It must be a privileged instruction
$$3.$$ An exception cannot be allowed to occur during execution of an $$RFE$$ instruction.

Which of the following are NOT true in a pipelined processor?
$$1.$$ Bypassing can handle all RAW hazards
$$2.$$ Register renaming can eliminate all register carried WAR hazards
$$3.$$ Control hazard penalties can be eliminated by dynamic branch prediction.

In an instruction execution pipeline, the earliest that the data $$TLB$$ (Translation Look aside Buffer) can be accessed is

The following code is to run on a pipelined processor with one branch delay slot
$$\eqalign{ & {{\rm I}_1}:\,\,ADD\,\,{R_2}\,\, \leftarrow \,\,{R_7} + {R_8} \cr & {{\rm I}_2}:\,\,SUB\,\,\,{R_4}\,\, \leftarrow \,\,{R_5} - {R_6} \cr & {{\rm I}_3}:\,\,ADD\,\,{R_1}\,\, \leftarrow \,\,{R_2} + {R_3} \cr & {{\rm I}_4}:\,\,STORE\,\,Memory\,\,\left[ {{R_4}} \right]\,\, \leftarrow \,\,{R_1} \cr & BRANCH\,\,to\,\,Label\,\,if\,\,{R_1} = = 0 \cr} $$

Which of the instructions $${{\rm I}_1},\,{{\rm I}_2},\,{{\rm I}_3}$$ or $${{\rm I}_4}$$ can legitimately occupy the delay slot without any other program modification?

For inclusion to hold between two cache levels $$L1$$ and $$L2$$ in a multilevel cache hierarchy, which of the following are necessary?

$$1.$$ $$L1$$ must be a write-through cache
$$2.$$ $$L2$$ must be a write-through cache
$$3.$$ The associativity of $$L2$$ must be greater than that of $$L1$$
$$4.$$ The $$L2$$ cache must be at least as large as the $$L1$$ cache

In the $$IEEE$$ floating point representation the hexadecimal value $$0\, \times \,00000000$$ corresponds to

Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records with keys

43 36 92 87 11 4 71 13 14 is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?

Consider the following sequence of nodes for the undirected graph given below.
1.a b e f d g c
2.a b e f c g d
3.a d g e b c f
4.a d b c g e f
A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the above is (are) possible output(s)?

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,..........., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

How many distinct BSTs can be constructed with 3 distinct keys?

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Which of the following statements is TRUE?

A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys.
I. 81, 537, 102, 439, 285, 376, 305
II. 52, 97, 121, 195, 242, 381, 472
III. 142, 248, 520, 386, 345, 270, 307
IV. 550, 149, 507, 395, 463, 402, 270
Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which. MBCAFHPYK KAMCBYPFH MABCKYFPH Pick the true statement from the following.

Which of the following is TRUE?

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution?

struct node { 
    int value; 
    struct node *next; 
}; 

Void rearrange (struct node *list ){ 
    struct node *p, * q; 
    int temp; 
    if( !list || !list-> next) return; 
    p = list; q = list->next; 
    while (q) { 
      temp = p->value; 
      p-> value = q ->value; 
      q-> value = temp; 
      p = q-> next; 
      q = p ? p->next : 0; 
    } 
}

Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field, and the file organization is unspanned. The file is stored in a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the file, and a multi-level index scheme is used to store the secondary index, the number of first-level and second-level blocks in the multi-level index are respectively

A clustering index is defined on the fields which are of type

Consider the following three schedules of transactions T₁, T₂ and T₃.
[ Notation: In the following NYO represents the action Y (R for read, W for write) performed by transac­tion N on object O. ]

(S1) 2RA 2WA 3RC 2WB 3WA 3WC 1RA 1RB 1WA 1WB

(S2) 3RC 2RA 2WA 2WB 3WA 1RA 1RB 1WA 1WB 3WC

(S3) 2RZ 3RC 3WA 2WA 2WB 3WC 1RA 1RB 1WA 1WB

Which of the following statements is TRUE?

Let R and S be two relations with the following schema

R (P, Q, R1, R2, R3)

S (P, Q, S1, S2)

Where {P, Q} is the key for both schemas. Which of the following queries are equivalent?
I. $$\Pi_P \left(R \bowtie S\right)$$
II. $$\Pi_P \left(R\right) \bowtie \Pi_P\left(S\right)$$
III. $$\Pi_P \left(\Pi_{P, Q} \left(R\right) \cap \Pi_{P,Q} \left(S\right) \right)$$
IV. $$\Pi_P \left(\Pi_{P, Q} \left(R\right) - \left(\Pi_{P,Q} \left(R\right) - \Pi_{P,Q} \left(S\right)\right)\right)$$

Which of the following tuple relational calculus expression(s) is/are equivalent to $$\forall t \in r \left(P\left(t\right)\right)$$?

I. $$\neg \exists t \in r \left(P\left(t\right)\right)$$
II. $$\exists t \notin r \left(P\left(t\right)\right)$$
III. $$\neg \exists t \in r \left(\neg P\left(t\right)\right)$$
IV. $$\exists t \notin r \left(\neg P\left(t\right)\right)$$

Consider The Following Relational Scheme

Student (school-id, sch-roll-no, sname, saddress)
School (school-id, sch-name, sch-address, sch-phone)
Enrolment (school-id, sch-roll-no, erollno, examname)
ExamResult (Erollno, examname, marks)

What does the following SQL query output?

SELECT sch-name, COUNT (*) 
FROM School C, Enrolment E, 
ExamResult R 
WHERE E.school-id = C.school-id 
AND E.examname = R.examname 
AND E.erollno = R.erollno
AND R.marks = 100 AND S.school-id IN 
(SELECT school-id 
 FROM student 
 GROUP BY school-id 
 HAVING COUNT (*) > 200) 
GROUP BY school-id;

Consider The Following Relational Scheme

Student (school-id, sch-roll-no, sname, saddress)
School (school-id, sch-name, sch-address, sch-phone)
Enrolment (school-id, sch-roll-no, erollno, examname)
ExamResult (Erollno, examname, marks)

Consider the following tuple relational calculus query

{ t | ∃E ∈ Enrolment t = E.school-id ∧ 
| { x | x ∈ ExamResult B.school-id = 
t ∧ ( ∃B ∈ ExamResult B.erollno = 
x.erollno ∧ B.examname = x.examname ∧ 
B.marks > 35 } | ÷ | 
{ x | x ∈ Enrolment ∧ x.school-id = t } 
| * 100 > 35 }

If a student needs to score more than 35 marks to pass an exam what does the query return?

Let $$R\left( {A,\,B,\,C,\,D,E,P,G} \right)$$ be a relational schema in which the following functional dependencies are known to hold: $$AB \to CD,\,\,DE \to P,\,\,C \to E.\,\,P \to C$$ and $$B \to G.$$ The relational schema $$R$$ is

Let $$R\left( {A,B,C,D} \right)$$ be a relational schema with the following functional dependencies:
$$A \to B,\,\,B \to C,\,\,C \to D$$ and $$D \to B.$$
The decomposition of $$R$$ into $$(A,B), (B,C)$$ and $$(B,D)$$

Consider the following relational schemes for a library database. Book ( Title, Author, Catalog_ no, Publisher, Year, Pr ice ) Collection ( Title, Author, Catalog no )
With in the following functional dependencies:
$${\rm I}.\,\,\,\,\,\,$$ Title Author $$ \to $$ Catalog_no
$${\rm II}.\,\,\,\,$$ Catalog_no $$ \to $$ Title Author Publisher Year
$${\rm III}.\,\,\,\,$$ Publisher Title Year $$ \to $$ Price

Assume { Author, Title } is the key for both schemes. Which of the following statements is true?

Consider the following $$ER$$ diagram

Which of the following is a correct attribute set for one of the tables for the correct answer to the above question?

Consider the following $$ER$$ diagram

The minimum number of table needed to represent $$M,$$ $$N,$$ $$P, R1, R2$$ is

In the Karnaugh map shown below, $$X$$ denotes a don’t care term. What is the minimal form of the function represented by the Karnaugh map?

If $$P, Q, R$$ are Boolean variables, then $$\left( {P + \overline Q } \right)$$ $$\left( {P.\overline Q + P.R} \right)\left( {\overline P .\overline R + \overline Q } \right)$$ Simplifies to

Given $${f_1},$$ $${f_3},$$ and $$f$$ in canonical sum of products form (in decimal) for the circuit. $$${f_1} = \sum {m\left( {4,5,6,7,8} \right)} $$$ $$${f_3} = \sum {m\left( {1,6,15} \right)} $$$ $$$f = \sum {m\left( {1,6,8,15} \right)} $$$
Then $${f_2}$$ is

$$\mathop {\lim }\limits_{x \to \infty } {{x - \sin x} \over {x + \cos \,x}}\,\,Equals$$

A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbours.

Starting with the above tree, while there remains a node $$v$$ of degree two in the tree, add an edge between the two neighbours of $$v$$ and then remove $$v$$ from the tree. How many edges will remain at the end of the process?

A binary tree with $$n>1$$ nodes has $${n_1}$$, $${n_2}$$ and $${n_3}$$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbours.

$${n_3}$$ can be expressed as:

$$G$$ is a graph on $$n$$ vertices and $$2n-2$$ edges. The edges of $$G$$ can be partitioned into two edge-disjoint spanning trees. Which of the following in NOT true for $$G$$?

$$G$$ is a simple undirected graph. Some vertices of $$G$$ are of odd degree. Add a node $$v$$ to $$G$$ and make it adjacent to each odd degree vertex of $$G$$. The resultant graph is sure to be

Which of the following statements is true for every planar graph on $$n$$ vertices?

When $$n = {2^{2k}}$$ for some $$k \ge 0$$, the recurrence relation $$$T\left( n \right) = \sqrt 2 T\left( {n/2} \right) + \sqrt n ,\,\,T\left( 1 \right) = 1$$$
evaluates to

In how many ways can $$b$$ blue balls and $$r$$ red balls be distributed in $$n$$ distinct boxes?

The exponent of $$11$$ in the prime factorization of $$300!$$ is

Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contains no consecutive $$0s$$.

Which of the following recurrences does $${x_n}$$ satisfy?

Let $${x_n}$$ denote the number of binary strings of length $$n$$ that contain no consecutive $$0s$$.

The value of $${x_5}$$ is

What is the chromatic number of the following graph?

A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve $$3{x^4} - 16{x^3} + 24{x^2} + 37$$ is

If $$\,\,\,\,f\,\,\,\,\left( x \right)$$ is defined as follows, what is the minimum value of $$f\,\left( x \right)$$ for $$x \in \left( {0,2} \right)$$ ? $$$f\left( x \right) = \left\{ {\matrix{ {{{25} \over {8x}}\,\,when\,\,x \le {3 \over 2}} \cr {x + {1 \over x}other\,wise} \cr } } \right.$$$

How many of the following matrices have an eigen value $$1$$?
$$\left[ {\matrix{ 1 & 0 \cr 0 & 0 \cr } } \right],\,\,\left[ {\matrix{ 0 & 1 \cr 0 & 0 \cr } } \right],\,\,\left[ {\matrix{ 1 & { - 1} \cr 1 & 1 \cr } } \right]\,\,and\,\,\left[ {\matrix{ { - 1} & 0 \cr 1 & { - 1} \cr } } \right]$$

What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?

The following system of equations
$${x_1}\, + \,{x_2}\, + 2{x_3}\, = 1$$
$${x_1}\, + \,2 {x_2}\, + 3{x_3}\, = 2$$
$${x_1}\, + \,4{x_2}\, + a{x_3}\, = 4$$ has a unique solution. The only possible value (s) for $$\alpha $$ is/are

If $$P, Q, R$$ are subsets of the universal set $$U$$, then
$$\left( {P \cap Q \cap R} \right) \cup \left( {{P^c} \cap Q \cap R} \right) \cup {Q^c} \cup {R^c}$$ is

What is the probability that in a randomly choosen group of r people at least three people have the same birthday?

Which of the following is the negation of $$$\left[ {\forall x,\alpha \to \left( {\exists y,\beta \to \left( {\forall u,\exists v,\gamma } \right)} \right)} \right]?$$$

$$P$$ and $$Q$$ are two propositions. Which of the following logical expressions are equivalent?

$${\rm I}.$$ $${\rm P}\, \vee \sim Q$$
$${\rm I}{\rm I}.$$ $$ \sim \left( { \sim {\rm P} \wedge Q} \right)$$
$${\rm I}{\rm I}{\rm I}.$$ $$\left( {{\rm P} \wedge Q} \right) \vee \left( {{\rm P} \wedge \sim Q} \right) \vee \left( { \sim {\rm P} \wedge \sim Q} \right)$$
$${\rm I}V.$$ $$\left( {{\rm P} \wedge Q} \right) \vee \left( {{\rm P} \wedge \sim Q} \right) \vee \left( { \sim {\rm P} \wedge Q} \right)$$

Which of the following first order formulae is logically valid? Here $$\alpha \left( x \right)$$ is a first order formulae with $$x$$ as a free variable, and $$\beta $$ is a first order formula with no free variable.

Let fsa and $$pda$$ be two predicates such that fsa$$(x)$$ means $$x$$ is a finite state automation, and pda$$(y)$$ means that $$y$$ is a pushdown automation. Let $$equivalent$$ be another predicate such that $$equivalent$$$$(a,b)$$ means $$a$$ and $$b$$ are equivalent. Which of the following first order logic statements represents the following:

Each finite state automation has an equivalent pushdown automation.

If $$P$$, $$Q$$, $$R$$ are Boolean variables, then $$(P + \bar{Q}) (P.\bar{Q} + P.R) (\bar{P}.\bar{R} + \bar{Q})$$ simplifies to

Let X be a random variable following normal distribution with mean + 1 and variance 4. Let Y be another normal variable with mean - 1 and variance unknown. If $$P\,(X\, \le \, - 1) = \,P(Y\,\, \ge \,2)$$, the standard deviation of Y is

Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that the studies mathematics the next day is 0.6. If she studies mathematics on a day, then the probability that she studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday, what is the probability that she studies computer science on Wednesday?

A sample space has two events A and B such that probabilities $$P\,(A\, \cap \,B)\, = \,1/2,\,\,P(\overline A )\, = \,1/3,\,\,P(\overline B )\, = \,1/3$$.
What is P $$P\,(A\, \cup \,B)\,$$?

A set of Boolean connectives is functionally complete if all Boolean function can be synthesized using those, Which of the following sets of connectives is NOT functionally complete?

The value of $$\int\limits_0^3 {\int\limits_0^x {\left( {6 - x - y} \right)dxdy\,\,\,} } $$ is _____.

If $$M$$ is a square matrix with a zero determinant, which of the following assertion(s) is (are) correct?
$$S1$$ : Each row of $$M$$ can be represented as a linear combination of the other rows
$$S2$$ : Each column of $$M$$ can be represented as a linear combination of the other columns
$$S3$$ : $$MX$$ $$=$$ $$0$$ has a nontrivial solution
$$S4$$ : $$M$$ has an inverse

A processor uses 36 bit physical addresses and 32 bit virtual addresses, with a page frame size of 4 Kbytes. Each page table entry is of size 4 bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows:
$$ * \,\,\,\,\,\,$$ Bits 30-31 are used to index into the first level page table
$$ * \,\,\,\,\,\,$$ Bits 21-29 are used to index into the second level page table
$$ * \,\,\,\,\,\,$$ Bits 12-20 are used to index into the third level page table, and
$$ * \,\,\,\,\,\,$$ Bits 0-11 are used as offset within the page

The number of bits required for addressing the next level page table (or page frame) in the page table entry of the first, second and third level page tables are respectively

Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?

For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to

The data blocks of a very large file in the Unix file system are allocated using

The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows:

P(s): s = s-1; 
if s < 0 then wait; 
V(s) : s = s-1; 
ifs <= 0 then wakeup a process waiting on s;

Assume that P_b and V_b the wait and signal operations on binary semaphores are provided. Two binary semaphores X_b and Y_b are used to implement the semaphore operations P(s) and V(s) as follows:

  P(s): Pb (Xb);
        S = s - 1;
        if(s < 0){
          Vb(Xb);
          Pb(Yb);
        }
        Else Vb (Xb);
  V(s): Pb (Xb);
        S = s + 1;
        if(s <= 0) Vb(Yb);
        Vb(Xb);

The initial values of X_b and Y_b are respectively

Which of the following is/are true of the auto-increment addressing mode?
$${\rm I}.\,\,\,$$ It is useful in creating self-relocating code
$${\rm II}.\,\,\,$$ If it is included in an Instruction Set Architecture, then an additional $$ALU$$ is required for effective address calculation.
$${\rm III}.\,\,\,$$ The amount of increment depends on the size of the data item accessed

A process executes the following code

for (i = 0; i < n; i + +) fork ( ); 

The total number of child processes created is

What is printed by the following C program?

#include < stdio.h >
int f(int x, int *py, int **ppz)
{
   int y, z;
  **ppz += 1; 
   z  = **ppz;
  *py += 2;
   y = *py;
   x += 3;
   return x + y + z;
}
 
void main()
{
   int c, *b, **a;
   c = 4;
   b = &c;
   a = &b; 
   printf( "%d", f(c,b,a));
   getchar();
}

Choose the correct option to fill ? 1 and ? 2 so that the program below prints an input string in reverse order. Assume that the input string is terminated by a newline character.

void recerse (void) {
  int c;
  if (?1) reverse() ;
  ?2
}
main {
  printf ("Enter Text" ); 
  printf("\n");
  reverse() ;
  printf("\n") ;
}

Which of the following are true?

I. A programming language which does not permit global variables of any kind and has no nesting of procedures/functions, but permits recursion can be implemented with static storage allocation

II. Multi-level access link (or display) arrangement is needed to arrange activation records only if the programming language being implemented has nesting of procedures/functions

III. Recursion in programming languages cannot be implemented with dynamic storage allocation

IV. Nesting procedures/functions and recursion require a dynamic heap allocation scheme and cannot be implemented with a stack-based allocation scheme for activation records

V. Programming languages which permit a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records

Which of the following are decidable?
$$1.$$ Whether the intersection of two regular languages is infinite
$$2.$$ Whether a given context-free language is regular
$$3.$$ Whether two push-down automata accept the same language
$$4.$$ Whether a given grammar is context-free

Which of the following statements are true?
$$1.$$ Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa
$$2.$$ All ε-productions can be removed from any context-free grammar by suitable transformations
$$3.$$ The language generated by a context-free grammar all of whose productions are of the form $$X \to w$$ or $$X \to wY$$ (where, $$w$$ is a string of terminals and $$Y$$ is a non terminal), is always regular
$$4.$$ The derivation trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees

If $$L$$ and $$\overline L $$ are recursively enumerable then $$L$$ is

Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?

Match the following List-$${\rm I}$$ with List - $${\rm II}$$

List-$${\rm I}$$
$$E)$$ Checking that identifiers are declared before their
$$F)$$ Number of formal parameters in the declaration of a function agrees with the number of actual parameters in a use of that function
$$G)$$ Arithmetic expression with matched pairs of parentheses
$$H)$$ Palindromes

List-$${\rm II}$$
$$P)$$ $$L = \left\{ {{a^n}{b^m}{c^n}{d^m}\,|\,n \ge 1,m \ge 1} \right\}$$
$$Q)$$ $$X \to XbX\,|\,XcX\,|\,dXf\,|g$$
$$R)$$ $$L = \left\{ {www\,|\,w \in \left( {a\,|\,b} \right){}^ * } \right\}$$
$$S)$$ $$X \to bXB\,|\,cXc\,|\,\varepsilon $$

Which of the following statement is false?

Which of the following are regular sets?

Match the following $$NFAs$$ with the regular expressions they correspond to

Given below are two finite state automata ($$ \to $$ indicates the start state and $$F$$ indicates a final state)

Which of the following represents the product automation $$ZY$$?