The problems 3-SAT and 2-SAT are

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source.
In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?

The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given order into a max Heap. The resultant max Heap is

The recurrence equation
T(1) = 1
T(n) = 2T(n - 1)+n, $$n \ge 2$$
Evaluates to

What does the following algorithm approximate?
(Assume m > 1, $$ \in > 0$$)

x = m;
y = 1;
while(x - y > ε){
 x = (x + y) / 2;
 y = m/x;
}
print(x);

The time complexity of the following C function is (assume n > 0)

int recursive(int n){
 if(n == 1){
   return (1);
 }
 return (recursive(n - 1) + recursive(n - 1));
}

Let A[1,...,n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is O(m). Consider the following program fragment written in a C like language:

counter = 0;
for(i = 1; i <= n; i++){
 if(A[i]==1){
   counter++;
 }else{
   f(counter); counter = 0;
 }
}

The complexity of this program fragment is

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

Consider the grammar rule $$E \to {E_1} - {E_2}$$ for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E₁ and E₂ do not have any common sub-expression, in order to get the shortest possible code.

Consider the grammar with the following translation rules and E as the start symbol.

$$\eqalign{ & E \to {E_1}\# T\,\,\left\{ {E.value = {E_1}.value*T.value} \right\} \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,|T\,\,\,\,\,\,\,\,\,\,\,\,\left\{ {E.value = T.value} \right\} \cr & T \to {T_1}\& F\,\,\,\left\{ {T.value = {T_1}.value*F.value} \right\} \cr & \,\,\,\,\,\,\,\,\,\,\,\,\,\,|\,F\,\,\,\,\,\,\,\,\,\,\,\left\{ {T.value = F.value} \right\} \cr & F \to num\,\,\,\,\,\,\,\left\{ {F.value = num.value} \right\} \cr} $$

Compute E.value for the root of the parse tree for the expression:
2 # 3 & 5 # 6 & 4.

Which of the following grammar rules violate the requirements of an operator grammar? P, Q, R are nonterminals, and r, s, t are terminals.

$$\eqalign{ & 1.\,P \to QR \cr & 2.\,P \to QsR \cr & 3.\,P \to \varepsilon \cr & 4.\,P \to QtRr \cr} $$

Choose the best matching between Group 1 and Group 2 :

Group –1

P. Data link layer
Q. Network layer
R. Transport layer

Group – 2

1. Ensures reliable transport of data over a physical point-to-point link
2. Encodes/decodes data for physical transimission
3. Allows end-to-end communication between two processes
4. Routes data from one network node to the next

Suppose that the maximum transmit window size for a TCP connection is 12000 bytes. Each packet consists of 2000 bytes. At some point of time, the connection is slow start phase with a current transmit window of 4000 bytes. Subsequently, the transmitter receiver two acknowledgments. Assume that no packet are lost and there are no time-outs. What is the maximum possible value of the current transmit window?

A TCP message consisting of 2100 bytes is passed to IP for delivery across two networks. The first network can carry a maximum payload of 1200 bytes per frame and the second network can carry a maximum payload of 400 bytes per frame, excluding network overhead. Assume that IP overhead per packet is 20 bytes. What is the total IP overhead in the second network for this transmission?

Consider three IP networks A, B and C. Host H_A in networks A sends messages each containing 180 bytes of application data to a host H_C in network C. The TCP layer prefixes a 20 byte header to the message. This passes through an intermediate network B. the maximum packet size, including 20 byte IP header, in each network is:

A : 1000 bytes
B : 100 bytes
C : 1000 bytes

The network A and B are connected through a 1 Mbps link, while B and C are connected by a 512 Kbps link (bps = bits per second).

What is the rate at which application data is transferred to host H_C? Ignore errors, acknowledgements, and other overheads.

Consider three IP networks A, B and C. Host H_A in networks A sends messages each containing 180 bytes of application data to a host H_C in network C. The TCP layer prefixes a 20 byte header to the message. This passes through an intermediate network B. the maximum packet size, including 20 byte IP header, in each network is:

A : 1000 bytes
B : 100 bytes
C : 1000 bytes

The network A and B are connected through a 1 Mbps link, while B and C are connected by a 512 Kbps link (bps = bits per second).

Assuming that the packets are correctly delivered, how many bytes, including headers, are delivered to the IP layer at the destination for one application message, in the best case? Consider only data packets.

The routing table of a router is shown below:

On which interface will the router forward packets addressed to destinations 128.75.43.16 and 192.12.17.10 respectively?

Which of the following is NOT true with respect to a transparent bridge and a router?

A and B are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both A and B attempt to transmit a frame, collide, and A wins the first backoff race. At the end of this successful transmission by A, both A and B attempt to transmit and collide. The probability that A wins the second backoff race is

A sender is employing public key Cryptography to send a secret message to a receiver. Which one of the following statement is true?

Consider the following program segment for a hypothetical $$CPU$$ having three user registers $$R1,R2, $$ and $$R3.$$

Let the clock cycles required for various operations be as follows:
Register to/from memory transfer:
$$3$$ clock cycles
ADD with both operands in register:
$$1$$ clock cycle
Instruction fetch and decode:
$$2$$ clock cycles per word

The total number of clock cycle required to execute the program is

Consider the following program segment for a hypothetical $$CPU$$ having three user registers $$R1,R2, $$ and $$R3.$$

Consider that the memory is byte addressable with word size $$32$$ bits, and the program has been loaded starting from memory location $$1000$$ (decimal). If an interrupt occurs while the $$CPU$$ has been halted after executing the HALT instruction, the return address (in decimal) saved in the stack will be

Which of the following addressing modes are suitable for program relocation at run time?
$$1.$$ Absolute addressing
$$2.$$ Based addressing
$$3.$$ Relative addressing
$$4.$$ Indirect addressing

A $$4$$-stage pipeline has the stage delays as $$150, 120,160$$ and $$140$$ nano seconds respectively. Registers that are used between the stages have a delay of $$5$$ nanoseconds each. Assuming constant clocking rate, the total time taken to process $$1000$$ data items on this pipeline will be

Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, uses the least recently used $$(LRU)$$ scheme. The number of cache misses for the following sequence of blocks addresses is $$8,12,0,12,8$$

The microinstructions stored in the control memory of a processor have a width of $$26$$ bits. Each microinstruction is divided into three fields: a micro-operation of $$13$$ bits, a next address field $$(X),$$ and a $$MUX$$ select field $$(Y).$$ There are $$8$$ status bits in the inputs of the $$MUX$$.

How many bits are there in the $$X$$ and $$Y$$ fields, and what is the size of the control memory in number of words?

A Hard disk with a transfer rate of $$10Mbytes/second$$ is constantly transferring data to memory using $$DMA.$$ The processor runs at $$600MHz$$ and takes $$300$$ and $$900$$ clock cycles to initiate and complete $$DMA$$ transfer respectively. The size of the data transfer is $$20$$ $$KB.$$ What is the $$\% $$ of processor time consumed for this operation ?

How many $$8$$-bit characters can be transmitted per second over $$9600$$ baud serial communication link using a parity synchronous mode of transmission with one start bit & Eight data bits, two stop bits, and one parity bit

Which one of the following is true for a $$CPU$$ having a single interrupt request line and single interrupt grant line?

$$A$$ $$4$$-bit carry look ahead adder, which adds two $$4$$-bit numbers, is designed using $$AND,$$ $$OR,$$ $$NOT,$$ $$NAND,$$ $$NOR$$ gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the adder? Assume that the carry network has been implemented using two-level $$AND$$-$$OR$$ logic.

What is the result of evaluating the following two expressions using three $$-$$ digit floating point arithmetic with rounding?
$$\eqalign{ & \left( {113. + - 111.} \right) + 7.51 \cr & 113. + \left( { - 111. + 7.51} \right) \cr} $$

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
i) 9679, 1989, 4199 hash to the same value
ii) 1471, 6171 has to the same value
iii) All elements hash to the same value
iv) Each element hashes to a different value

In a depth-first traversal of a graph G with n vertices,k edges are marked as tree edges. The number of connected components in G is

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?
i) preorder and postorder
ii) inorder and postorder
iii) preorder and inorder
iv) level order and postorder

Consider the following C program segment

struct CellNode{ 
    struct CellNode *leftChild; 
    int element; 
    struct CellNode *rightChild; 
  };
 
int Dosomething (struct CellNode *ptr) { 
      int value = 0; 
      if (ptr ! = NULL) 
          { if (ptr - > leftChild ! = NULL) 
            value = 1 + DoSomething (ptr - > leftChild); 
          if (ptr - > rightChild ! = NULL) 
            value = max(value,1 + DoSomething (ptr - > rightChild)); 
          } 
      return (value); 
} 

The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

Level order traversal of a rooted tree can be done by starting from the root and performing

Let P be a singly linked list, Let Q be the pointer to an intermediate node x in the list.What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{ no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x } then the worst-case time complexity of the program is

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

A program attempts to generate as many permutation as possible of the string “abcd” by pushing the character a,b,c,d in the same order onto a stack, but it may pop off the top character at any time. Which one of the following a strings CANNOT be generated using this program?

Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, ×, +, -. The postfix expression corresponding to the infix expression a + b×c-d^e^f is

The best data structure to check whether an arithmetic expression has balanced parentheses is a

Two matrices M₁ and M₂ are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M₁$$\times$$ M₂ will be

A single array A[1..MAXSIZE] is used to implement two stacks, The two stacks grow from opposite ends of the array. Variables top1 and top2 (top1 < top2) point to the location of the topmost element in each of the stacks, If the space is to be used efficiently, the condition for "stack full" is

Consider the relation Student (name, sex, marks), where the primary key is shown underlined, pertaining to students in a class that has at least one boy and one girl. What does the following relational algebra expression produce? (Note: ρ is the rename operator).

The order of an internal node in a B⁺ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?

Consider a table T in a relational database with a key field K. A B-tree of order p is used as an access structure on K, where p denotes the maximum number of tree pointers in a B-tree index node. Assume that K is 10 bytes long; disk block size is 512 bytes; each data pointer P_D is 8 bytes long and each block pointer P_B is 5 bytes long. In order for each B-tree node to fit in a single disk block, the maximum value of p is

Consider the following schedule S of transactions T1 and T2: Which of the following is TRUE about the schedule S?

Which level of locking provides the highest degree of concurrency in a relational database?

Let R₁ (A, B, C) and R₂ (D, E) be two relation schema, where the primary keys are shown underlined, and let C be a foreign key in R₁ referring to R₂. Suppose there is no violation of the above referential integrity constraint in the corresponding relation instances r₁ and r₂. Which one of the following relational algebra expressions would necessarily produce an empty relation?

Consider two tables in a relational database with columns and rows as follows:

 Table: Student

Roll_no	Name	Dept_id
1	ABC	1
2	DEF	1
3	GHI	2
4	JKL	3

 Table: Department

Dept_id	Dept_name
1	A
2	B
3	C

Roll_no is the primary key of the Student table, Dept_id is the primary key of the Department table and Studetn.Dept_id is a foreign key from
Department. Dept_id.

What will happen if we try to execute the following two SQL statements?

(i) update Student set Dept_id = Null where Roll_no =1
(ii) update Department set Dept_id = Null where Dept_id =1

A relational database contains two table student and department in which student table has columns roll_no, name and dept_id and department table has columns dept_id and detp_name. the following insert statements were executed successfully to populate the empty tables:

 Insert into department values (1, ‘Mathematics’)
 Insert into department values (2, ‘Physics’)
 Insert into student values (1, ‘Navin’,1)
 Insert into student values (2, ‘Mukesh’,2)
 Insert into student values (3, ‘Gita’,1)

How many rows and columns will be retrieved by the following SQL statement?

Select * from student, department;

The employee information in a company is stored in the relation

Employee (name, sex, salary, deptName)

Consider the following SQL query

  Select deptName
  From Employee
  Where sex = ‘M’
  Group by deptName
  Having avg(salary) >
  (Select avg (salary) From Employee);

It returns the names of the department in which

Consider the following relation schema pertaining to a students database:

Students (rollno, name, address)
Enroll(rollno,courseno, coursename)

Where the primary keys are shown underlined. The number of tuples in the student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where '*' denotes natural join?

The relation scheme student Performance (Name, CourseNo, RollNo, Grade) has the following functional dependencies:

Name, courseNo $$\,\, \to \,\,$$ grade
RollNo, courseNo $$\,\, \to \,\,$$ grade
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,$$ Name $$\,\, \to \,\,$$ rollNo
$$\,\,\,\,\,\,\,\,\,\,\,\,\,$$$$\,\,\,\,\,\,\,\,\,$$ RollNo $$\,\, \to \,\,$$ name

The highest normal form of this relation scheme is

A relation Empdt $$1$$ is defined with attributes empcode (unique), name, street, city, state and pincode. For any pincode, there is only one city and state. Also, for any given street city and the state, there is just one pincode. In normalization terms, Empdt$$1$$ is a relation in

Consider the following entity relationship diagram $$(ERD),$$ where two entities $$E1$$ and $$E2$$ have a relation $$R$$ of cardinality $$1:m.$$

The attributes of $$E1$$ are $$A11, A12$$ and $$A13$$ where $$A11$$ is the key attribute. The attributes of $$E2$$ are $$A21, A22$$ and $$A23$$ where $$A21$$ is the key attribute and $$A23$$ is a multi-valued attribute. Relation $$R$$ does not have any attribute. A relational database containing minimum number of tables with each table satisfying the requirements of the third normal form $$(3NF)$$ is designed form the above $$ERD.$$ The minimum number of tables in the database is

Consider the partial implementation of a $$2$$-bit counter using $$T$$ flip-flops following the sequence $$0$$-$$2$$-$$3$$-$$1$$-$$0,$$ as shown below.

To complete the circuit, the input $$X$$ should be

$$SR.$$ latch made by cross coupling two $$NAND$$ gates if $$S=R=0,$$ Then it will result in

Consider a multiplexer with $$X$$ and $$Y$$ as data inputs and $$Z$$ as control input. If $$z=0$$ select input $$x,$$ and $$z=1$$ selects input $$Y$$. what are the connections required to realize the $$2-$$variable Boolean function $$f=T+R$$ without using any additional Hardware?

A circuit outputs a digit in the form of $$4$$ bits. $$0$$ is represented by $$0000$$, $$1$$ by $$0001..., $$ $$9$$ by $$1001.$$ A combinational circuit is to be designed which takes these $$4$$ bits as input and outputs $$1$$ if the digit $$ \ge 5,$$ and $$0$$ otherwise. If only $$AND,$$ $$OR$$ and $$NOT$$ gates may be used, what is the minimum number of gates required?

Which are the essential prime implicants of the following Boolean function? $$F\left( {a,b,c} \right) = {a^1}c + a{c^1} + {b^1}c$$

The Boolean function $$x'y' +xy +x'y$$ is equivalent to

Let $$A=1111$$ $$1010$$ and $$B=0000$$ $$1010$$ be two $$8$$-bit $$2's$$ complement numbers. Their product in $$2's$$ complement is

$${73_x}$$ (in base $$-$$ $$x$$ number system) is equal to $${54_y}$$ (in base $$-y$$ number system), the possible values of $$x$$ and $$y$$ are

In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 student have taken Computer Organization coures; 50 students have taken both Programming Language and Data Structures, 35 students have taken both Programming Languages and Computer Organization; 30 students have taken both Data Structures and Computer Organization; 15 students have taken all the three course.

How many students have not taken any of the three courses?

What is the number of vertices in an undirected connected graph with $$27$$ edges, $$6$$ vertices of degree $$2$$, $$\,\,$$ $$3$$ vertices of degree 4 and remaining of degree 3?

Let $${G_1} = \left( {V,\,{E_1}} \right)$$ and $${G_2} = \left( {V,\,{E_2}} \right)$$ be connected graphs on the same vertex set $$V$$ with more than two vertices. If $${G_1} \cap {G_2} = \left( {V,{E_1} \cap {E_2}} \right)$$ is not a connected graph, then the graph $${G_1} \cup {G_2} = \left( {V,{E_1} \cup {E_2}} \right)$$

How many graphs on $$n$$ labeled vertices exist which have at least $$\left( {{n^2} - 3n} \right)/2\,\,\,$$ edges?

In an M$$ \times $$N matrix such that all non-zero entries are covered in $$a$$ rows and $$b$$ columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is

If matrix $$X = \left[ {\matrix{ a & 1 \cr { - {a^2} + a - 1} & {1 - a} \cr } } \right]$$
and $${X^2} - X + 1 = 0$$
($${\rm I}$$ is the identity matrix and $$O$$ is the zero matrix), then the inverse of $$X$$ is

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is

Let $$A$$ be and n$$ \times $$n matrix of the folowing form.

What is the value of the determinant of $$A$$?

How many solutions does the following system of linear equations have?

- x + 5y = - 1
x - y = 2
x + 3y = 3

The recurrence equation
$$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$
$$\,\,\,\,\,\,T\left( n \right) = 2T\left( {n - 1} \right) + n,\,n \ge 2$$
evaluates to

In how many ways can we distribute 5 distinct balls, $${B_1},{B_2},......,{B_5}$$ in 5 distinct cells, $${C_1},{C_2},.....,{C_5}$$ such that Ball $${B_i}$$ is not in cell $${C_i}$$, $$\forall i = 1,2,....,5$$ and each cell contains exactly one ball?

Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of $$k$$ colours, such that the colour-pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of $$k$$ that satisfies this requirement?

What is the maximum number of edges in an acyclic undirected graph with $$n$$ vertices?

What values of x, y and z satisfy the following system of linear equations? $$$\left[ {\matrix{ 1 & 2 & 3 \cr 1 & 3 & 4 \cr 2 & 3 & 3 \cr } } \right]\,\,\left[ {\matrix{ x \cr y \cr z \cr } } \right]\,\, = \,\left[ {\matrix{ 6 \cr 8 \cr {12} \cr } } \right]$$$

Let A, B, C, D be $$n\,\, \times \,\,n$$ matrices, each with non-zero determination. If ABCD = I, then $${B^{ - 1}}$$ is

The number of different $$n \times n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is

Let $${R_1}$$ be a relation from $$A = \left\{ {1,3,5,7} \right\}$$ to $$B = \left\{ {2,4,6,8} \right\}$$ and $${R_2}$$ be another relation from $$B$$ to $$C$$ $$ = \left\{ {1,2,3,4} \right\}$$ as defined below:

i) An element $$x$$ in $$A$$ is related to an element $$y$$ in $$B$$ (under $${R_1}$$) if $$ x + y $$ is divisible by $$3$$.
ii) An element EExEE in $$B$$ is related to an elements $$y$$ in $$C$$ (under $${R_2}$$) if $$x + y$$ is even but not divisible by $$3$$.

Which is the composite relation $$R1R2$$ from $$A$$ to $$C$$?

Consider the binary relation: $$S = \left\{ {\left( {x,y} \right)|y = x + 1\,\,and\,\,x,y \in \left\{ {0,1,2,...} \right\}} \right\}$$

The reflexive transitive closure of $$S$$ is

The number of different $$n$$ $$x$$ $$n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is (Note: power ($$2,$$ $$x$$) is same as $${2^x}$$)

The inclusion of which of the following sets into

S = { {1, 2}, 1, 2, 3}, {1, 3, 5}, {1, 2, 4},
{1, 2, 3, 4, 5} }
Is necessary and sufficient to make S a complete lattice under the partial order defined by set containment?

The following is the incomplete operation table of a 4-element group. The last row of the table is

Two n bit binary stings, S1 and, are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings different) is equal to d is

An examination paper has 150 multiple-choice questions of one mark each, with each question having four choices. Each incorrect answer fetches-0.25 mark. Suppose 1000 students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained all these students is

A point is randomly selected with uniform probability in the X-Y plane within the rectangle with corners at
(0, 0), (1, 0), (1, 2) and (0, 2). If p is the length of the position vector of the point, the expected value of $${p^2}$$ is

If a fair coin is tossed four times, what is the probability that two heads and two tails will result?

In a population of N families, 50% of the families have three children, 30% of the families have two children and the remaining families have one child. What is the probability that a randomly picked child belongs to a family with two children ?

Let $$p, q, r$$ and $$s$$ be four primitive statements. Consider the following arguments:

$$P:\left[ {\left( {\neg p \vee q} \right) \wedge \left( {r \to s} \right) \wedge \left( {p \vee r} \right)} \right] \to \left( {\neg s \to q} \right)$$
$$Q:\left[ {\left( {\neg p \wedge q} \right) \wedge \left[ {q \to \left( {p \to r} \right)} \right]} \right] \to \neg r$$
$$R:\left[ {\left[ {\left( {q \wedge r} \right) \to p} \right] \wedge \left( {\neg q \vee p} \right)} \right] \to r$$
$$S:\left[ {p \wedge \left( {p \to r} \right) \wedge \left( {q \vee \neg r} \right)} \right] \to q$$

Which of the above arguments are valid?

The following propositional statement is $$$\left( {P \to \left( {Q \vee R} \right)} \right) \to \left( {\left( {P \wedge Q} \right) \to R} \right)$$$

Let $$a(x,y)$$, $$b(x,y)$$ and $$c(x,y)$$ be three statements with variables $$x$$ and $$y$$ chosen from some universe. Consider the following statement: $$$\left( {\exists x} \right)\left( {\forall y} \right)\left[ {\left( {a\left( {x,\,y} \right) \wedge b\left( {x,\,y} \right)} \right) \wedge \neg c\left( {x,\,y} \right)} \right]$$$

Which one of the following is its equivalent?

Identify the correct translation into logical notation of the following assertion.

$$Some\,boys\,in\,the\,class\,are\,taller\,than\,all\,the\,girls$$
Note: taller$$\left( {x,\,y} \right)$$ is true if $$x$$ is taller than $$y$$.

Consider a System with a two-level paging scheme in which a regular memory access takes $$150$$ nanoseconds, and servicing a page fault takes $$8$$ milliseconds. An average instruction takes $$100$$ nanoseconds of $$CPU$$ time, and two memory accesses. The $$TLB$$ hit ratio is $$90$$% and the page fault rate is one in every $$10,000$$ instructions. What is the effective average instruction execution time?

The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by.

Which of the following addressing modes are suitable for program relocation at run time?
$$1.$$ Absolute addressing
$$2.$$ Based addressing
$$3.$$ Relative addressing
$$4.$$ Indirect addressing

Consider a program $$P$$ that consists of two source modules $${M_1}$$ and $${M_2}$$ contained in two different files. If $${M_1}$$ contains a reference to a function defined in $${M_2}$$, the reference will be resolved at.

Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head scheduling algorithm used is First Come First Served $$(FCFS).$$ If $$FCFS$$ is replaced by Shortest Seek Time First $$(SSTF),$$ claimed by the vendor to give $$50\% $$ better benchmark results, what is the expected improvement in the $${\rm I}/O$$ performance of user programs?

Consider the following set of processes, with the arrival times and the $$CPU$$-burst times given in milliseconds.

What is the average turnaround time for these processes with the preemptive shortest remaining processing time first $$(SRTF)$$ algorithm?

Consider the following statements with respect to user-level threads and kernel-supported threads.
i) Context switch is faster with kernel- supported threads
ii) For user-level threads, a system call can block the entire process
iii) Kernel-supported threads can be scheduled independently
iv) Use-level threads are transparent to the kernel

Which of the above statements are true?

Consider the following C program segment:

char p[20];
char *s = "string";
int length = strlen(s);
for(i=0; i < length; i++)
  p[i] = s[length-i];
printf("%s",p);

The output of the program is

Consider the following C function:

void swap (int a, int b)
{
   int temp;
   temp = a;
   a = b;
   b = temp;
}

In order to exchange the values of two variables x and y.

Consider the following C program

main ( )
{
  int x, y, m, n;
  scanf("%d %d", &x, &y);
  /* Assume x > 0 and y > 0 */
  m=x; n=y;
  while(m!=n)
  {
    if(m>n)
    m=m-n;
    else
    n=n-m;
  }
  printf("%d", n);
}

The program computes

Consider the following C function:

int f(int n)
{
static int i = 1;
if(n>=5) return n;
n = n+1;
i++;
return f(n);
}

The value returned by f(1) is

Choose the best matching between the programming style in Group 1 and their characteristics in Group 2

Group 1
P. Functional
Q. Logic
R. Object-oriented
S. Imperative

Group 2
1. Command-based, procedural
2. Imperative, abstract data types
3. Side-effect free, declaretive, expression Evaluation
4. Declaretive, clausal representation, theorem proving

The goal of structured programming is to

The language $$\left\{ {{a^m}{b^n}{c^{m + n}}\left| {m,n \ge } \right.} \right\}$$ is

Let $$M = \left( {K,\,\sum {,\,F,\,\Delta ,\,s,\,F} } \right)$$ be a pushdown automation. Where $$K = \left\{ {s,\,f} \right\},\,F = \left\{ f \right\},\,\sum { = \left\{ {a,b} \right\},\,F = \left\{ a \right\}} $$ and $$\Delta = \left\{ {\left( {\left( {s,\,a,\, \in } \right)} \right.,\,\left. {\left( {s,\,a} \right)} \right),\,\left( {\left( {s,\,b,\, \in } \right),\,\left. {\left( {s,\,a} \right)} \right),\,} \right.} \right.$$ $$\left( {\left( {s,\,a,\, \in } \right),\,\left( {f,\, \in } \right),\,\left( {\left( {f,\,a,\,a} \right),\,\left. {\left( {f,\, \in } \right)} \right),\,\left( {\left( {f,\,b,\,a} \right),\,\left. {\left. {\left( {f,\, \in } \right)} \right)} \right\}} \right.} \right.} \right..$$

Which one of the following strings is not a number of $$L(M)?$$

Consider the following grammar $$G:$$
$$\eqalign{ & S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr & A \to bA\,\left| {\,aB} \right. \cr & B \to bB\,\left| {\,aS\,\left| {\,a} \right.} \right. \cr} $$

Let $${N_a}\left( w \right)$$ and $${N_b}\left( w \right)$$ denote the number of $$a's$$ and $$b's$$ in a string $$w$$ respectively. The language
$$L\left( G \right)\,\,\, \subseteq \left\{ {a,b} \right\} + $$ generated by $$G$$ is

Which of the following grammar rules violate the requirements of an operator grammar ? $$P,$$ $$Q, R$$ are non-terminals and $$r, s, t$$ are terminals. $$$\eqalign{ & 1)\,\,\,P \to Q\,R\,\,\,\,\,2)\,\,\,P \to Q\,s\,R \cr & 3)\,\,\,P \to c\,\,\,\,\,\,\,\,\,\,\,4)P \to Q\,t\,R\,r \cr} $$$

The following finite state machine accepts all those binary strings in which the number of $$1's$$ and $$0's$$ are respectively