## GATE 2001

 Question 1

Consider the following statements:

S1: The sum of two singular n × n matrices may be non-singular
S2: The sum of two n × n non-singular matrices may be singular.

Which of the following statements is correct?

 A S1 and S2 are both true B S1 is true, S2 is false C S1 is false, S2 is true D S1 and S2 are both false
Engineering-Mathematics       Linear-Algebra
Question 1 Explanation: Question 2

Consider the following relations:

R1(a,b) iff (a+b) is even over the set of integers
R2(a,b) iff (a+b) is odd over the set of integers
R3(a,b) iff a.b > 0 over the set of non-zero rational numbers
R4(a,b) iff |a-b| <= 2 over the set of natural numbers

Which of the following statements is correct?

 A R1 and R2 are equivalence relations, R3 and R4 are not B R1 and R3 are equivalence relations, R2 and R4 are not C R1 and R4 are equivalence relations, R2 and R3 are not D R1, R2, R3 and R4 are all equivalence relations
Engineering-Mathematics       Sets-And-Relation
Question 2 Explanation:
R1:
a+a = 2a
The set (a,a) is reflexive.
The set representation (a,a), (b,b) is also Symmetric.
The set representation is Transitive.
So, this is Equivalence.
R2:
a+a ≠ 2a
The (a,a) is non-reflexive.
R3:
a⋅a>0 → Reflexive
a⋅b>0 and b⋅a>0 → Symmetric
a⋅b>0, b⋅c>0 then c⋅a>0 → Transitive
The relation R3 is equivalence relation.
R4:
|a - a| ≤ 2, which is not possible, not Reflexive.
R1 & R3 are equivalence, R2 & R4 are not.
 Question 3

Consider two well-formed formulas in prepositional logic

`   F1: P ⇒ ¬P          F2: (P⇒¬P)∨(¬P⇒P)  `

Which of the following statements is correct?

 A F1 is satisfiable, F2 is valid B F1 unsatisfiable, F2 is satisfiable C F1 is unsatisfiable, F2 is valid D F1 and F2 are both satisfiable
Engineering-Mathematics       Propositional-Logic
Question 3 Explanation: F1 is satisfiable; F2 is valid.
 Question 4

Consider the following two statements:

S1: {02n|n≥1|} is a regular language
S2: {0m1n0m+n|m≥1 and n≥1|} is a regular language

Which of the following statements is correct?

 A Only S1 is correct B Only S2 is correct C Both S1 and S2 are correct D None of S1 and S2 is correct
Theory-of-Computation       Regular Languge
Question 4 Explanation:
For S1 we can construct DFA. S1 represents the string contains even no. of 0's. So S1 is regular.
For S2, DFA is not possible which is not regular.
 Question 5

Which of the following statements is true?

 A If a language is context free it can always be accepted by a deterministic push-down automaton B The union of two context free languages is context free C The intersection of two context free languages is context free D The complement of a context free language is context free
Theory-of-Computation       Properties-of-Languages
Question 5 Explanation:
Context free languages closed under Union, concatenation and kleen star. But not close under intersection and complementation.
 Question 6

Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

 A N2 B 2N C 2N D N!
Theory-of-Computation       Finite-Automata
Question 6 Explanation:
If NFA contains N, then possible number of states in possible DFA is 2N.
If NFA have two states {1}{2} = 2
Then DFA may contain {ϕ}{1}{2}{1,2} = 4 = 22 = 2N
 Question 7

More than one word is put in one cache block to

 A exploit the temporal locality of reference in a program B exploit the spatial locality of reference in a program C reduce the miss penalty D none of the above
Computer-Organization       Cache
Question 7 Explanation:
Spatial locality refers to the use of data elements within relatively close storage locations. To exploit the spatial locality, more than one word are put into cache block.
The temporal locality refers to reuse of data elements with a smaller regular intervals.
 Question 8

Which of the following statements is false?

 A Virtual memory implements the translation of a program’s address space into physical memory address space B Virtual memory allows each program to exceed the size of the primary memory C Virtual memory increases the degree of multiprogramming D Virtual memory reduces the context switching overhead
Operating-Systems       Virtual Memory
Question 8 Explanation:
In a system with virtual memory context switch includes extra overhead in switching of address spaces.
 Question 9

A low memory can be connected to 8085 by using

 A INTER B C HOLD D READY
Computer-Organization       Microprocessor
Question 9 Explanation:
Communication is only possible when READY signal is set. So a low memory can be connected to 8085 by using READY signal.
 Question 10

Suppose a processor does not have any stack pointer register. Which of the following statements is true?

 A It cannot have subroutine call instruction B It can have subroutine call instruction, but no nested subroutine calls C Nested subroutine calls are possible, but interrupts are not D All sequences of subroutine calls and also interrupts are possible
Computer-Organization       Subroutines
Question 10 Explanation:
If stack pointer register is not available then activation records in the stack cannot be created. So it cannot have subroutine call instruction.
 Question 11

Given the following Karnaugh map, which one of the following represents the minimal Sum-Of-Products of the map? A xy+y'z B wx'y'+xy+xz C w'x+y'z+xy D xz+y
Digital-Logic-Design       K-Map
Question 11 Explanation: ⇒ y'z + xy
 Question 12

A processor needs software interrupt to

 A test the interrupt system of the processor B implement co-routines C obtain system services which need execution of privileged instructions D return from subroutine
Computer-Organization       Interrupt
Question 12 Explanation:
To execute privileged instructions, system services can be obtained using software interrupt.
 Question 13

A CPU has two modes-privileged and non-privileged. In order to change the mode from privileged to non-privileged

 A a hardware interrupt is needed B a software interrupt is needed C a privileged instruction (which does not generate an interrupt) is needed D a non-privileged instruction (which does not generate an interrupt is needed
Computer-Organization       Interrupt
Question 13 Explanation:
For switching between privileged to non-privileged area, non-privileged instruction is used, without interrupt.
 Question 14

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

 A O(n) B O(n log n) C O(n2) D O(n!)
Algorithms        Sorting
Question 14 Explanation:
In worst case Randomized quicksort execution time complexity is same as quicksort.
 Question 15

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i≤n), the index of the parent is

 A i-1 B ⌊i/2⌋ C ⌈i/2⌉ D (i+1)/2
Data-Structures       Heap-Tree
Question 15 Explanation:
Parent Node is at index: ⌊i/2⌋
Left Child is at index: 2i
Right child is at index: 2*i+1
 Question 16

Let f(n) = n2logn and g(n) = n(logn)10 be two positive functions of n. Which of the following statements is correct?

 A f(n) = O(g(n) and g(n) ≠ O(f(n)) B g(n) = O(f(n) and f(n) ≠ O(g(n)) C f(n) ≠ O(g(n)) and g(n) ≠ O(f(n)) D f(n) = O(g(n)) and g(n) = O(f(n))
Algorithms        Time-Complexity
Question 16 Explanation:
f(n) = n2logn; g(n) = n(logn)10
Cancel nlogn from f(n), g(n)
f(n) = n; g(n) = (logn)9
n is too large than (logn)9
So f(n)! = O(g(n)) and g(n) = O(f(n))
 Question 17

The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

 A Assembly B Parsing C Relocation D Symbol resolution
Compiler-Design       Run-Time-Environments
Question 17 Explanation:
Relocation can change the assigned address of data and code in the program.
 Question 18

Which of the following statements is false?

 A An unambiguous grammar has same leftmost and rightmost derivation B An LL(1) parser is a top-down parser C LALR is more powerful than SLR D An ambiguous grammar can never be LR(k) for any k
Compiler-Design       Parsers
Question 18 Explanation:
Option B: LL parser is a top-down parser for a subset of context-free languages. It parses the input from Left to right, performing Left most derivation of the sentence.
Option C: LALR is more powerful than SLR.
Option D: An ambiguous grammar can never be LR (k) for any k, because LR(k) algorithm aren’t designed to handle ambiguous grammars. It would get stuck into undecidability problem, if employed upon an ambiguous grammar, no matter how large the constant k is.
 Question 19

Consider a set of n tasks with known runtimes r1, r2, ..., rn to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput?

 A Round-Robin B Shortest-Job-First C Highest-Response-Ratio-Next D First-Come-First-Served
Operating-Systems       Process-Scheduling
Question 19 Explanation:
First we know what is throughput. It means total number of tasks executed per unit time. SJF executes shortest job very early so throughput increases in the case of SJF.
 Question 20

Where does the swap space reside?

 A RAM B Disk C ROM D On-chip cache
Computer-Organization       Disk-Scheduling
Question 20 Explanation:
Swap space is an area on disk that temporarily holds a process memory image.
When memory is full and process needs memory, inactive parts of process are put in swap space of disk.
 Question 21

Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will

 A always decrease the number of page faults B always increase the number of page faults C sometimes increase the number of page faults D never affect the number of page faults
Operating-Systems       Page-Replacement
Question 21 Explanation:
Belady’s Anomaly more number of frames = More page faults.
See Belady’s anomaly is the name given to the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.
This phenomenon is commonly experienced in following page replacement algorithms:
First in first out (FIFO), Second chance algorithm, Random page replacement algorithm.
 Question 22

Which of the following requires a device driver?

 A Register B Cache C Main memory D Disk
Computer-Organization       DMA
Question 22 Explanation:
Disk driver is software which enables communication between internal hard disk (or drive) and computer.
 Question 23

Consider a schema R(A,B,C,D) and functional dependencies A → B and C → D. Then the decomposition of R into R1(AB) and R2(CD) is

 A dependency preserving and lossless join B lossless join but not dependency preserving C dependency preserving but not lossless join D not dependency preserving and not lossless join
Database-Management-System       Functional-Dependency
Question 23 Explanation:
If the given relations are to be lossless then
R1∩R2 ≠ 0
Given R1(A,B), R2
R1∩R2 = 0
Not lossless.
The given relation decomposed into R1(A,B) and R2(C,D) and there are only two functional dependencies A→B and C→D. So the given decomposition is dependency preserving.
 Question 24

Suppose the adjacency relation of vertices in a graph is represented in a table Adj(X,Y). Which of the following queries cannot be expressed by a relational algebra expression of constant length?

 A List of all vertices adjacent to a given vertex B List all vertices which have self loops C List all vertices which belong to cycles of less than three vertices D List all vertices reachable from a given vertex
Database-Management-System       Relational-Algebra
Question 24 Explanation:
(a) Finding a adjacency vertex for the given vertex is too simple i.e., Adj(X,Y).
(b) Finding a self loop is also simple (Oop(X,X))
(c) If a → b, b → c then c!=a, finding this is also simple.
(d) List all the elements reachable from a given vertex is too difficult in Relational Algebra.
 Question 25

Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. Then the relational algebra expression σA=a(r⋈s) is always equal to

 A σA=a (r) B r C σA=a (r)⨝s D None of the above
Database-Management-System       Relational-Algebra
Question 25 Explanation:
(a) A=a for all r
(b) Display table
(c) A=a for all Tables r and s
 Question 26

How many 4-digit even numbers have all 4 digits distinct?

 A 2240 B 2296 C 2620 D 4536
Engineering-Mathematics       Combinatorics
Question 26 Explanation:
If the last digit is 0 then If last digit is (2, 4, 6, 8) Total possibilities = 504 + 1792 = 2296
 Question 27

Consider the following statements:

S1: There exists infinite sets A, B, C such that A∩(B∪C) is finite.
S2: There exists two irrational numbers x and y such that (x+y) is rational.

Which of the following is true about S1 and S2?

 A Only S1 is correct B Only S2 is correct C Both S1 and S2 are correct D None of S1 and S2 is correct
Engineering-Mathematics       Sets-And-Relation
Question 27 Explanation:
S1: Consider A = {2,4,6,8,10,...} set of all even numbers
B = {2,3,5,7,11,13,...} set of prime numbers
C = {1,3,5,7,...} set of odd numbers
(B∪C) = {1,2,3,5,7,...}
A∩(B∪C) = {2}
Which is finite, S1 is true.
S2: Consider A=5+√3 Irrational
B=5-√3 Irrational
A+B=10 Rational
A+B, which is rational number, S2 is true.
 Question 28

Let f: A→B be a function, and let E and F be subsets of A. Consider the following statements about images.

S1: f(E ∪ F) = f(E) ∪ f(F)
S1: f(E ∩ F) = f(E) ∩ f(F)

Which of the following is true about S1 and S2?

 A Only S1 is correct B Only S2 is correct C Both S1 and S2 are correct D None of S1 and S2 is correct
Engineering-Mathematics       Sets-And-Relation
Question 28 Explanation:
S1: f(E∪F) = f(E)∪f(F)
The both LHS and RHS contains the same element in E and F.
So, S1 is true.
S2: f(E∩F) = f(E)∩f(F)
E and F are partitions of A.
f(E)∩f(F) = ϕ
f(ϕ) is not defined, but f(E)∩f(F)=1.
So, S2 is false.
 Question 29

Seven (distinct) car accidents occurred in a week. What is the probability that they all occurred on the same day?

 A 1/77 B 1/76 C 1/27 D 7/27
Engineering-Mathematics       Probability
Question 29 Explanation:
Probability of all accidents on sunday = 1/77
Such as total no. of days in a week = 7
Total probability = 7 × 1/77 = 1/76
 Question 30

Consider a DFA over Σ = {a,b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?

 A 8 B 14 C 15 D 48
Theory-of-Computation       Finite-Automata
Question 30 Explanation:
A DFA which is no. of a's divisible by 6 consists of 6 states i.e., mod6 results 0,1,2,3,4,5.
Same as b's divisible by 8 contains 8 state.
Total no. of states is = 8 * 6 = 48
 Question 31

Consider the following languages:

L1 = {ww|w ∈ {a,b}*}
L2 = {wwR|w ∈ {a,b}*, wR is the reverse of w}
L3 = {02i|i is an integer}
L3 = {0i2|i is an integer}

Which of the languages are regular?

 A Only L1 and L2 B Only L2, L3 and L4 C Only L3 and L4 D Only L3
Theory-of-Computation       Regular-Language
Question 31 Explanation:
L1 = {ww|w∈{a,b}*}
⇒ This is not regular language. We can't be able to identify where the 'w' will ends and where the next 'w' starts.
L2 = {wwR|w∈{a,b}*, wR is the reverse of w}
⇒ This also not a regular language. We can't identify where 'w' ends.
L4 = {0i2|i is an integer}
= {0i*0i|i is an integer}
⇒ This is also not a regular language. We can't identify where 0i ends.
L3 = {02i|i is an integer}
⇒ This is regular. We can easily find whether a string is even or not.
 Question 32

Consider the following problem X.

Given a Turing machine M over the input alphabet Σ, any state q of M And a word w∈Σ*, does the computation of M on w visit the state q?

Which of the following statements about X is correct?

 A X is decidable B X is undecidable but partially decidable C X is undecidable and not even partially decidable D X is not a decision problem
Theory-of-Computation       Turing Mchine
Question 32 Explanation:
The given X is a Halting problem. So which is to be undecidable but partially decidable.
 Question 33

Consider the following circuit with initial state Q0 = Q1 = 0. The D Flip-flops are positive edged triggered and have set up times 20 nanosecond and hold times 0. Consider the following timing diagrams of X and C; the clock period of C <= 40 nanosecond. Which one is the correct plot of Y? A B C D Digital-Logic-Design       Sequential-Circuits
Question 33 Explanation: Given clock is +edge triggered.
See the first positive edge. X is 0, and hence the output is 0, because
Y = Q1N = D1×Q0' = 0⋅Q0' = 0
At second +edge, X is 1 and Q0' is also 1. So output is 1 (when second +ve edge of the clock arrives, Q0' would surely be 1 because the setup time of flip flop is given as 20ns and clock period is ≥ 40ns).
At third +ve edge, X is 1 and Q0' is 0, so output is 0.
Now output never changes back to 1 as Q0' is always 0 and when Q0' finally becomes 1, X is 0.
Hence option (A) is the correct answer.
 Question 34

Which is the most appropriate match for the items in the first column with the items in the second column

```X. Indirect Addressing        I. Array implementation
Y. Indexed Addressing         II. Writing re-locatable code
Z. Base Register Addressing   III. Passing array as parameter ```
 A (X, III) (Y, I) (Z, II) B (X, II) (Y, III) (Z, I) C (X, III) (Y, II) (Z, I) D (X, I) (Y, III) (Z, II)
Computer-Organization       Match-the-Following
Question 34 Explanation:
⇒ Array implementation can be done by Indexed addressing.
⇒ Writing relocatable code can be done by Base Register addressing by changing the value of Base Register.
⇒ While passing an array as parameter we use pointer and hence can use Indirect addressing.
 Question 35

The 2’s complement representation of (-539)10 in hexadecimal is

 A ABE B DBC C DE5 D 9E7
Digital-Logic-Design       Number-Systems
Question 35 Explanation:
(539)10 = (0010 0001 1011)2
For (-539)10 = (1101 1110 0100)2
1's complement = (1101 1110 0100)2
2's complement = (1101 1110 0101)2
= (DE5)16
 Question 36

Consider the circuit shown below. The output of a 2:1 Mux is given by the function (ac' + bc). Which of the following is true?

 A f = x1' + x2 B f = x1'x2 + x1x2' C f = x1x2 + x1'x2' D f = x1 + x2'
Digital-Logic-Design       Number-Systems
Question 36 Explanation:
g = (a and x1′) or (b and x1)
g = (1 and x1’) or (0 and x1)
g = x1’
f = ac’ + bc
f = (a and x2′) or (b and x2)
f = (g and x2′) or (x1 and x2)
f = x1’x2’ + x1x2
 Question 37

Consider the circuit given below with initial state Q0 = 1, Q1 = Q2 = 0. The state of the circuit is given by the value 4Q2 + 2Q1 + Q0 Which one of the following is the correct state sequence of the circuit?

 A 1,3,4,6,7,5,2 B 1,2,5,3,7,6,4 C 1,2,7,3,5,6,4 D 1,6,5,7,2,3,4
Digital-Logic-Design       Sequential-Circuits
Question 37 Explanation: Question 38

Consider the following data path of a simple non-pilelined CPU. The registers A, B, A1, A2, MDR, the bus and the ALU are 8-bit wide. SP and MAR are 16-bit registers. The MUX is of size 8 × (2:1) and the DEMUX is of size 8 × (1:2). Each memory operation takes 2 CPU clock cycles and uses MAR (Memory Address Register) and MDR (Memory Date Register). SP can be decremented locally. The CPU instruction “push r”, where = A or B, has the specification

```     M [SP] ← r
SP ← SP - 1```

How many CPU clock cycles are needed to execute the “push r” instruction?

 A 2 B 3 C 4 D 5
Computer-Organization       Machine-Instructions
Question 38 Explanation:
T1: SP → MAR, 2 cycles (as SP is 16 bits and data bus is 8 bits so needs 2 cycles to move data)
T2: 8 → MBR, 1 cycle
T3: M[MAR] ← MBR, 2 cycles (As it is a memory operation)
So, total 5 clock cycles.
 Question 39

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

 A d(r,u) B d(r,u)>d(r,v) C d(r,u)≤d(r,v) D None of the above
Data-Structures       Graphs
Question 39 Explanation:
d(r,u) and d(r, v) will be equal when u and v are at same level, otherwise d(r,u) will be less than d(r,v).
 Question 40

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ...,vn} of n vertices?

 A n(n-1)/2 B 2n C n! D 2n(n-1)/2
Engineering-Mathematics       Graph-Theory
Question 40 Explanation:
With n vertices no. of possible edges = n C 2
Each subset of these edges will be form a graph.
No. of possible undirected graphs is 2(n C 2)
⇒ 2(n(n-1)/2)
 Question 41

What is the minimum number of stacks of size n required to implement a queue of size n?

 A One B Two C Three D Four
Data-Structures       Stack-and-Queue
Question 41 Explanation:
Minimum number of stacks of size n required to implement a queue of size n is two. With the help of two stacks we can able to implement a queue.
 Question 42

What is printed by the print statements in the program P1 assuming call by reference parameter passing?

```Program P1()
{
x = 10;
y = 3;
func1(y,x,x);
print x;
print y;
}
func1(x,y,z)
{
y = y+4;
z = x+y+z;
} ```
 A 10, 3 B 31, 3 C 27, 7 D None of the above
Programming       Parameter-Passing
Question 42 Explanation:
Here, variable x of func1 points to address of variable y.
And variable y and z of func1 points to address of variable x.
Therefore, y = y+4 ⇒ y = 10+4 = 14
and z = x+y+z ⇒ z = 14+14+3 = 31
z will be stored back in k.
Hence, x=31 and y will remain as it is (y=3).
Hence, answer is (B).
 Question 43

Consider the following three C functions:

```[PI]            int*g(void)
{
int x = 10;
return(&x);
}

[P2]            int*g(void)
{
int*px;
*px = 10;
return px;
}

[P3]            int*g(void)
{
int*px;
px = (int *) malloc(sizeof(int));
*px = 10;
return px;
} ```

Which of the above three functions are likely to cause problems with pointers?

 A Only P3 B Only P1 and P3 C Only P1 and P2 D P1, P2 and P3
Data-Structures       Pointers
Question 43 Explanation:
[P1] → May cause error because the function is returning the address of locally declared variable.
[P2] → It will cause problem because px is in int pointer that is not assigned with any address and we are doing dereferencing.
[P3] → It will work because memory will be stored in px that can be use further. Once function execution completes this will exist in Heap.
 Question 44

Consider the following program

```                Program P2
var n: int:
procedure W(var x: int)
begin
x=x+1;
print x;
end

procedure D
begin
var n: int;
n=3;
W(n);
End
begin               //beginP2
n=10;
D;
end  ```

If the language has dynamic scoping and parameters are passed by reference, what will be printed by the program?

 A 10 B 11 C 3 D None of the above
Programming       Programming
Question 44 Explanation:
n=3
W(n)=W(3)
Procedure W(var x; int)
begin
x = x+1 = 3+1 = 4
Print x → Print x=4
end
 Question 45

Which of the following does not interrupt a running process?

 A A device B Timer C Scheduler process D Power failure
Operating-Systems       Process
Question 45 Explanation:
Scheduler process doesn’t interrupt any process, it’s Job is to select the processes for following three purposes.
 Question 46

Consider a machine with 64 MB physical memory and a 32-bit virtual address space. If the page size is 4 KB, what is the approximate size of the page table?

 A 16 MB B 8 MB C 2 MB D 24 MB
Operating-Systems       Process
Question 46 Explanation:
No. of entries in page table = 232/ 212 = 220
Frame size = 226 / 212 = 214
PT have to be stored in one frame so entry size must be 2 bytes, hence size of PT = 220 * 2 = 2 MB
 Question 47

Consider Peterson’s algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below.

```   repeat
flag[i] = true;
turn = j;
while (P) do no-op;
Enter critical section, perform actions, then exit critical
section
flag[i] = false;
Perform other non-critical section actions.
until false; ```

For the program to guarantee mutual exclusion, the predicate P in the while loop should be.

 A flag[j]=true and turn=i B flag[j]=true and turn=j C flag[i]=true and turn=j D flag[i]=true and turn=i
Operating-Systems       Process-Synchronization
Question 47 Explanation:
To ensure the mutual exclusion, we have to take care that ‘turn’ value which is ‘j’ so we should not allow that process in CS which is having flag[j] = true.
 Question 48

R(A,B,C,D) is a relation. Which of the following does not have a lossless join, dependency preserving BCNF decomposition?

 A A → B, B → CD B A → B, B → C, C → D C AB → C, C → AD D A → BCD
Database-Management-System       Normalization
Question 48 Explanation:
We have, R (A, B, C, D) and the Functional Dependency set = {AB→C, C→AD}. We decompose it as R1(A, B, C) and R2(C, D). This preserves all dependencies and the join is lossless too, but the relation R1 is not in BCNF. In R1 we keep ABC together otherwise preserving {AB→C} will fail, but doing so also causes {C→A} to appear in R1. {C→A} violates the condition for R1 to be in BCNF as C is not a super key. Condition that all relations formed after decomposition should be in BCNF is not satisfied here.
 Question 49

Which of the following relational calculus expressions is not safe?

 A {t|∃u ∈ R1 (t[A] = u[A])∧ ¬∃s ∈ R2 (t[A] = s[A])} B {t|∀u ∈ R1 (u[A]= "x" ⇒ ∃s ∈ R2 (t[A] = s[A] ∧ s[A] = u[A]))} C {t|¬(t ∈ R1)} D {t|∃u ∈ R1 (t[A] = u[A])∧ ∃s ∈ R2 (t[A] = s[A])}
Database-Management-System       Relational-Calculus
 Question 50

Consider a relation geq which represents “greater than or equal to”, that is, (x,y) ∈ geq only if y >= x.

```create table geq
(  Ib integer not null
ub integer not null
primary key 1b
foreign key (ub) references geq on delete cascade ) ```

Which of the following is possible if a tuple (x,y) is deleted?

 A A tuple (z,w) with z > y is deleted B A tuple (z,w) with z > x is deleted C A tuple (z,w) with w < x is deleted D The deletion of (x,y) is prohibited
Database-Management-System       SQL
 Question 51

(a) Prove that powerset (A∩B) = powerset(A)∩powerset(B)

(b) Let sum(n)=0+1+2+…+n for all natural numbers n. Give an induction proof to show that the following equation is true for all natural numbers m and n:

` sum(m+n)=sum(m)+sum(n)+mn `
 A Theory Explanation is given below.
Engineering-Mathematics       Descriptive
 Question 52

Consider the function h: N×N → N so that h(a,b) = (2a+1)2b-1, where N ={0,1,2,3,…..} is the set of natural numbers.

(a) Prove that the function h is an injection (one-one).
(b) Prove that it is also a Subjection (onto).
 A Theory Explanation is given below.
Engineering-Mathematics       Sets and Functions
 Question 53

Construct DFA’s for the following languages:

``` (a) L = {w|w ∈ {a,b}*, w has baab as a subsring }
(b) L = {w|w ∈ {a,b}*, w has an odd number of a's and an odd number of b's} ```
 A Theory Explanation is given below.
Theory-of-Computation       Finite-Automata
 Question 54

Give a deterministic PDA for the language L = {ancb2n|n ≥ 1} over the alphabet Σ = {a,b,c}. Specify the acceptance state.

 A Theory Explanation is given below.
Theory-of-Computation       Push-Down-Automata
 Question 55

Let a decision problem X be defined as follows:

```    X: Given a Turing machine M over Σ and nay word w ∈ Σ,
does M loop forever on w? ```

You may assume that the halting problem of Turing machine is undecidable but partially decidable.

(a) Show that X is undecidable.
(b) Show that X is not even partially decidable.
 A Theory Explanation is given below.
Theory-of-Computation       Turing Machine
 Question 56

Consider a disk with following specifications: 20 surface, 1000 tracks/surface, 16 sectors/track, data density 1 KB/sector, rotation speed 3000 rpm. The operating system initiates the transfer between the disk and the memory sector-wise. Once the head has been placed on the right track, the disk reads a sector in a single scan. It reads bits from the sector while the head is passing over the sector. The read bits are formed into bytes in a serial-in-parallel-out buffer and each byte is then transferred to memory. The disk writing is exactly a complementary process.

For parts (c) and (d) below, assume memory read-write time = 0.1 microsecond/byte, interrupt driven transfer has an interrupt overhead = 0.4 microseconds, the DMA initialization and termination overhead is negligible compared to the total sector transfer time. DMA requests are always granted.

(a) What is the total capacity of the disk?
(b) What is the data transfer rate?
(c) What is the percentage of time the CPU is required for this disk I/O for bytewise interrupts driven transfer?
(d) What is the maximum percentage of time the CPU is held up for this disk I/O for cycle-stealing DMA transfer?
 A Theory Explanation if given below.
Computer-Organization       Secondary-Storage
 Question 57

A CPU has 32-bit memory address and a 256 KB cache memory. The cache is organized as a 4-way set associative cache with cache block size of 16 bytes.

(a) What is the number of sets in the cache?
(b) What is the size (in bits) of the tag field per cache block?
(c) What is the number and size of comparators required for tag matching?
(d) How many address bits are required to find the byte offset within a cache block?
(e) What is the total amount of extra memory (in bytes) required for the tag bits?
 A Theory Explanation is given below.
Computer-Organization       Cache
 Question 58

(a) Is the 3-variable function f = ∑(0,1,2,4) its self-dual? Justify your answer.
(b) Give a minimal product-of-sum form of the b output of the following excess-3 to BCD converter. A Theory Explanation is given below.
Digital-Logic-Design       Descriptive
Question 58 Explanation:
(a) The function is self dual because
→ There is no mutually exclusive pair.
→ No. of minterms = No. of maxterms
(b) Write Minimal POS. Question 59

A sequential circuit takes an input stream of 0’s and 1’s and produces an output stream of 0’s and 1’s. Initially it replicates the input on its output until two consecutive 0’s are encountered on the input. From then onward, it produces an output stream, which is the bit-wise complement of input stream until it encounters two consecutive 1’s, whereupon the process repeats. An example of input and output stream is shown below.

```The input stream: 101100 01001011 0 11
The desired output: 101100 10110100 0 11 ```

J-K master-slave flip-flops are to be used to design the circuit.
(a) Give the state transition diagram.
(b) Give the minimized sum-of-product expression for J and K inputs of one of its state flip-flops.

 A Theory Explanation is given below.
Digital-Logic-Design       Sequential-Circuits
Question 59 Explanation:  Question 60

Consider a 5-stage pipeline – IF (Instruction Fetch), ID (Instruction Decode and register read), EX (Execute), MEM (memory), and WB (Write Back). All (memory or register) reads take place in the second phase of a clock cycle and writes occur in the first phase of the clock cycle. Consider the execution of the following instruction sequence:

```      11:      sub r2, r3, r4;         /*   r2 ← r3 – r4    */
12:      sub r4, r2, r3;         /*   r4 ← r2 – r3    */
13:      sw r2, 100(r1)          /*   M[r1+100] ← r2  */
14:      sub r3, r4, r2;         /*   r3 ← r4 – r2    */  ```

(a) Show all data dependencies between the four instructions.
(b) Identify the data hazards.
(c) Can all hazards be avoided by forwarding in this case?

 A Theory Explanation is given below.
Computer-Organization       Pipelining
 Question 61

Consider the following C program:

```           void abc(char*s)
{
if(s==’\0’)return;
abc(s+1);
abc(s+1);
printf(“%c”,s);
}
main()
{  abc(“123”)
}  ```

(a) What will be the output of the program?
(b) If abc(s) is called with a null-terminated string s of length n characters (not counting the null (‘\0’) character), how many characters will be printed by abc(s)?

 A Theory Explanation is given below.
Programming       C-Programming
 Question 62

(a) Insert the following keys one by one into a binary search tree in the order specified.

`         15, 32, 20, 9, 3, 25, 12, 1  `

Show the final binary search tree after the insertions.
(b) Draw the binary search tree after deleting 15 from it.
(c) Complete the statements S1, S2 and S3 in the following function so that the function computes the depth of a binary rooted at t.

```              typedef struct tnode{
int key;
struct tnode *left, *right;
} *Tree;
int depth(Tree t)
{
int x,y;
it (t == NULL) return0;
x=depth(t → left);
S1:              ____________;
S2:              if(x>y) return _____________:
S3:              else return _____________;
} ```
 A Theory Explanation is given below.
Data-Structures       Binary-Search-Tree
 Question 63

Consider a weighted undirected graph with vertex set V = {n1,n2,n3,n4,n5,n6} and edge set

``` E = {(n1,n2,2),(n1,n3,8),(n1,n6,3),(n2,n4,4),(n2,n5,12),(n3,n4,7),(n4,n5,9),
(n4,n6,4)}. The third value in each tuple represents the weight of the edge
specified in the tuple. ```

(a) List the edges of a minimum spanning tree of the graph.
(b) How many distinct minimum spanning trees does this graph have?
(c) Is the minimum among the edge weights of a minimum spanning tree unique overall possible minimum spanning trees of a graph?
(d) Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?

 A Theory Explanation is given below.
Algorithms        Minimum-Spanning-Tree
Question 63 Explanation:
(b) 2 distinct MST's.
(c) Yes, it always. Because 'the edge weight 2 is unique'.
(d) Yes, it always. Because 'the edge weight 9 is unique'.
 Question 64

Consider the following grammar with terminal alphabet ∑{a,(,),+,*} and start symbol E. The production rules of the grammar are:

```              E → aA
E → (E)
A → +E
A → *E
A → ε ```

(a) Compute the FIRST and FOLLOW sets for E and A.
(b) Complete the LL(1) parse table for the grammar.

 A Theory Explanation is given below.
Compiler-Design       Parsers
 Question 65

The syntax of the repeat-until statement is given by the gollowing grammar

`   S → repeat S1 until E  `

Where E stands for expressions, S and S1 stand for statement. The non-terminals S and S1 have an attribute code that represents generated code. The nonterminal E has two attributes. The attribute code represents generated code to evaluate the expression and store its truth value in a distinct variable, and the attribute varName contains the name of the variable in which the truth value is stored? The truth-value stored in the variable is 1 if E is true, 0 if E is false.

Give a syntax-directed definition to generate three-address code for the repeatuntil statement. Assume that you can call a function newlabel( ) that returns a distinct label for a statement. Use the operator ‘\\’ to concatenate two strings and the function gen(s) to generate a line containing the string s.

 A Theory Explanation is given below.
Compiler-Design       Syntax-Directed-Translation
 Question 66

(a) Remove left-recursion from the following grammar:

`    S → Sa| Sb | a | b `

(b) Consider the following grammar:

`    S → aSbS| bSaS |ε  `

Construct all possible parse trees for the string abab. Is the grammar ambiguous?

 A Theory Explanation is given below.
Compiler-Design       Grammar
 Question 67

Two concurrent processes P1 and P2 want to use two resources R1 and R2 in a mutually exclusive manner. Initially, R1 and R2 are free. The programs executed by the two processes are given below.

```Program for P1:
S1: While (R1 is busy) do no-op;
S2: Set R1 ← busy;
S3: While (R2 is busy) do no-op;
S4: Set R2 ← busy;
S5: Use R1 and R2;
S6: Set R1 ← free;
S7: Set R2 ← free;
Program for P2:
Q1: While (R1 is busy) do no-op;
Q2: Set R1 ← busy;
Q3: While (R1 is busy) do no-op;
Q4: Set R1 ← busy;
Q5: Use R1 and R2;
Q6: Set R2 ← free;
Q7: Set R1 ← free; ```

(a) Is mutual exclusion guaranteed for R1 and R2? If not, show a possible interleaving of the statements of P1 and P2 such that mutual exclusion is violated (i.e., both P1 and P2 use R1 or R2 at the same time).
(b) Can deadlock occur in the above program? If yes, show a possible interleaving of the statements of P1 and P2 leading to deadlock.
(c) Exchange the statements Q1 and Q3 and statements Q2 and Q4. Is mutual exclusion guaranteed now? Can deadlock occur?

 A Theory Explanation is given below.
Operating-Systems       Descriptive
 Question 68

Consider a disk with the 100 tracks numbered from 0 to 99 rotating at 3000 rpm. The number of sectors per track is 100. the time to move the head between two successive tracks is 0.2 millisecond.

(a) Consider a set of disk requests to read data from tracks 32, 7, 45, 5 and 10. Assuming that the elevator algorithm is used to schedule disk requests, and the head is initially at track 25 moving up (towards larger track numbers), what is the total seek time for servicing the requests?
(b) Consider an initial set of 100 arbitrary disk requests and assume that no new disk requests arrive while servicing these requests. If the head is initially at track 0 and the elevator algorithm is used to schedule disk requests, what is the worst case time to complete all the requests?

 A Theory Explanation is given below.
Computer-Organization       Secondary-Storage
 Question 69

Consider the relation examinee (regno, name, score), where regno is the primary key to score is a real number.
(a) Write a relational algebra using (∏,σ,ρ,×) to find the list of names which appear more than once in examinee.
(b) Write an SQL query to list the regno of examinees who have a score greater than the average score.
(c) Suppose the relation appears (regno, centr_code) specifies the center where an examinee appears. Write an SQL query to list the centr_code having an examinee of score greater than 80.

 A Theory Explanation is given below.
Database-Management-System       Descriptive
 Question 70

We wish to construct a B+ tree with fan-out (the number of pointers per node) equal to 3 for the following set of key values:

`             80, 50, 10, 70, 30, 100, 90   `

Assume that the tree is initially empty and the values are added in the order given.
(a) Show the tree after insertion of 10, after insertion of 30, and after insertion of 90. Intermediate trees need not be shown.
(b) The key values 30 and 10 are now deleted from the tree in that order. Show the tree after each deletion.

 A Theory Explanation is given below.
Database-Management-System       B+-Trees
There are 70 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com
error: Content is protected !!