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 o

Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge-weighted directed graph with verte

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 H

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

The time complexity of the following C function is (assume n > 0) int recursive(int n){ if(n == 1){ return (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)

What does the following algorithm approximate? (Assume m > 1, $$ \in > 0$$) x = m; y = 1; while(x - y > ε){ x

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

Consider the grammar rule $$E \to {E_1} - {E_2}$$ for arithmetic expressions. The code generated is targeted to a CPU ha

Consider the grammar with the following translation rules and E as the start symbol. $$\eqalign{ & E \to {E_1}\# T

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

Choose the best matching between Group 1 and Group 2 : Group –1 P. Data link layer Q. Network layer R. Transport lay

Suppose that the maximum transmit window size for a TCP connection is 12000 bytes. Each packet consists of 2000 bytes. A

A TCP message consisting of 2100 bytes is passed to IP for delivery across two networks. The first network can carry a m

Consider three IP networks A, B and C. Host HA in networks A sends messages each containing 180 bytes of application dat

Consider three IP networks A, B and C. Host HA in networks A sends messages each containing 180 bytes of application dat

The routing table of a router is shown below: On which interface will the router forward packets addressed to destinati

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 tra

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

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

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

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

A $$4$$-stage pipeline has the stage delays as $$150, 120,160$$ and $$140$$ nano seconds respectively. Registers that ar

Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced,

The microinstructions stored in the control memory of a processor have a width of $$26$$ bits. Each microinstruction is

A Hard disk with a transfer rate of $$10Mbytes/second$$ is constantly transferring data to memory using $$DMA.$$ The pro

How many $$8$$-bit characters can be transmitted per second over $$9600$$ baud serial communication link using a parity

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,$$ $$

What is the result of evaluating the following two expressions using three $$-$$ digit floating point arithmetic with ro

Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the

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

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pair

Consider the following C program segment struct CellNode{ struct CellNode *leftChild; int element; struc

The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is

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 co

A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for e

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node sh

A program attempts to generate as many permutation as possible of the string “abcd” by pushing the character a,b,c,d in

Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highes

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

Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or

A single array A[1..MAXSIZE] is used to implement two stacks, The two stacks grow from opposite ends of the array. Varia

Consider the relation Student (name, sex, marks), where the primary key is shown underlined, pertaining to students in a

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,

The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child poi

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 R1 (A, B, C) and R2 (D, E) be two relation schema, where the primary keys are shown underlined, and let C be a forei

Consider two tables in a relational database with columns and rows as follows:  Table: Student .tg {border-collap

A relational database contains two table student and department in which student table has columns roll_no, name and dep

The employee information in a company is stored in the relation Employee (name, sex, salary, deptName) Consider the foll

Consider the following relation schema pertaining to a students database: Students (rollno, name, address) Enroll(rollno

A relation Empdt $$1$$ is defined with attributes empcode (unique), name, street, city, state and pincode. For any pinco

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

Consider the following entity relationship diagram $$(ERD),$$ where two entities $$E1$$ and $$E2$$ have a relation $$R$$

Consider the partial implementation of a $$2$$-bit counter using $$T$$ flip-flops following the sequence $$0$$-$$2$$-$$3

$$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,$$ an

A circuit outputs a digit in the form of $$4$$ bits. $$0$$ is represented by $$0000$$, $$1$$ by $$0001..., $$ $$9$$ by $

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

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$$ co

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

In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures

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

Let $${G_1} = \left( {V,\,{E_1}} \right)$$ and $${G_2} = \left( {V,\,{E_2}} \right)$$ be connected graphs on the same ve

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

Let $$A$$ be and n$$ \times $$n matrix of the folowing form. What is the value of the determinant of $$A$$?

If matrix $$X = \left[ {\matrix{ a & 1 \cr { - {a^2} + a - 1} & {1 - a} \cr } } \right]$$ and $${X^

In an M$$ \times $$N matrix such that all non-zero entries are covered in $$a$$ rows and $$b$$ columns. Then the maximum

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

How many solutions does the following system of linear equations have? - x + 5y = - 1x - y = 2x + 3y = 3

The recurrence equation $$\,\,\,\,\,\,\,T\left( 1 \right) = 1$$ $$\,\,\,\,\,\,T\left( n \right) = 2T\left( {n - 1} \rig

In how many ways can we distribute 5 distinct balls, $${B_1},{B_2},......,{B_5}$$ in 5 distinct cells, $${C_1},{C_2},...

Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints wi

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 \c

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}$$

The number of different $$n$$ $$x$$ $$n$$ symmetric matrices with each elements being either $$0$$ or $$1$$ is (No

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

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

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

An examination paper has 150 multiple-choice questions of one mark each, with each question having four choices. Each in

A point is randomly selected with uniform probability in the X-Y plane within the rectangle with corners at (0, 0), (1

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 re

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

Let $$p, q, r$$ and $$s$$ be four primitive statements. Consider the following arguments: $$P:\left[ {\left( {\neg p \ve

Let $$a(x,y)$$, $$b(x,y)$$ and $$c(x,y)$$ be three statements with variables $$x$$ and $$y$$ chosen from some universe.

Identify the correct translation into logical notation of the following assertion. $$Some\,boys\,in\,the\,class\,are\,t

Consider a System with a two-level paging scheme in which a regular memory access takes $$150$$ nanoseconds, and servici

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

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

Consider a program $$P$$ that consists of two source modules $${M_1}$$ and $${M_2}$$ contained in two different files. I

Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head

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

Consider the following statements with respect to user-level threads and kernel-supported threads. i) Context switch is

Consider the following C program segment: char p[20]; char *s = "string"; int length = strlen(s); for(i=0; i < length

Consider the following C function: void swap (int a, int b) { int temp; temp = a; a = b; b = temp; } In orde

Consider the following C program main ( ) { int x, y, m, n; scanf("%d %d", &x, &y); /* Assume x > 0 an

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); } T

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

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} \r

Consider the following grammar $$G:$$ $$\eqalign{ & S \to bS\,\left| {\,aA\,\left| {\,b} \right.} \right. \cr

Which of the following grammar rules violate the requirements of an operator grammar ? $$P,$$ $$Q, R$$ are non-terminals

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