search
Log In
Questions from GATE 2002

Recent questions tagged gate2002

5 votes
3 answers
1
The functionality of atomic TEST-AND-SET assembly language instruction is given by the following C function int TEST-AND-SET (int *x) { int y; A1: y=*x; A2: *x=1; A3: return y; } Complete the following C functions for implementing code for entering and ... and starvation-free? For the above solution, show by an example that mutual exclusion is not ensured if TEST-AND-SET instruction is not atomic?
asked Feb 28, 2018 in Operating System jothee 948 views
4 votes
1 answer
2
In the indexed scheme of blocks to a file, the maximum possible size of the file depends on: The number of blocks used for index and the size of index Size of Blocks and size of Address Size of index Size of block
asked Jul 31, 2016 in Operating System jothee 599 views
14 votes
2 answers
3
Determine whether each of the following is a tautology, a contradiction, or neither ("$\lor$" is disjunction, "$\land$" is conjunction, "$\rightarrow$" is implication, "$\neg$" is negation, and "$\leftrightarrow$" is biconditional (if and only if). $A \leftrightarrow (A \lor A)$ $(A \lor B) \rightarrow B$ $A \land (\neg (A \lor B))$
asked Nov 7, 2014 in Mathematical Logic Arjun 1.3k views
22 votes
1 answer
4
Construct all the parse trees corresponding to $i + j * k$ for the grammar $E \rightarrow E+E$ $E \rightarrow E*E$ $E \rightarrow id$ In this grammar, what is the precedence of the two operators $*$ and $+$? If only one parse tree is desired for any string in the same language, what changes are to be made so that the resulting LALR(1) grammar is unambiguous?
asked Sep 16, 2014 in Compiler Design Kathleen 1.3k views
19 votes
1 answer
5
We require a four state automaton to recognize the regular expression $(a\mid b)^*abb$ Give an NFA for this purpose Give a DFA for this purpose
asked Sep 16, 2014 in Theory of Computation Kathleen 1.3k views
20 votes
3 answers
6
The following solution to the single producer single consumer problem uses semaphores for synchronization. #define BUFFSIZE 100 buffer buf[BUFFSIZE]; int first = last = 0; semaphore b_full = 0; semaphore b_empty = BUFFSIZE void producer() { while(1) { produce an ... $p2$, immediately after $c1$ and immediately before $c2$ so that the program works correctly for multiple producers and consumers.
asked Sep 16, 2014 in Operating System Kathleen 2.3k views
26 votes
3 answers
7
A computer uses $32-bit$ virtual address, and $32-bit$ physical address. The physical memory is byte addressable, and the page size is $4$ $\text{kbytes}$ . It is decided to use two level page tables to translate from virtual address to physical ... entries that can be contained in each page? How many bits are available for storing protection and other information in each page table entry?
asked Sep 16, 2014 in Operating System Kathleen 4.6k views
15 votes
2 answers
8
Draw the process state transition diagram of an OS in which (i) each process is in one of the five states: created, ready, running, blocked (i.e., sleep or wait), or terminated, and (ii) only non-preemptive scheduling is used by the OS. Label the transitions appropriately.
asked Sep 16, 2014 in Operating System Kathleen 2.2k views
26 votes
2 answers
9
The following table refers to search items for a key in $B$-trees and $B^+$ ... $(2,11)$ and $(11,6)$ are now inserted into $R.$ What are the additional tuples that are inserted in $V$?
asked Sep 16, 2014 in Databases Kathleen 2.4k views
40 votes
3 answers
10
For relation R=(L, M, N, O, P), the following dependencies hold: $ M \rightarrow O,$ $NO \rightarrow P,$ $P \rightarrow L$ and $L \rightarrow MN$ R is decomposed into R1 = (L, M, N, P) and R2 = (M, O). Is the above ... . Is the above decomposition dependency-preserving? If not, list all the dependencies that are not preserved. What is the highest normal form satisfied by the above decomposition?
asked Sep 16, 2014 in Databases Kathleen 3.9k views
19 votes
4 answers
11
A university placement center maintains a relational database of companies that interview students on campus and make job offers to those successful in the interview. The schema of the database is given below: ... $five$ students were offered jobs, the name of the degree and the average offered salary of students in this degree program.
asked Sep 16, 2014 in Databases Kathleen 1.9k views
19 votes
1 answer
12
The aim of the following question is to prove that the language $\{M \mid M$ $\text {is the code of the Turing Machine which, irrespective of the input, halts and outputs a}$ $1\}$, is undecidable. This is to be done by reducing from the language $\{M', x \mid M'$ ... what is the second step $M$ must make? What key property relates the behaviour of $M$ on $w$ to the behaviour of $M'$ on $x$?
asked Sep 16, 2014 in Theory of Computation Kathleen 1.3k views
23 votes
7 answers
13
In how many ways can a given positive integer $n \geq 2$ be expressed as the sum of $2$ positive integers (which are not necessarily distinct). For example, for $n=3$, the number of ways is $2$, i.e., $1+2, 2+1$. Give only the answer ... positive integer $n \geq k$ be expressed as the sum of $k$ positive integers (which are not necessarily distinct). Give only the answer without explanation.
asked Sep 16, 2014 in Combinatory Kathleen 2.1k views
18 votes
3 answers
14
Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths in a directed graph $G$ with $n*n$ adjacency matrix $A$. $A[i,j]$ equals $1$ if there is an edge in $G$ from $i$ to $j$, and $0$ otherwise. Your ... complete line containing the blanks in the Algorithm step and fill in the blanks. Fill in the blank: The running time of the Algorithm is $O$(___).
asked Sep 16, 2014 in Algorithms Kathleen 1.9k views
16 votes
2 answers
15
The following recursive function in C is a solution to the Towers of Hanoi problem. void move(int n, char A, char B, char C) { if (......................) { move (.............................); printf("Move disk %d from pole %c to pole %c\n", n, A,C); move (.....................); } } Fill in the dotted parts of the solution.
asked Sep 16, 2014 in Programming Kathleen 1.4k views
29 votes
1 answer
16
In a C program, an array is declared as $\text{float} \ A[2048]$. Each array element is $4 \ \text{Bytes}$ in size, and the starting address of the array is $0x00000000$. This program is run on a computer that has a direct mapped data ... would occur? Justify your answer briefly. Assume that the data cache is initially empty and that no other data or instruction accesses are to be considered.
asked Sep 16, 2014 in CO and Architecture Kathleen 2.3k views
31 votes
4 answers
17
Consider the following $32-bit$ floating-point representation scheme as shown in the format below. A value is specified by $3$ fields, a one bit sign field (with $0$ for positive and $1$ for negative values), a $24 bit$ fraction field (with the binary point ... in the hexadecimal. What is the largest value that can be represented using this format? Express your answer as the nearest power of $10$.
asked Sep 16, 2014 in Digital Logic Kathleen 4.2k views
10 votes
1 answer
18
Consider the following circuit. $A = a_2a_1a_0$ and $B=b_2b_1b_0$ are three bit binary numbers input to the circuit. The output is $Z=z_3z_2z_1z_0$. R0, R1 and R2 are registers with loading clock shown. The registers are loaded with their input data with the falling edge of a clock pulse ... b. What does the circuit implement?
asked Sep 16, 2014 in Digital Logic Kathleen 964 views
23 votes
4 answers
19
Express the function $f(x,y,z) = xy' + yz'$ with only one complement operation and one or more AND/OR operations. Draw the logic circuit implementing the expression obtained, using a single NOT gate and one or more AND/OR gates. Transform the following logic circuit (without expressing its switching function) into an equivalent logic circuit that employs only $6$ NAND gates each with $2$-inputs.
asked Sep 16, 2014 in Digital Logic Kathleen 2.3k views
14 votes
1 answer
20
Draw all binary trees having exactly three nodes labeled $A, B$ and $C$ on which preorder traversal gives the sequence $C, B, A$.
asked Sep 16, 2014 in DS Kathleen 857 views
21 votes
4 answers
21
Obtain the eigen values of the matrix$A=\begin {bmatrix} 1 & 2 & 34 & 49 \\ 0 & 2 & 43 & 94 \\ 0 & 0 & -2 & 104 \\ 0 & 0 & 0 & -1 \end{bmatrix}$
asked Sep 16, 2014 in Linear Algebra Kathleen 1.3k views
14 votes
2 answers
22
$S=\{(1,2), (2,1)\}$ is binary relation on set $A = \{1,2,3\}$. Is it irreflexive? Add the minimum number of ordered pairs to S to make it an equivalence relation. Give the modified $S$. Let $S=\{a,b\}$ and let $\square(S)$ be the powerset ... $\subseteq$ (set inclusion)' on $\square(S)$. Draw the Hasse diagram corresponding to the lattice ($\square(S), \subseteq$)
asked Sep 16, 2014 in Set Theory & Algebra Kathleen 1.2k views
14 votes
4 answers
23
Let $A$ be a set of $n(>0)$ elements. Let $N_r$ be the number of binary relations on $A$ and let $N_f$ be the number of functions from $A$ to $A$ Give the expression for $N_r,$ in terms of $n.$ Give the expression for $N_f,$ terms of $n.$ Which is larger for all possible $n,N_r$ or $N_f$
asked Sep 16, 2014 in Set Theory & Algebra Kathleen 1.2k views
35 votes
6 answers
24
From the following instance of a relation schema $R(A,B,C)$ ... $B$ does not functionally determine $C$ $B$ does not functionally determine $C$ $A$ does not functionally determine $B$ and $B$ does not functionally determine $C$
asked Sep 16, 2014 in Databases Kathleen 5.2k views
33 votes
5 answers
25
Relation $R$ is decomposed using a set of functional dependencies, $F$, and relation $S$ is decomposed using another set of functional dependencies, $G$. One decomposition is definitely $\text{BCNF}$, the other is definitely $3NF$, but it is not known which ... (Assume that the closures of $F$ and $G$ are available). Dependency-preservation Lossless-join $\text{BCNF}$ definition $3NF$ definition
asked Sep 16, 2014 in Databases Kathleen 4k views
25 votes
3 answers
26
A $B^+$ - tree index is to be built on the Name attribute of the relation STUDENT. Assume that all the student names are of length $8$ bytes, disk blocks are of size $512$ bytes, and index pointers are of size $4$ bytes. Given the scenario, what would be the best choice of the degree (i.e. number of pointers per node) of the $B^+$ - tree? $16$ $42$ $43$ $44$
asked Sep 16, 2014 in Databases Kathleen 5.6k views
22 votes
5 answers
27
In the index allocation scheme of blocks to a file, the maximum possible size of the file depends on the size of the blocks, and the size of the address of the blocks. the number of blocks used for the index, and the size of the blocks. the size of the blocks, the number of blocks used for the index, and the size of the address of the blocks. None of the above
asked Sep 16, 2014 in Databases Kathleen 5.5k views
33 votes
4 answers
28
Which combination of the following features will suffice to characterize an OS as a multi-programmed OS? More than one program may be loaded into main memory at the same time for execution If a program waits for certain events such as I/O, another program is immediately scheduled for execution If ... program is immediately scheduled for execution. (a) (a) and (b) (a) and (c) (a), (b) and (c)
asked Sep 16, 2014 in Operating System Kathleen 4.6k views
24 votes
4 answers
29
Dynamic linking can cause security concerns because Security is dynamic The path for searching dynamic libraries is not known till runtime Linking is insecure Cryptographic procedures are not available for dynamic linking
asked Sep 16, 2014 in Operating System Kathleen 2.6k views
24 votes
2 answers
30
To evaluate an expression without any embedded function calls One stack is enough Two stacks are needed As many stacks as the height of the expression tree are needed A Turing machine is needed in the general case
asked Sep 16, 2014 in Compiler Design Kathleen 3.2k views
...