Let G be a simple graph with 20 vertices and 100 edges. If the size of the minimum vertex cover of G is 8, the size of the maximum independent set of G is

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

Consider a relation scheme R = (A, B, C, D, E, H), on which the following functional dependencies hold: (A ® B, BC ® D, E ® C, D ® A). What are the candidate keys of R?

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1 Which of the following is false?

Consider the grammar with the following translation rules and E as the start symbol. E ® E1 # T {E.value = E1.value * T.value} | T {E.value = T.value } T ® T1 & F {T.value = T1.value + F.value} | F {T.value = F.value} F ® num {F.value = num.value } Compute E. value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.

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

The problems 3-SAT and 2-SAT are

Consider a relation scheme R = (A, B, C, D, E, H), on which the following functional dependencies hold: (A ® B, BC ® D, E ® C, D ® A). What are the candidate keys of R?

In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed through multiple bridges. Why is the spanning tree algorithm used for bridge-routing?

Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which of the following is true?

Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = d1d2... dm. int n, rev; rev = 0; while (n > 0) { rev = rev * 10 + n % 10; n = n/10; } The loop invariant condition at the end of the ith iteration is

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) User-level threads are transparent to the kernel Which of the above statements are true?

Which of the following are essential features of an object-oriented programming language? (i) Abstraction and encapsulation (ii) Strictly-typedness (iii) Type-safe property coupled with sub-type rule (iv) Polymorphism in the presence of inheritance

Consider the following program segment for a hypothetical CPU having three user registers Rl R2 and R3. Instruction Operation Instruction Size in word. MOV Rl,5000 ; Rl ¬ Memory[5000] 2 MOV R2,(R1) ; R2 ¬ Memory[(Rl)] ADD R2,R3 ; R2 ¬ R2 + R3 1 MOV 6000, R2 ; Memory[6000] ¬ R2 2 HALT; Machine halts 1 Let the clock cycles required for various operations be as follows. 1 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 cycles required to execute the program is

How many distinct binary search trees can be created out of 4 distinct keys?

Packets of the same session may be routed through different paths in

Consider the following relation schema pertaining to a students database: Student (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 the minimum number of tuples that can be presented in (Student * Enroll), where ' *' denotes natural join?

Assume the following C variable declaration:

int *A [10], B [10][10];

Which of the following expressions will not give compile-time errors if used as left hand side(s) of assignment statement(s) in a C program?

I. A [2]
II. A [2] [3] III. B [1]
IV. B [2][3]

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

Consider the grammar E ® E + n | E x n | n For a sentence n + n x n, the handles in the right-sentential form of the reduction are

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)?

Postorder traversal of a binary search tree T produces the following sequence of keys:

10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

Which of the following sequences of keys can be the result of an inorder traversal of the tree T?

Let f: B ® C and g: A ® B be two functions and let h = f o g. Given that h is an onto function. Which of the following is true?

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 do something when a pointer to the root of a non-empty tree is passed as argument is

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

In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet contains a header of 3 bytes, then the optimum packet size is

If 73x (in base-x number system) is equal to 54y (in base-y number system), the possible values of x and y are

What does the following algorithm approximate? (Assume m > 1, Î > 0) x = m; y - i; while (x - y > Î) { x = (x + y) / 2;
y = m/x ; } print (x);

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 the Shortest Seek Time First (SSTF), claimed by the vendor to give 50% better benchmark results, what is the expected improvement in the I/O performance of user programs?