search
Log In

Recent questions tagged gate2003

2 votes
2 answers
1
2^2n =O(2^n) True or False Its false but why
asked Nov 26, 2017 in Algorithms aka 53 232 views
5 votes
0 answers
2
Consider this GATE 2003 question: https://gateoverflow.in/937/gate2003-46 Here, instead of XOR gates we had OR gates, then which of the following operations can we perform? $A + B, A - B\ and\ A + 1$
asked Nov 3, 2017 in CO and Architecture Rishabh Gupta 2 352 views
4 votes
0 answers
3
Consider the following logic program P A(x) <- B(x, y), C(y) <- B(x,x) Which of the following first order sentences is equivalent to P? Can anyone explain how it can be solved ?
asked Jun 29, 2017 in Mathematical Logic Syedarshadali 508 views
53 votes
3 answers
4
A processor uses $\text{2-level}$ page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both $32$ bits wide. The memory is byte addressable. For virtual to physical address translation, the $10$ most ... the page tables of this process is $\text{8 KB}$ $\text{12 KB}$ $\text{16 KB}$ $\text{20 KB}$
asked Apr 24, 2016 in Operating System jothee 9.6k views
22 votes
3 answers
5
Consider the following assembly language program for a hypothetical processor A, B, and C are 8 bit registers. The meanings of various instructions are shown as comments. MOV B, #0 ; $B \leftarrow 0$ MOV C, #8 ; $C \leftarrow 8$ Z: CMP C, #0 ; compare C with 0 JZ X ; jump ... as same as its initial value? RRC A, #1 NOP ; no operation LRC A, #1; left rotate A through carry flag by one bit ADD A, #1
asked Apr 24, 2016 in CO and Architecture jothee 3.9k views
44 votes
6 answers
6
In a permutation \(a_1 ... a_n\), of $n$ distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\). What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of \(1. . . n\) with at most $n$ inversions? \(\Theta(n^2)\) \(\Theta(n\log n)\) \(\Theta(n^{1.5})\) \(\Theta(n)\)
asked Apr 24, 2016 in Algorithms jothee 7.8k views
28 votes
6 answers
7
The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions. global int i=100, j=5; void P(x) { int i=10; print(x+10); i=200; j=20; print (x); } main() {P(i+j);} If the ... scoping and call by name parameter passing mechanism, the values printed by the above program are $115, 220$ $25, 220$ $25, 15$ $115, 105$
asked Apr 24, 2016 in Compiler Design jothee 3.7k views
38 votes
5 answers
8
Suppose we want to synchronize two concurrent processes $P$ and $Q$ using binary semaphores $S$ and $T$. The code for the processes $P$ and $Q$ ... $Z, S$ initially $1$ $V(S)$ at $W, V(T)$ at $X, P(S)$ at $Y, P(T)$ at $Z, S$ and $T$ initially $1$
asked Apr 24, 2016 in Operating System jothee 4.7k views
36 votes
6 answers
9
Consider the following circuit composed of XOR gates and non-inverting buffers. The non-inverting buffers have delays $\delta_1 = 2 ns$ and $\delta_2 = 4 ns$ as shown in the figure. Both XOR gates and all wires have zero delays. Assume that all gate inputs, outputs, and wires are stable at logic ... (change of logic levels) occur(s) at $B$ during the interval from $0$ to $10$ ns? $1$ $2$ $3$ $4$
asked Dec 2, 2015 in Digital Logic shikharV 6.6k views
41 votes
6 answers
10
In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time $\Theta (n \log n)$ $\Theta (n)$ $\Theta(\log n)$ $\Theta(1)$
asked Sep 19, 2014 in DS Disha 11.7k views
30 votes
4 answers
11
Consider the function $f$ defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ((p == NULL) || (p->next == NULL)|| ((p->data <= p ->next -> data) && f(p->next))); } For a given linked list ... in non-decreasing order of data value the elements in the list are sorted in non-increasing order of data value not all elements in the list have the same data value
asked Sep 17, 2014 in DS Kathleen 4.8k views
25 votes
6 answers
12
Consider the C program shown below: #include<stdio.h> #define print(x) printf("%d", x) int x; void Q(int z) { z+=x; print(z); } void P(int *y) { int x = *y + 2; Q(x); *y = x - 1; print(x); } main(void) { x = 5; P(&x); print(x); } The output of this program is: $12 \ 7 \ 6$ $22 \ 12 \ 11$ $14 \ 6 \ 6$ $7 \ 6 \ 6$
asked Sep 17, 2014 in Programming Kathleen 4.6k views
37 votes
6 answers
13
In the following $C$ program fragment, $j$, $k$, $n$ and TwoLog_n are integer variables, and $A$ is an array of integers. The variable $n$ is initialized to an integer $\geqslant 3$, and TwoLog_n is initialized to the value of $2^*\lceil \log_2(n) \rceil$ for (k = 3; k <= n; k++) A[k] ... $\left\{m \mid m \leq n, \text{m is prime} \right\}$ { }
asked Sep 17, 2014 in Algorithms Kathleen 4.3k views
28 votes
4 answers
14
Consider three data items $D1, D2,$ and $D3,$ and the following execution schedule of transactions $T1, T2,$ and $T3.$ In the diagram, $R(D)$ and $W(D)$ denote the actions reading and writing the data item $D$ ... $T2; T3; T1$ The schedule is serializable as $T2; T1; T3$ The schedule is serializable as $T3; T2; T1$ The schedule is not serializable
asked Sep 17, 2014 in Databases Kathleen 3.4k views
29 votes
3 answers
15
Consider the set of relations shown below and the SQL query that follows. Students: (Roll_number, Name, Date_of_birth) Courses: (Course_number, Course_name, Instructor) Grades: (Roll_number, Course_number, Grade) Select distinct Name from Students, Courses, Grades where Students.Roll_number= ... of students who have got an A grade in at least one of the courses taught by Korth None of the above
asked Sep 17, 2014 in Databases Kathleen 5.1k views
29 votes
3 answers
16
Consider the following functional dependencies in a database. ... , Age) is in second normal form but not in third normal form in third normal form but not in BCNF in BCNF in none of the above
asked Sep 17, 2014 in Databases Kathleen 5.2k views
53 votes
7 answers
17
Host $A$ is sending data to host $B$ over a full duplex link. $A$ and $B$ are using the sliding window protocol for flow control. The send and receive window sizes are $5$ packets each. Data packets (sent only from $A$ to $B$) are all $1000$ bytes long and the transmission time for ... communication? $7.69 \times 10^6$ Bps $11.11 \times 10^6$ Bps $12.33 \times 10^6$ Bps $15.00 \times 10^6$ Bps
asked Sep 17, 2014 in Computer Networks Kathleen 11.6k views
21 votes
7 answers
18
A $2$ $km$ long broadcast LAN has $10^7$ bps bandwidth and uses CSMA/CD. The signal travels along the wire at $2 \times 10^8$ m/s. What is the minimum packet size that can be used on this network? $50$ $\text{bytes}$ $100$ $\text{bytes}$ $200$ $\text{bytes}$ None of the above
asked Sep 17, 2014 in Computer Networks Kathleen 4.6k views
31 votes
6 answers
19
The subnet mask for a particular network is $255.255.31.0.$ Which of the following pairs of $\text{IP}$ addresses could belong to this network? $172.57.88.62$ and $172.56.87.23$ $10.35.28.2$ and $10.35.29.4$ $191.203.31.87$ and $191.234.31.88$ $128.8.129.43$ and $128.8.161.55$
asked Sep 17, 2014 in Computer Networks Kathleen 10.7k views
20 votes
3 answers
20
Suppose we want to synchronize two concurrent processes $P$ and $Q$ using binary semaphores $S$ and $T$. The code for the processes $P$ and $Q$ is shown below. Process P: Process Q: while(1) { while(1) { W: Y: print '0'; print '1'; print '0'; print '1'; X: Z: } } Synchronization statements can be ... $P(S)$ at $W, V(S)$ at $X, P(T)$ at $Y, V(T)$ at $Z, S$ initially $1$ , and $T$ initially $0$
asked Sep 17, 2014 in Operating System Kathleen 2.7k views
60 votes
3 answers
21
A uni-processor computer system only has two processes, both of which alternate $10$ $\text{ms}$ CPU bursts with $90$ $\text{ms}$ I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in ... first scheduling Static priority scheduling with different priorities for the two processes Round robin scheduling with a time quantum of $5$ $\text{ms}$
asked Sep 17, 2014 in Operating System Kathleen 6.8k views
37 votes
4 answers
22
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statistically linked libraries? Smaller sizes of executable files Lesser overall page fault rate in the system Faster program startup Existing programs need not be re-linked to take advantage of newer versions of libraries
asked Sep 17, 2014 in Compiler Design Kathleen 6.1k views
2 votes
3 answers
23
Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar. Class P { Class Q subclass of P { void f(int i) { void f(int i ... of y to P. The output produced by executing the above program fragment will be 1 2 1 2 1 1 2 1 2 2 2 2
asked Sep 17, 2014 in Programming Kathleen 2k views
26 votes
5 answers
24
The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions. global int i=100, j=5; void P(x) { int i=10; print(x+10); i=200; j=20; print (x); } main() {P(i+j);} If the ... and call by need parameter passing mechanism, the values printed by the above program are: $115, 220$ $25, 220$ $25, 15$ $115, 105$
asked Sep 17, 2014 in Programming Kathleen 3.4k views
32 votes
5 answers
25
The following resolution rule is used in logic programming. Derive clause $(P \vee Q)$ from clauses $(P\vee R),(Q \vee ¬R)$ Which of the following statements related to this rule is FALSE? $((P ∨ R)∧(Q ∨ ¬R))⇒(P ∨ Q)$ is logically valid $(P ∨ Q)⇒((P ∨ R))∧(Q ∨ ¬R))$ ... if and only if $(P ∨ R)∧(Q ∨ ¬R)$ is satisfiable $(P ∨ Q)⇒ \text{FALSE}$ if and only if both $P$ and $Q$ are unsatisfiable
asked Sep 17, 2014 in Mathematical Logic Kathleen 4.3k views
4 votes
0 answers
26
Consider the following logic program P $\begin{align*} A(x) &\gets B(x,y), C(y) \\ &\gets B(x,x) \end{align*}$ Which of the following first order sentences is equivalent to P? $(\forall x) [(\exists y) [B(x,y) \land C(y)] \Rightarrow A(x)] \land \neg (\exists x)[B(x,x)]$ ... $(\forall x) [(\forall y) [B(x,y) \land C(y)] \Rightarrow A(x)] \land (\exists x)[B(x,x)]$
asked Sep 17, 2014 in Programming Kathleen 1.9k views
39 votes
4 answers
27
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex ... longest path length from $j$ to $k$ If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges
asked Sep 17, 2014 in Algorithms Kathleen 6.2k views
35 votes
10 answers
28
The following are the starting and ending times of activities $A, B, C, D, E, F, G$ and $H$ respectively in chronological order: $ a_s \: b_s \: c_s \: a_e \: d_s \: c_e \: e_s \: f_s \: b_e \: d_e \: g_s \: e_e \: f_e \: h_s \: g_e \: h_e $ ... scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required? $3$ $4$ $5$ $6$
asked Sep 17, 2014 in Algorithms Kathleen 4.3k views
14 votes
2 answers
29
What is the weight of a minimum spanning tree of the following graph? $29$ $31$ $38$ $41$
asked Sep 17, 2014 in Algorithms Kathleen 2.4k views
57 votes
4 answers
30
Let $G =(V,E)$ be an undirected graph with a subgraph $G_1 = (V_1, E_1)$. Weights are assigned to edges of $G$ as follows. $w(e) = \begin{cases} 0 \text{, if } e \in E_1 \\1 \text{, otherwise} \end{cases}$ A single-source shortest path algorithm is executed on ... number of edges in the shortest paths from $v_1$ to all vertices of $G$ $G_1$ is connected $V_1$ forms a clique in $G$ $G_1$ is a tree
asked Sep 17, 2014 in Algorithms Kathleen 7.4k views
...