text:
## Gate IT 2007

 Question 1
Suppose there are two coins. The first coin gives heads with probability 5/8 when tossed, while the second coin gives heads with probability 1/4. One of the two coins is picked up at random with equal probability and tossed. What is the probability of obtaining heads ?
 A 7/8 B 1/2 C 7/16 D 5/32
Gate IT 2007
Discuss it

Question 1 Explanation:
Either 1st coin is selected or second coin is selected
Probability of 1st coin to be selected = ½
And probability of getting head on it = 5/8
Or
Probability of 2nd coin to be selected = 1/2
And pobability of getting head on 2nd coin = ¼
Probability of getting head (overall) = (Probability of selecting 1st coin * Probability of head on it) +(Probability of selecting 2nd coin * Probability of getting head on it) = (1/2)*(5/8) + (1/2)*(1/4) = 7/16
 Question 2
Let A be the . What is the maximum value of xTAx where the maximum is taken over all x that are the unit eigenvectors of A?
 A 5 B (5 + √5)/2 C 3 D (5 - √5)/2
Gate IT 2007
Discuss it

Question 2 Explanation:
|M-λ.I| = 0, where λ is the eigen values and I is the identity matrix
|A-(λ*I)| = 0
(3-λ)(2-λ)-1 = 0
6-3λ -2λ + λ2+1=0
λ2-5λ+5=0
λ = (5+√5)/2 and (5-√5)/2,
λ = (5+√5)/2 is max value another root with negative sign which will not be max value.
For, λ=5+5√2, xTAx=[18.131 21.231 21.231 34.331]
For, λ=5−5√2, xTAx=[Tex]\begin{pmatrix} 14.300&−0.700\\ 6.200&1.200 \end{pmatrix}[/Tex]
Hence, for λ=5+5√2 the value of xTAx is maximum.
 Question 3
Consider a weighted undirected graph with positive edge weights and let uv be an edge in the graph. It is known that the shortest path from the source vertex s to u has weight 53 and the shortest path from s to v has weight 65. Which one of the following statements is always true?
 A weight (u, v) < 12 B weight (u, v) ≤ 12 C weight (u, v) > 12 D weight (u, v) ≥ 12
Graph Shortest Paths    Graph Theory    Gate IT 2007
Discuss it

Question 3 Explanation:
The minimum weight happens when (S,U) + (U,V) = (S,V) Else (S,U) + (U,V) >= (S,V) Given (S,U) = 53, (S,V) = 65 53 + (U,V) >= 63 (U,V) >= 12. This solution is contributed by Anil Saikrishna Devarasetty
 Question 4
In the Spiral model of software development, the primary determinant in selecting activities in each iteration is
 A Iteration size B Cost C Adopted process such as Rational Unified Process or Extreme Programming D Risk
Software Engineering    Gate IT 2007
Discuss it

Question 4 Explanation:
Spiral model is used to discover all risks associated as early as possible.
 Question 5
Which of the following systems is a most likely candidate example of a pipe and filter architecture ?
 A Expert system B DB repository C Aircraft flight controller D Signal processing
Computer Organization and Architecture    Gate IT 2007
Discuss it

Question 5 Explanation:

Reference: Software Architecture: A Case Based Approach By Vasudeva Varma, Varma Vasudeva
 Question 6
A processor takes 12 cycles to complete an instruction I. The corresponding pipelined processor uses 6 stages with the execution times of 3, 2, 5, 4, 6 and 2 cycles respectively. What is the asymptotic speedup assuming that a very large number of instructions are to be executed?
 A 1.83 B 2 C 3 D 6
Computer Organization and Architecture    Gate IT 2007
Discuss it

Question 6 Explanation:
For non pipeline processor,
It takes, 12 cycles to complete 1 instruction
So, for n instructions it will take 12n cycle
For pipelined processor,
Each stage time = max{each stage cycles} = max{3, 2, 5, 4, 6 and 2} = 6 cycles
So, for n instructions it will take = 6*6+ (n-1)*6 {6*6 for 1st instruction and for rest of n-1 it will take 6}
For a large number of instructions:
Limn->∞ 12n/36 + (n-1)*6 = 12/6 =2
 Question 7
Which of the following input sequences for a cross-coupled R-S flip-flop realized with two NAND gates may lead to an oscillation ?
 A 11, 00 B 01, 10 C 10, 01 D 00, 11
Digital Logic & Number representation    Gate IT 2007
Discuss it

Question 7 Explanation:
RS flip flop using NAND gates. So, 00 input causes indeterminate state which MAY lead to oscillation.
 Question 8
The following circuit implements a two-input AND gate using two 2-1 multiplexers.

What are the values of X1, X2, X3?
 A X1=b, X2=0, X3=a B X1=b, X2=1, X3=b C X1=a, X2=b, X3=1 D X1=a, X2=0, X3=b
Digital Logic & Number representation    Gate IT 2007
Discuss it

Question 8 Explanation:

F = (bX1' + aX1)X3 + X2X3'
By putting following values: X1 = b, X2 = 0, X3 = a
We will get F = ab.
 Question 9
Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?
 A L (D) ⊂ L (G) B L (D) ⊃ L (G) C L (D) = L (G) D L (D) is empty
Regular languages and finite automata    Gate IT 2007
Discuss it

Question 9 Explanation:
By changing grammar, language will not change here. {as converting NFA to DFA language will not be changed}
 Question 10
Processes P1 and P2 use critical_flag in the following routine to achieve mutual exclusion. Assume that critical_flag is initialized to FALSE in the main program.
 get_exclusive_access ( ) { if (critical _flag == FALSE) { critical_flag = TRUE ; critical_region () ; critical_flag = FALSE; } } Consider the following statements.
i. It is possible for both P1 and P2 to access critical_region concurrently.
Which of the following holds?
 A (i) is false and (ii) is true B Both (i) and (ii) are false C (i) is true and (ii) is false D Both (i) and (ii) are true
Process Management    Deadlock    Gate IT 2007
Discuss it

Question 10 Explanation:

Say P1 starts first and executes statement 1, after that system context switches to P2 (before executing statement 2), and it enters inside if statement, since the flag is still false. So now both processes are in critical section!! so (i) is true.. (ii) is false By no way it happens that flag is true and no process' are inside the if clause, if someone enters the critical section, it will definitely make flag = false. So no deadlock.
 Question 11
Let a memory have four free blocks of sizes 4k, 8k, 20k, 2k. These blocks are allocated following the best-fit strategy. The allocation requests are stored in a queue as shown below.

The time at which the request for J7 will be completed will be
 A 16 B 19 C 20 D 37
Gate IT 2007
Discuss it

Question 11 Explanation:
Initially when a process arrives and needs memory, it would search for a hole big enough to fit the job and if the hole is larger then the remaining hole is returned to the free storage list.
 Memory Block Size Job (t=0) Job(t=8) Job(t=10) Job(t=11) 1 4k J3 - 2 units (1K free left) 2 8k J4 – 8 units (2K free left) J5 - 14 units J5 – 14 units J5 – 14 units 3 20k J2 -10 units(6K free left) J2 -10 units J6 – 11 units J7 – 19 units 4 2k J1 -4 units
Therefore, the process finishes at J7=19 units Option B
 Question 12
The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 bytes per page is
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0410.
Suppose that the memory can store only one page and if x is the address which causes a page fault then the bytes from addresses x to x + 99 are loaded on to the memory.
How many page faults will occur ?
 A 0 B 4 C 7 D 8
Memory Management    Gate IT 2007
Discuss it

Question 12 Explanation:

Address	        Page faults	last byte in memory
0100 		page fault, 	 199
0200 		page fault, 	 299
0430		page fault,      529
0499 		no page fault
0510 		no page fault
0530 		page fault,     629
0560            no page fault
0120 		page fault,     219
0220	 	page fault,     319
0240            no page fault
0260            no page fault
0320		page fault,     419
0410            no page fault
So, 7 is the answer- (C)
 Question 13
Consider the following statements about the timeout value used in TCP. i. The timeout value is set to the RTT (Round Trip Time) measured during TCP connection establishment for the entire duration of the connection. ii. Appropriate RTT estimation algorithm is used to set the timeout value of a TCP connection. iii. Timeout value is set to twice the propagation delay from the sender to the receiver. Which of the following choices hold?
 A (i) is false, but (ii) and (iii) are true B (i) and (iii) are false, but (ii) is title C (i) and (ii) are false, but (iii) is true D (i), (ii) and (iii) are false
Transport Layer    Misc Topics in Computer Networks    Gate IT 2007
Discuss it

Question 13 Explanation:
Time-out timer in TCP: One can’t use static timer used in data link layer (DLL), which is HOP to HOP connection, since nobody knows how many hops are there in the path form sender to receiver as it uses IP service and path may vary time to time. So, dynamic timers are used in TCP. Time-out timer should increase or decrease depending on traffic to avoid unnecessary congestion due to retransmissions. There are three algorithms are for this purpose: 1. Basic algorithm 2. Jacobson’s algorithm 3. Karl’s modification. Solution:
1. The timeout value is set to the RTT (Round Trip Time) measured during TCP connection establishment for the entire duration of the connection.- FALSE The timeout value can’t be fixed for entire duration as it will turn timer to static timer, we need dynamic timer for timeout.
1. Appropriate RTT estimation algorithm is used to set the timeout value of a TCP connection.-TRUE Yes, all three algorithm are appropriate RTT estimation algorithm used to set timeout value dynamically.
1. Timeout value is set to twice the propagation delay from the sender to the receiver.-FALSE This statement is false because, timeout value is set to twice the propagation delay in data link layer where, hop to hop distance is known, not in TCP layer.
This solution is contributed by Sandeep pandey.
 Question 14
Consider a TCP connection in a state where there are no outstanding ACKs. The sender sends two segments back to back. The sequence numbers of the first and second segments are 230 and 290 respectively. The first segment was lost, but the second segment was received correctly by the receiver. Let X be the amount of data carried in the first segment (in bytes), and Y be the ACK number sent by the receiver. The values of X and Y (in that order) are
 A 60 and 290 B 230 and 291 C 60 and 231 D 60 and 230
Transport Layer    Gate IT 2007
Discuss it

Question 14 Explanation:
data in 1st segment is from byte number 230 to byte number 289, that is 60 bytes As 1st is lost so, TCP will send ACK for the next in-order segment receiver is expecting. So it will be for 230.
 Question 15
Consider the following two statements: i. A hash function (these are often used for computing digital signatures) is an injective function. A. encryption technique such as DES performs a permutation on the elements of its input alphabet. Which one of the following options is valid for the above two statements?
 A Both are false B Statement (i) is true and the other is false C Statement (ii) is true and the other is false D Both are true
Network Security    Gate IT 2007
Discuss it

Question 15 Explanation:

Injective Function:

A function F(X) is said to be injective if it has one-to-one mapping. Statement 1: Hash function is an injective function Statement 2: DES Encryption technique performs a permutation on the elements of its input alphabet

1) Generally, a hash function H(X) is mapping from a larger set to a predefined output set For example, let H(X) = (X)%5 The above function H(X) is not injective because Let X1 = 10, X2 = 15 H(10) = H(15) = 0 As the output of H(X1) = H(X2) where X1!= X2 => H(X) is many-to-one function. Statement 1 is false.

2) In DES encryption scheme, it performs P-Box permutation. Statement 1 is false, Statement 2 is true.

This solution is contributed by Anil Saikrishna Devarasetty.

 Question 16
The minimum positive integer p such that 3p modulo 17 = 1 is
 A 5 B 8 C 12 D 16
Misc    Network Security    Gate IT 2007
Discuss it

Question 16 Explanation:
Either use Fermat's Little Theorem (reference)
Or put the value of p and get the answer
 Question 17
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute bn mod m,0≤b,n≤m ?
 A O(logn) B O(√n) C O(n/logn) D O(n)
Network Security    Gate IT 2007
Discuss it

Question 17 Explanation:
This Problem can be solved using Divide And Conquer Paradigm Algorithm :

Binary_exp(b,n)                            // Compute bn mod m

{

if(n == 0)

Return 1;

Else if(n == 1)

Return b mod m;

Else

{

Half = Binary_exp(b,n/2);

if(n%2 == 0)                                // n is even

Return (Half*Half) mod m;

Else                                    // n is odd

Return (((Half*Half) mod m)*n) mod m;

}

}

Recurrence Relation for computing the time complexity of the above given algorithm is T(n) = T(n/2) + constant = (log2n) This solution is contributed by Pranjul Ahuja.
 Question 18
A firewall is to be configured to allow hosts in a private network to freely open TCP connections and send packets on open connections. However, it will only allow external hosts to send packets on existing open TCP connections or connections that are being opened (by internal hosts) but not allow them to open TCP connections to hosts in the private network. To achieve this the minimum capability of the firewall should be that of
 A A combinational circuit B A finite automaton C A pushdown automaton with one stack D A pushdown automaton with two stacks
Misc Topics in Computer Networks    Network Security    Gate IT 2007
Discuss it

Question 18 Explanation:
A) A combinational circuit => Not possible, because we need memory in Firewall, Combinational ckt has none.
B) A finite automaton => We need infinite memory, there is no upper limit on Number of TCP ckt so Not this.
C) A pushdown automaton with one stack => Stack is infinite. Suppose we have 2 connections , we have pushed details of those on stack we can not access the details of connection which was pushed first, without popping it off. So Big NO.
D) pushdown automaton with two stacks => This is TM. It can do everything our normal computer can do so Yes. Firewall can be created out of TM.
 Question 19
Consider the XML document fragment given below:

With reference to the HTML lines given above, consider the following statements.
1. Clicking on the point <80, 75> does not have any effect.
2. The web browser can identify the area applicable to the mouse-click within the image and the subsequent action to be taken without additional responses from the web server.
3. The dots in the cgi-bin URL will be resolved by the web browser before it is sent to the web server
4. The "fd.html" request when sent to the web server will result in a GET request.
Exactly how many of the statements given above are correct?
 A 0 B 1 C 2 D 3
HTML and XML    Gate IT 2007
Discuss it

 Question 20
Consider the XML document fragment given below:

Consider the XPath expression: *[not (self ) : : TOC]
What would be the result of the given XPath expression when the current node is Book?
 A The Title and Content elements B The Content and TOC elements C The Title and TOC elements D The Title Content and TOC elements
HTML and XML    Gate IT 2007
Discuss it

Question 20 Explanation:
Out of Syllabus now
 Question 21
Which one of these first-order logic formula is valid?
 A ∀x(P(x) => Q(x)) => (∀xP(x) => ∀xQ(x)) B ∃x(P(x) ∨ Q(x)) => (∃xP(x) => ∃xQ(x)) C ∃x(P(x) ∧ Q(x)) <=> (∃xP(x) ∧ ∃xQ(x)) D ∀x∃y P(x, y) => ∃y∀x P(x, y)
Propositional and First Order Logic.    Gate IT 2007
Discuss it

Question 21 Explanation:
(A) LHS->RHS
LHS: For every x (if P holds then Q holds)
RHS: If P(x) holds for all x, then Q(x) holds for all x.
(B) LHS !->RHS
LHS: An x exist for which either P(x) is true or Q(x) is true.
RHS: If an x exist for which P(x) is true then another x exist for which Q(x) is true.
(C) It is not necessary that on RHS both x are same.
LHS: There exist an x for which both P(x) and Q(x) are true.
RHS: There exist an x for which P(x) is true and there exist an x for which Q(x) is true.
(D) LHS!->RHS
LHS: For every x, there exist a y such that P(x, y) holds.
RHS: There exist a y such that for all x P(x, y) holds.
 Question 22
The trapezoidal method is used to evaluate the numerical value of . Consider the following values for the step size h.
i. 10-2
ii. 10-3
iii. 10-4
iv. 10-5
For which of these values of the step size h, is the computed value guaranteed to be correct to seven decimal places. Assume that there are no round-off errors in the computation.
 A (iv) only B (iii) and (iv) only C (ii), (iii) and (iv) only D (i), (ii), (iii) and (iv)
Numerical Methods and Calculus    Gate IT 2007
Discuss it

 Question 23
A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division.
i. (0, 0) ∊ P.
ii. (a, b) ∊ P if and only if a % 10 ≤ b % 10 and (a/10, b/10) ∊ P.
Consider the following ordered pairs:
i. (101, 22)
ii. (22, 101)
iii. (145, 265)
iv. (0, 153)
Which of these ordered pairs of natural numbers are contained in P?
 A (i) and (iii) B (ii) and (iv) C (i) and (iv) D (iii) and (iv)
Numbers    Gate IT 2007
Discuss it

 Question 24
A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the dfs call to the vertex u terminates. Which of the following statements is always true for all edges (u, v) in the graph ?
 A d[u] < d[v] B d[u] < f[v] C f[u] < f[v] D f[u] > f[v]
Gate IT 2007
Discuss it

Question 24 Explanation:

Starting DFS at node V
1] Visit(V) -> DFS(X) ->Visit(X) ->DFS(U) ->Visit(U) -> backtrack(X) -> backtrack(V)
Therefore: d[U] > d[V], d[U] < f[V], f[U] < f[V]
But, visiting order is just opposite of finishing order.
Hence f[U] > f[V]
 Question 25
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?
 A 1 B 2 C 3 D n
Graph    Graph Minimum Spanning Tree    Gate IT 2007
Discuss it

Question 25 Explanation:
A graph is connected iff all nodes can be traversed from each node. For a graph with n nodes, there will be n-1 minimum number of edges.
Given that there are n edges, that means a cycle is there in the graph.
The simplex graph with these conditions may be:

Now we can make a different spanning tree by removing one edge from the cycle, one at a time.
Minimum cycle length can be 3, So, there must be atleast 3 spanning trees in any such Graph.
 Question 26
Consider n jobs J1, J2,......Jn such that job Ji has execution time ti and a non-negative integer weight wi. The weighted mean completion time of the jobs is defined to be , where Ti is the completion time of job Ji. Assuming that there is only one processor available, in what order must the jobs be executed in order to minimize the weighted mean completion time of the jobs?
 A Non-decreasing order of ti B Non-increasing order of wi C Non-increasing order of witi D None-increasing order of wi/ti
CPU Scheduling    Gate IT 2007
Discuss it

 Question 27
The function f is defined as follows:
int f (int n) {
if (n <= 1) return 1;
else if (n % 2  ==  0) return f(n/2);
else return f(3n - 1);
}

Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the following statements.
1. The function f terminates for finitely many different values of n ≥ 1.
ii. The function f terminates for infinitely many different values of n ≥ 1.
iii. The function f does not terminate for finitely many different values of n ≥ 1.
iv. The function f does not terminate for infinitely many different values of n ≥ 1.
Which one of the following options is true of the above?
 A (i) and (iii) B (i) and (iv) C (ii) and (iii) D (ii) and (iv)
Recursion    Functions    C Quiz - 113    Gate IT 2007
Discuss it

Question 27 Explanation:
The function terminates for all values having a factor of 2 {(2.x)2==0}
So, (i) is false and (ii) is TRUE.
Let n = 3, it will terminate in 2nd iteration.
Let n=5, it will go like 5 - 14 - 7 - 20 - 10 - 5 – and now it will repeat.
And any number with a factor of 5 and 2, there are infinite recursions possible.
So, (iv) is TRUE and (iii) is false.
 Question 28
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.
 A 5 B 6 C 7 D 10
Hash    Gate IT 2007
Discuss it

Question 28 Explanation:
For each entry probability of collision is 1/20 {as possible total spaces =20, and an entry will go into only 1 place}
Say after inserting x values probability becomes ½
 (1/20).x = ½
 X=10
 Question 29
When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value 60?
 A 35 B 64 C 128 D 5040
Binary Search Trees    Tree Traversals    Gate IT 2007
Discuss it

Question 29 Explanation:
There are two set of values, smaller than 60 and greater than 60. Smaller values 10, 20, 40 and 50 are visited, means they are visited in order. Similarly, 90, 80 and 70 are visited in order.
= 7!/(4!3!)
= 35
 Question 30
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
i. isEmpty (Q) — returns true if the queue is empty, false otherwise.
ii. delete (Q) — deletes the element at the front of the queue and returns its value.
iii. insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:
 void f (queue Q) {
int i ;
if (!isEmpty(Q)) {
i = delete(Q);
f(Q);
insert(Q, i);
}
}

What operation is performed by the above function f ?
 A Leaves the queue Q unchanged B Reverses the order of the elements in the queue Q C Deletes the element at the front of the queue Q and inserts it at the rear keeping the other elements in the same order D Empties the queue Q
Queue    C Quiz - 113    Gate IT 2007
Discuss it

Question 30 Explanation:
As it is recursive call, and removing from front while inserting from end, that means last element will be deleted at last and will be inserted 1st in the new queue. And like that it will continue till first call executes insert(Q,i) function.
So, the queue will be in reverse.
 Question 31
Consider the C program given below :
 #include <stdio.h>
int main ()    {
int sum = 0, maxsum = 0,  i,  n = 6;
int a [] = {2, -2, -1, 3, 4, 2};
for (i = 0; i < n; i++)    {
if (i == 0 || a [i]  < 0  || a [i] < a [i - 1])  {
if (sum > maxsum) maxsum = sum;
sum = (a [i] > 0) ? a [i] : 0;
}
else sum += a [i];
}
if (sum > maxsum) maxsum = sum ;
printf ("%d\n", maxsum);

}

What is the value printed out when this program is executed?
 A 9 B 8 C 7 D 6
Arrays    C Quiz - 113    Gate IT 2007
Discuss it

Question 31 Explanation:
If you look for loop carefully, you will notice that it assigns sum variable to some value in if condition and increments it in the else condition. On further thought, it would be clear that this loop stores sum of increasing subsequence of positive integers in sum variable and max of sum in maxsum. Hence, maxsum - maximum sum of increasing subsequence of positive integers will get printed out when this program is executed, which is 3 + 4 = 7. This solution is contributed by Vineet Purswani //output will be 3+4 =7 {for || if 1st argument is true 2nd argument will not be calculated, and if 1st argument is false, 2nd argument will be calculated} Another Solution When i=1 -> i==0 is false, but a[i]<0 is true so condition (1) is true.Now if (sum > maxsum) is true, since sum=2 and maxsum=0.So maxsum=2. sum = (a [i] > 0) ? a [i] : 0; , sum=0 since a[i]<0.
When i=2 -> i==0 is false, a[i]<0 is true and so condition (1) is true.Now if (sum > maxsum) is false, since sum=0 and maxsum=2.Since sum = (a [i] > 0) ? a [i] : 0; , sum=0 since a[i]<0.
When i=3 -> i==0 is false , a[i]<0 is false and a [i] < a [i – 1] is false so condition (1) is false. Now sum += a [i] = 3. When i=4 -> i==0 is false , a[i]<0 is false and a [i] < a [i – 1] is false so condition (1) is false. Now sum += a [i] = 7. When i=5 -> i==0 is false , a[i]<0 is false and a [i] < a [i – 1] is true so condition (1) is true. sum > maxsum is true, since sum=7 and maxsum=2,so maxsum=7.Since sum = (a [i] > 0) ? a [i] : 0, so sum=2 since a[5]>0. This solution is contributed by nirmal Bharadwaj
 Question 32
Consider the following C program:
   #include
#define EOF -1
void push (int); /* push the argument on the stack */
int pop  (void); /* pop the top of the stack */
void flagError ();
int main ()
{         int c, m, n, r;
while ((c = getchar ()) != EOF)
{ if  (isdigit (c) )
push (c);
else if ((c == '+') || (c == '*'))
{          m = pop ();
n = pop ();
r = (c == '+') ? n + m : n*m;
push (r);
}
else if (c != ' ')
flagError ();
}
printf("% c", pop ());
}

What is the output of the program for the following input ? 5 2 * 3 3 2 + * +
 A 15 B 25 C 30 D 150
Stack    C Quiz - 113    Gate IT 2007
Discuss it

Question 32 Explanation:
The function of the program is:- 1) If the current character is a digit it pushes into stack 2) Else if the current character is operator,  it pops two elements and then performs the operation. Finally it pushes the resultant element into stack. Initially stack s is empty. 5 2 * 3 3 2 + * + 1) 5 -> It pushes into s 2) 2 -> It pushes into s 3) * -> It pops two elements n = 2, m=5 n*m = 10 It pushes 10 into s 4) 3 -> It pushes into s 5) 3 -> It pushes into s 6) 2 -> It pushes into s 7) + -> n=2, m=3 n+m=5 It pushes 5 into s 8) * -> n=5, m=3 n*m=15 It pushes 15 into s 9) + -> n=15, m=10 n+m = 25 It pushes 25 into s.   Finally the result value is the only element present in stack. This solution is contributed  by Anil Saikrishna Devarasetty. Result = 25
 Question 33
Consider the program below in a hypothetical language which allows global variable and a choice of call by reference or call by value methods of parameter passing.
 int i ;
program main ()
{
int j = 60;
i = 50;
call f (i, j);
print i, j;
}
procedure f (x, y)
{
i = 100;
x = 10;
y = y + i ;
}

Which one of the following options represents the correct output of the program for the two parameter passing mechanisms?
 A Call by value : i = 70, j = 10; Call by reference : i = 60, j = 70 B Call by value : i = 50, j = 60; Call by reference : i = 50, j = 70 C Call by value : i = 10, j = 70; Call by reference : i = 100, j = 60 D Call by value : i = 100, j = 60; Call by reference : i = 10, j = 70
Variable Declaration and Scope    C Quiz - 113    Gate IT 2007
Discuss it

Question 33 Explanation:
Call by value: A copy of parameters will be passed and whatever updations are performed will be valid only for that copy, leaving original values intact.
Call by reference: A link to original variables will be passed, by allowing the function to manipulate the original variables.
 Question 34
Consider the program below in a hypothetical programming language which allows global variables and a choice of static or dynamic scoping.
 int i ;
program main ()
{
i = 10;
call f();
}

procedure f()
{
int i = 20;
call g ();
}
procedure g ()
{
print i;
}

Let x be the value printed under static scoping and y be the value printed under dynamic scoping. Then, x and y are
 A x = 10, y = 10 B x = 20, y = 10 C x = 10, y = 20 D x = 20, y = 20
Gate IT 2007
Discuss it

Question 34 Explanation:
Static scoping: 1
 Question 35
Early binding refers to a binding performed at compile time and late binding refers to a binding performed at execution time. Consider the following statements:
i. Static scope facilitates w1 bindings.
ii. Dynamic scope requires w2 bindings.
iii. Early bindings w3 execution efficiency.
iv. Late bindings w4 execution efficiency.
The right choices of wl, w2, w3 and w4 (in that order) are
 A Early, late, decrease, increase B Late, early, increase, decrease C Late, early, decrease, increase D Early, late, increase, decrease
Gate IT 2007
Discuss it

Question 35 Explanation:
Early binding can be done in Static Scoping(during compile time). Early binding increases efficiency (running time will be reduced).
Late binding can be done in Dynamic scoping (during execution time). Late binding decreases efficiency as it needs to be done at run-time. (but it increases flexibility)
 Question 36
The floating point unit of a processor using a design D takes 2t cycles compared to t cycles taken by the fixed point unit. There are two more design suggestions D1 and D2. D1 uses 30% more cycles for fixed point unit but 30% less cycles for floating point unit as compared to design D. D2 uses 40% less cycles for fixed point unit but 10% more cycles for floating point unit as compared to design D. For a given program which has 80% fixed point operations and 20% floating point operations, which of the following ordering reflects the relative performances of three designs?
(Di > Dj denotes that Di is faster than Dj)
 A D1 > D > D2 B D2 > D > D1 C D > D2 > D1 D D > D1 > D2
Gate IT 2007
Discuss it

Question 36 Explanation:
0.8 * (time taken in fixed point) + 0.2 (time taken in floating point)
Say, t=1
D = 0.8(1) + 0.2(2)
=1.2
D1 = 0.8(1.3)+0.2(1.4)
=1.04 +.28
=1.32
D2 = 0.8(1-0.04) + 0.2(2-2*0.1)
= 0.8*0.96 + 0.2*1.8
= 0.768 +0.36 = 1.128
D1>D>D2
 Question 37
Consider a Direct Mapped Cache with 8 cache blocks (numbered 0-7). If the memory block requests are in the following order 3, 5, 2, 8, 0, 63, 9,16, 20, 17, 25, 18, 30, 24, 2, 63, 5, 82,17, 24. Which of the following memory blocks will not be in the cache at the end of the sequence ?
 A 3 B 18 C 20 D 30
Gate IT 2007
Discuss it

Question 37 Explanation:
Location of memory block in cache  =  block  % number of cache blocks Since it is a direct mapped cache, no replacement policy is required. As we can see in the table, 18 is further replaced by 82 in the 2nd cache block whereas 3,20 and 30 are all present in the cache till the end. Therefore, Answer is B
 Memory Block Blocks 0 8, 0, 16, 24 1 9, 17, 25, 63, 17 2 2, 18, 2, 82 3 3 4 20 5 5, 5 6 30 7 63,63
 Question 38
The following expression was to be realized using 2-input AND and OR gates. However, during the fabrication all 2-input AND gates were mistakenly substituted by 2-input NAND gates.
(a.b).c + (a'.c).d + (b.c).d + a. d
What is the function finally realized ?
 A 1 B a' + b' + c' + d' C a' + b + c' + d' D a' + b' + c + d'
Gate IT 2007
Discuss it

 Question 39
Data forwarding techniques can be used to speed up the operation in presence of data dependencies. Consider the following replacements of LHS with RHS.

In which of the following options, will the result of executing the RHS be the same as executing the LHS irrespective of the instructions that follow ?
 A (i) and (iii) B (i) and (iv) C (ii) and (iii) D (ii) and (iv) E Only (i)
Gate IT 2007
Discuss it

Question 39 Explanation:
(i) Is true, as both registers and location are updated
(iii) and (iv) are the same!! and both are wrong because R2 is writing last, not R1.
(ii) false, because R2 get the correct data, but location has not got updated.
 Question 40
What is the final value stored in the linear feedback shift register if the input is 101101?
 A 0110 B 1011 C 1101 D 1111
Gate IT 2007
Discuss it

Question 40 Explanation:

The linear feedback shift register makes use of XOR gate for tapping and providing feedback. It works by shifting and placing the feedback value. Feedback value is determined by last bit and second bit tapped and fed to XOR gate.

 A B XOR 0 0 0 0 1 1 1 0 1 1 1 0
Reference: NPTEL: : http://nptel.ac.in/courses/106105031/19 This solution is contributed by Kriti Kushwaha .
 Question 41
Following table indicates the latencies of operations between the instruction producing the result and instruction using the result.
 Load R1, Loc 1;	 Load R1 from memory location Loc1
Add R1, R2, R1;	 Add R1 and R2 and save result in R1
Dec R2;	 Decrement R2
Dec R1;	 Decrement R1
Mpy R1, R2, R3;	 Multiply R1 and R2 and save result in R3
Store R3, Loc 3;	 Store R3 in memory location Loc 3

What is the number of cycles needed to execute the above code segment assuming each instruction takes one cycle to execute ?
 A 7 B 10 C 13 D 14
Gate IT 2007
Discuss it

Question 41 Explanation:
 Question 42
(C012.25)H - (10111001110.101)B =
 A (135103.412)o B (564411.412)o C (564411.205)o D (135103.205)o
Gate IT 2007
Discuss it

Question 42 Explanation:
(C012.25)H - (10111001110.101)B
= 1100 0000 0001 0010. 0010 0101 (convert each digit of hexa to 4 bit binary)
- 0000 0101 1100 1110. 1010 0000
= 1011 1010 0100 0011. 1000 0101
= 1 011 101 001 000 011 . 100 001 010 (make pairing of 3 to convert in octal)
= (135103.412)o
 Question 43
An error correcting code has the following code words:
00000000, 00001111, 01010101, 10101010, 11110000.
What is the maximum number of bit errors that can be corrected ?
 A 0 B 1 C 2 D 3
Gate IT 2007
Discuss it

Question 43 Explanation:
While transmitting the data through the channel , noise may be added to the data and thus, may cause errors in the data. Hamming code errors CANNOT be DETECTED if one code converts into another ,so if maximum hamming distance (i.e. the number of 1 s when we XOR 2 hamming codes ) between any two codes is ‘t’ then for detection error should not be more than t-1,otherwise the code could have been converted to another and we may assume that it is a correct hamming code. Similarly,for CORRECTION we should also know which hamming code it was,thus, if the maximum hamming distance is d then d/2 is the partition between two hamming codes from where we can find which code it was.Thus,if we have to correct ‘t’ errors then Max dist = 2*t +1 Max hamming distance is between 01010101 and 10101010 =>8 Thus, 8=2*t+1 t=3.5 We’ll take ceil as taking more than these bits will again make it impossible to correct the error. This solution is contributed by Shashank Shanker khare Another one d=(2t+1) t=number of bits could be corrected
maximum hamming distance between any two of the given code = 8 (between 01010101 and 10101010)
t=3.5, t=3
 Question 44
A hard disk system has the following parameters :
• Number of tracks = 500
• Number of sectors/track = 100
• Number of bytes /sector = 500
• Time taken by the head to move from one track to adjacent track = 1 ms
• Rotation speed = 600 rpm.
What is the average time taken for transferring 250 bytes from the disk ?
 A 300.5 ms B 255.5 ms C 255.0 ms D 300.0 ms
Gate IT 2007
Discuss it

Question 44 Explanation:
Avg. time to transfer = Avg. seek time + Avg. rotational delay + Data transfer time
• Avg Seek Time -  time taken  to move from 1st track to 1sr track : 0ms, 1st to 2nd : 1ms, 2ms, 3ms,....499ms Avg Seek time =( ∑0+1+2+3+...+499)/500 = 249.5 ms
• Avg Rotational Delay - RMP : 600 , 600 rotations in 60 sec (one Rotation = 60/600 sec = 0.1 sec) So, Avg Rotational Delay = 0.1/2= 50 ms
• Data Transfer Time: In One 1 Rotation we can read data on one track = 100 * 500 = 50,000 B data is read in one rotation. 250 bytes -> 0.1 * 250 / 50,000 = 0.5 ms
Therfore ATT = 295.5+50+0.5 = 300 ms
 Question 45
The line T in the following figure is permanently connected to the ground. Which of the following inputs (X1 X2 X3 X4) will detect the fault ?
 A 0000 B 0111 C 1111 D None of these
Gate IT 2007
Discuss it

Question 45 Explanation:

We consider circuit in two different configurations to check the inputs. And then apply the three available inputs to get output values. On doing so, we observe that all inputs give same outputs in both the configurations. Thus None of these is the answer.

This solution is contributed by Kriti Kushwaha.

 Question 46
The two grammars given below generate a language over the alphabet {x, y, z}

Which one of the following choices describes the properties satisfied by the strings in these languages?
 A G1 : No y appears before any x G2 : Every x is followed by at least one y B G1 : No y appears before any x G2 : No x appears before any y C G1 : No y appears after any x G2 : Every x is followed by at least one y D G1 : No y appears after any x G2 : Every y is followed by at least one x
Gate IT 2007
Discuss it

 Question 47
Consider the following DFA in which s0 is the start state and s1, s3 are the final states.

What language does this DFA recognize ?
 A All strings of x and y B All strings of x and y which have either even number of x and even number of y or odd number or x and odd number of y C All strings of x and y which have equal number of x and y D All strings of x and y with either even number of x and odd number of y or odd number of x and even number of y
Gate IT 2007
Discuss it

 Question 48
Consider the grammar given below
S → x B | y A
A → x | x S | y A A
B → y | y S | y B B
Consider the following strings.
(i) xxyyx
(ii) xxyyxy
(iii) xyxy
(iv) yxxy
(v) yxx
(vi) xyx
Which of the above strings are generated by the grammar ?
 A (i), (ii), and (iii) B (ii), (v), and (vi) C (ii), (iii), and (iv) D (i), (iii), and (iv)
Gate IT 2007
Discuss it

Question 48 Explanation:
Only iii and iv are possible.
 Question 49
Consider the following grammars. Names representing terminals have been specified in capital letters.

Which one of the following statements is true?
 A G1 is context-free but not regular and G2 is regular B G2 is context-free but not regular and G1 is regular C Both G1 and G2 are regular D Both G1 and G2 are context-free but neither of them is regular
Gate IT 2007
Discuss it

Question 49 Explanation:
Given grammars can be re-written as:
Say, while = w, expr =E, stmt = S, other = o
Here, we can write a right linear grammar for G1 as
S -> w(E)S
S -> o
E->ID
So, L(G1) is regular.
Now for G2 also we can write a right linear grammar:
S -> w(E)S
E -> E+E
E -> E*E
S -> o
So, L(G2) is regular
 Question 50
Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively.

The automation which recognizes the language L(P) ∩ L(Q) is :

 A a B b C c D d
Gate IT 2007
Discuss it

Question 50 Explanation:
Both accepts strings starting with a or b so option D cancels out.
In P(L) after c both a and b could be accepted, but in Q(L) only a could be accepted. Option C drops out here,
In P(L) aa could be accepted, but in Q(L) aa could not be accepted. Option B drops out here,
 Question 51
In the simplified flowchart given below, the shaded boxes represent code that is executed during a test case.

The Branch coverage is
 A 3/4 B 2/3 C 1/2 D 3/8
Gate IT 2007
Discuss it

Question 51 Explanation:

3/8 are exposed
 Question 52
Consider the CPM activity chart where an arc connecting two milestones is labeled with a task identifier and the time taken in days. For example in order to go from A to B, task T1 takes 180 days. A dashed line depicts an additional dependency that is equivalent to a zero time task.

The set of activities that lie on the critical path are
 A T1, T2, T8, T10 B T1, T3, T8, T10 C T1, T2, T3, T4, T5, T6, T7, T8, T9, T10 D T1, T4, T5, T7, T8, T10
Gate IT 2007
Discuss it

Question 52 Explanation:
Critical path is the one which takes longest time,
 Question 53
Consider the following pseudo-code:
 IF ((A > B) AND (C > D)) THEN
A = A + 1
B = B + 1
ENDIF

The cyclomatic complexity of the pseudo-code is
 A 2 B 3 C 4 D 5
Gate IT 2007
Discuss it

Question 53 Explanation:
Cyclomatic complexity = (π − s + 2)
where π is the number of decision points in the program, and s is the number of exit points.
 Question 54
Synchronization in the classical readers and writers problem can be achieved through use of semaphores. In the following incomplete code for readers-writers problem, two binary semaphores mutex and wrt are used to obtain synchronization
wait (wrt)
writing is performed
signal (wrt)
wait (mutex)
if readcount = 1 then S1
S2
S3
if readcount = 0 then S4
signal (mutex)

The values of S1, S2, S3, S4, (in that order) are
 A signal (mutex), wait (wrt), signal (wrt), wait (mutex) B signal (wrt), signal (mutex), wait (mutex), wait (wrt) C wait (wrt), signal (mutex), wait (mutex), signal (wrt) D signal (mutex), wait (mutex), signal (mutex), wait (mutex)
Gate IT 2007
Discuss it

Question 54 Explanation:
 Question 55
In a multi-user operating system on an average, 20 requests are made to use a particular resource per hour. The arrival of requests follows a Poisson distribution. The probability that either one, three or five requests are made in 45 minutes is given by :
 A 6.9 × 106 × e-20 B 1.02 × 106 × e-20 C 6.9 × 103 × e-20 D 1.02 × 103 × e-20
Gate IT 2007
Discuss it

Question 55 Explanation:
In 1 hr. requests received =20
So in 45 min requests received = 15
So, lemda = 15
So, using poission distribution formula: P(x; μ) = (e) (μx) / x!
p(one request) + p(3 request) + p(5 request) = p(1; 15) + p(3; 15) + p(5; 15) = 6.9 * 103 * e-15 = 1.02 × 106 × e-20
 Question 56
A demand paging system takes 100 time units to service a page fault and 300 time units to replace a dirty page. Memory access time is 1 time unit. The probability of a page fault is p. In case of a page fault, the probability of page being dirty is also p. It is observed that the average access time is 3 time units. Then the value of p is
 A 0.194 B 0.233 C 0.514 D 0.981
Gate IT 2007
Discuss it

Question 56 Explanation:
Page fault service time =100
page fault service time =300 (if there is dirty page)
probability of page fault =p
probability of being dirty is =p
so total page fault service time(ps) = p(300)+ (1-p)(100) = 200p+100
now given EAT =3 so
EAT = p(page fault service time +memory access time)+(1-p) memory access time
3= p*page fault service time + memory access time
3 =p(200p+100)+1= 200p2+100p+1
p=0.0194
 Question 57
The contents of the text file t1 txt containing four lines are as follows :
a1 b1
a2 b2
a3 b2
a4 b1
The contents of the text file t2 txt containing five lines are as follows :
a1 c1
a2 c2
a3 c3
a4 c3
a5 c4
Consider the following Bourne shell script :
 awk - F '  '  ' {Print $1,$2} ' t1.txt |
while read a b ; do
awk -v aV = $a - v by =$b  - F ' '
aV = = $1 (print aV, bV,$2 ) ' t2.txt
done

Which one of the following strings will NOT be present in the output generated when the above script in run?
(Note that the given strings may be substrings of a printed line.)
 A "b1 c1" B "b2 c3" C "b1 c2" D "b1 c3"
Gate IT 2007
Discuss it

 Question 58
For the network given in the figure below, the routing tables of the four nodes A, E, D and G are shown. Suppose that F has estimated its delay to its neighbors, A, E, D and G as 8, 10, 12 and 6 msecs respectively and updates its routing table using distance vector routing technique.

A.

B.

C.

D.
 A A B B C C D D
Gate IT 2007
Discuss it

Question 58 Explanation:
Distance from F to F is 0 which option C is dropped
Using DV routing protocol, F -> D -> B yields distance as 20 that drops option B and D.
 Question 59
In the waveform (a) given below, a bit stream is encoded by Manchester encoding scheme. The same bit stream is encoded in a different coding scheme in wave form (b). The bit stream and the coding scheme are
 A 1000010111 and Differential Manchester respectively B 0111101000 and Differential Manchester respectively C 1000010111 and Integral Manchester respectively D 0111101000 and Integral Manchester respectively
Gate IT 2007
Discuss it

Question 59 Explanation:
In simple language, Manchester encoding has +A to -A transition for the clock cycle for which bit is '1' and transition from -A to +A for the cycle when bit is '0' (A is the amplitude). The amplitudes are bipolar in Differential manchester encoding same as manchester encoding just that it toggles at '1'. When bit is '1' we get transition from +A to -A and it remains the same until next '1' arrives. The output changes to opposite transition (-A to +A) when next '1' arrives. The second encoding resembles the differential manchester code for the given number.   Image source: Google Images NPTEL Videos for Line coding: http://nptel.ac.in/courses/106105082/7 This solution is contributed by Kriti Kushwaha.
 Question 60
Let us consider a statistical time division multiplexing of packets. The number of sources is 10. In a time unit, a source transmits a packet of 1000 bits. The number of sources sending data for the first 20 time units is 6, 9, 3, 7, 2, 2, 2, 3, 4, 6, 1, 10, 7, 5, 8, 3, 6, 2, 9, 5 respectively. The output capacity of multiplexer is 5000 bits per time unit. Then the average number of backlogged of packets per time unit during the given period is
 A 5 B 4.45 C 3.45 D 0
Gate IT 2007
Discuss it

Question 60 Explanation:
he capacity of multiplexer is 5000 bits per unit time. This means there are 5 packets per unit time since each source transmits a packet of 1000 bits in a unit time. If the number of packets transmitted is larger than 5 then the extra packets are backlogged. This number gets added to the next number and further backlog is calculated.
 Number of packets (+backlog from previous) Backlog 6 1 9+1 5 3+5 3 7+3 5 2+5 2 2+2 0 2 0 3 0 4 0 6 1 1+1 0 10 5 7+5 7 5+7 7 8+7 10 3+10 8 6+8 9 2+9 6 9+6 10 5+10 10 Total Backlog 89
Average number of backlogged packets = 89/20 = 4.45 This solution is contributed by Kriti Kushwaha .
 Question 61
Let us consider a statistical time division multiplexing of packets. The number of sources is 10. In a time unit, a source transmits a packet of 1000 bits. The number of sources sending data for the first 20 time units is 6, 9, 3, 7, 2, 2, 2, 3, 4, 6, 1, 10, 7, 5, 8, 3, 6, 2, 9, 5 respectively. The output capacity of multiplexer is 5000 bits per time unit. Then the average number of backlogged of packets per time unit during the given period is
 A 3 B 4.26 C 4.53 D 5.26
Gate IT 2007
Discuss it

Question 61 Explanation:
Average hops for a message to reach to root - (3∗8)+(2∗4)+(1∗2)+(0∗1)15 = 2.267 Where, 3 hops & 8 routers for Bottom-most level and similarly the others Similarly average hops for a message to comes down to leaf- (3∗8)+(2∗4)+(1∗2)+(0∗1)15
{Same as above}
So, Total Hops = 2 * 2.267 = 4.53
 Question 62
A broadcast channel has 10 nodes and total capacity of 10 Mbps. It uses polling for medium access. Once a node finishes transmission, there is a polling delay of 80 μs to poll the next node. Whenever a node is polled, it is allowed to transmit a maximum of 1000 bytes. The maximum throughput of the broadcast channel is
 A 1 Mbps B 100/11 Mbps C 10 Mbps D 100 Mbps
Gate IT 2007
Discuss it

Question 62 Explanation:
Efficiency = transmission time/(transmission time + polling delay time)
Tt =1000 bytes/10Mbps =800μs.
Polling delay is = 80 μs
Efficiency=800/(800+80)= 10/11
Maximum throughput is =(10/11) * 10 Mbps= 100/11 Mbps
 Question 63
Consider a selection of the form σA≤100(r), where r is a relation with 1000 tuples. Assume that the attribute values for A among the tuples are uniformly distributed in the interval [0, 500]. Which one of the following options is the best estimate of the number of tuples returned by the given selection query ?
 A 50 B 100 C 150 D 200
Gate IT 2007
Discuss it

Question 63 Explanation:

Here σA<=100 signifies a selection query which selects all the tuples which has attribute A’s value less than or equal to 100. Attribute A’s values in the range [0,500] are uniformaly distributed among 1000 tuples. So first when we arrange all 1000 tuples in the ascending order of attribute A’s value, then first 200 tuples will have attribute A’s values in the range [0,99] and next 200 tuples will have attribute A’s values in the range [100,199] and so on .So number of tuples returned by the given selection query is 200.

This solution is contributed by Nirmal Bharadwaj.

 Question 64
Consider the following two transactions : T1 and T2. Which of the following schemes, using shared and exclusive locks, satisfy the requirements for strict two phase locking for the above transactions?
 A A B B C C D D
Gate IT 2007
Discuss it

Question 64 Explanation:
Shared locks are used for Read,exclusive locks are used for Write data. one exclusive lock can not take other exclusive lock which is already taken by other schedule as it will lead to deadlock. Requirements to follow Strict 2PL: 1. Exclusive locks should be released after the commit (Releasing exclusive lock after commit restrict the deadlock condition. i.e. we cannot get lock on item were exclusive lock already taken. 2. No Locking can be done after the first Unlock and vice versa. option (A): Incorrect because to write B,S1 needs exclusive lock on B and to write A,S2 needs exclusive Lock on A. that's why it is incorrect. option (B): Incorrect because one exclusive lock cannot take other's Exclusive Lock. here, S1 has taken exclusive lock on item A, S2 has taken exclusive lock on item B so now S1 can't take exclusive lock on item B and S2 can't take exclusive lock on item A. that's why it is incorrect. option (C): Correct as it is following all the three requirement for strict 2PL. Here,schedule S1 releases exclusive lock on B after commit and schedule S2 releases exclusive lock on A after commit.(condition 1 satisfied) option(D): incorrect as according to condition 1,Exclusive locks should be released after the commit. here,schedule S1 releases exclusive lock on B before commit and schedule S2 releases exclusive lock on A before commit. Hence it is incorrect. This solution is contributed by Nitika Bansal .
 Question 65
Consider the following implications relating to functional and multivalued dependencies given below, which may or may not be correct.
i. If A ↠ B and A ↠ C then A → BC
ii. If A → B and A → C then A ↠ BC
iii. If A ↠ BC and A → B then A → C
iv. If A → BC and A → B then A ↠ C
Exactly how many of the above implications are valid?
 A 0 B 1 C 2 D 3
Gate IT 2007
Discuss it

 Question 66
Consider the following relation schemas :
• b-Schema = (b-name, b-city, assets)
• a-Schema = (a-num, b-name, bal)
• d-Schema = (c-name, a-number)
Let branch, account and depositor be respectively instances of the above schemas. Assume that account and depositor relations are much bigger than the branch relation. Consider the following query: Пc-nameb-city = "Agra" ⋀ bal < 0 (branch ⋈ (account ⋈ depositor) Which one of the following queries is the most efficient version of the above query ?
 A Пc-name (σbal < 0 (σb-city = "Agra" branch ⋈ account) ⋈ depositor) B Пc-name (σb-city = "Agra"branch ⋈ (σbal < 0 account ⋈ depositor)) C Пc-name (σb-city = "Agra" branch ⋈ σb-city = "Agra" ⋀ bal < 0 account) ⋈ depositor) D Пc-name (σb-city = "Agra" ⋀ bal < 0 account ⋈ depositor))
Gate IT 2007
Discuss it

Question 66 Explanation:
For better record processing, We should always do select before join to avoid unnecessary tuples being considered for join.(For an SQL query this is not strictly required as DBMS will rearrange the query to make it efficient) and processing a smaller table gives more efficiency than the larger one. option (A): П c-name (σ bal < 0 (σ b-city = "Agra" branch ⋈ account) ⋈ depositor) here we are doing join between relatively smaller table(branch) and larger one(account) and the output that this inner table gives (which is smaller in comparison to joins that we are doing in B) is used for join with depositor table with the selection condition.(same as given query). option (B): П c-name (σ b-city = "Agra" branch ⋈ (σ bal < 0 account ⋈ depositor)) here we are doing a join between two massive table account and depositor with selection condition(for balance less than zero) and the output that this inner table gives is used for join with branch table(relatively smaller table) with the selection condition (for city Agra). (same as given query) so option A and option B both are same as given query but there is difference between record processing as the record processing of option A will get reduced by some rate. (as filtered conditions are applied after the join between one smaller and one larger table which will give relatively smaller table than the join of two larger tables). So, overall option A is much better than option B. option (C): П c-name ((σ b-city = "Agra" branch ⋈ σ b-city = "Agra" depositor) Incorrect as there is no b-city column in a-Schema. option (D): П c-name (σ b-city = "Agra" branch ⋈ (σ b-city = "Agra" depositor)) Incorrect as there is no b-city column in a-Schema. ⋀ bal < 0 account) ⋈ ⋀ bal < 0 account ⋈ Note: don't miss this sentence "account and depositor relations are much bigger than the branch relation" because That makes A the best answer. This solution is contributed by Nitika Bansal.
 Question 67
Consider the following clauses: i. Not inherently suitable for client authentication. ii. Not a state sensitive protocol. iii. Must be operated with more than one server. iv. Suitable for structured message organization. v. May need two ports on the serve side for proper operation. The option that has the maximum number of correct matches is
 A IMAP-(i), FTP-(ii), HTTP-(iii), DNS-(iv), POP3-(v) B FTP-(i), POP3-(ii), SMTP-(iii), HTTP-(iv), IMAP-(v) C POP3-(i), SMTP-(ii), DNS-(iii), IMAP-(iv), HTTP-(v) D SMTP-(i), HTTP-(ii), IMAP-(iii), DNS-(iv), FTP-(v)
Gate IT 2007
Discuss it

Question 67 Explanation:
FTP need to open two ports at server, 1 for control information at 21 and another for data. SMTP- Not suitable for client authentication ,SMTP AUTH an extension is provided for authentication now. HTTP- It doesn’t depend on the state of the device or OS. IMAP- It includes a central server ,hence must have more than one server DNS- Suitable for structured message organization. FTP – needs port 20 and 21 for control and data.   This solution is contributed by Shashank Shanker khare.

 Question 68
Your are given the following four bytes : 10100011            00110111            11101001            10101011 Which of the following are substrings of the base 64 encoding of the above four bytes ?
 A zdp B fpq C qwA D oze
Gate IT 2007
Discuss it

Question 68 Explanation:
refer Base 64 table
 Question 69
Consider the regular expression R = (a + b)* (aa + bb) (a + b)*<br> Which of the following non-deterministic finite automata recognizes the language defined by the regular expression R? Edges labeled λ denote transitions on the empty string.
 A A B B C C D D
Gate IT 2007
Discuss it

Question 69 Explanation:
baa is not accepted by B, so B eliminated<br> in D a is accepted that’s not there in regular expression<br> C accepts extra expressions
 Question 70
Consider the regular expression R = (a + b)* (aa + bb) (a + b)* Which deterministic finite automaton accepts the language represented by the regular expression R ?
 A A B B C C D D
Gate IT 2007
Discuss it

 Question 71
Consider the regular expression R = (a + b)* (aa + bb) (a + b)*<br> Which one of the regular expressions given below defines the same language as defined by the regular expression R?
 A (a(ba)* + b(ab)*)(a + b)+ B (a(ba)* + b(ab)*)*(a + b)* C (a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)* D (a(ba)* (a + bb) + b(ab)*(b + aa))(a + b)+
Gate IT 2007
Discuss it

Question 71 Explanation:
A accepts ab but given does not
B empty may be accepted, not in given
 Question 72
Consider a token ring topology with N stations (numbered 1 to N) running token ring protocol where the stations are equally spaced. When a station gets the token it is allowed to send one frame of fixed size. Ring latency is tp, while the transmission time of a frame is tt. All other latencies can be neglected.
The maximum utilization of the token ring when tt =3 ms, tp = 5 ms, N = 10 is
 A 0.545 B 0.6 C 0.857 D 0.961
Gate IT 2007
Discuss it

Question 72 Explanation:
Maximum efficiency of token ring = (tt)/(tt +( tp/n))
tt= 3 ms
tp =5 ms and n=10,
efficiency = 3/(3+.5)= .857
 Question 73
Consider a token ring topology with N stations (numbered 1 to N) running token ring protocol where the stations are equally spaced. When a station gets the token it is allowed to send one frame of fixed size. Ring latency is tp, while the transmission time of a frame is tt. All other latencies can be neglected.
The maximum utilization of the token ring when tt = 5 ms, tp = 3 ms, N = 15 is :
 A 0.545 B 0.655 C 0.9375 D 0.961
Gate IT 2007
Discuss it

Question 73 Explanation:
Maximum efficiency of token ring = (tt)/(tt +( tp/n)) tt= 5 ms tt =3 ms and n=15, efficiency = (5)/(5+3/15) = 5/5.2 = .961
 Question 74
Consider the sequence <xn>, n>= 0 defined by the recurrence relation xn + 1 = c . xn2- 2, where c > 0. Suppose there exists a non-empty, open interval (a, b) such that for all x0 satisfying a < x0 < b, the sequence converges to a limit. The sequence converges to the value?
 A (1 + (1 + 8c)1/2)/2c B (1 - (1 + 8c)1/2)/2c C 2 D 2/(2c-1)
Gate IT 2007
Discuss it

Question 74 Explanation:
This solution is contributed by Anil Saikrishna Devarasetty.
 Question 75
Consider the following expression
Which of the following Karnaugh Maps correctly represents the expression?

 A A B B C C D D
Gate IT 2007
Discuss it

 Question 76
Consider the following expression
Which of the following expressions does not correspond to the Karnaugh Map obtained for the above expression??
 A c'd'+ ad' + abc' + (ac)'d B (ac)' + c'd' + ad' + abc'd C (ac)' + ad' + abc' + c'd D b'c'd' + acd' + (ac)' + abc'
Gate IT 2007
Discuss it

 Question 77
Let P1, P2,..... , Pn be n points in the xy-plane such that no three of them are collinear. For every pair of points Pi and Pj, let Lij be the line passing through them. Let Lab be the line with the steepest gradient amongst all n(n -1)/2 lines. Which one of the following properties should necessarily be satisfied ?
 A Pa and Pb are adjacent to each other with respect to their x-coordinate B Either Pa or Pb has the largest or the smallest y-coordinate among all the points C The difference between x-coordinatef Pa and Pb is minimum D None of the above
Gate IT 2007
Discuss it

Question 77 Explanation:
This solution is contributed by  Anil Saikrishna Devarasetty.
 Question 78
Let P1,P2,…,Pn be n points in the xy-plane such that no three of them are collinear. For every pair of points Pi and Pj, let Lij be the line passing through them. Let Lab be the line with the steepest gradient among all n(n−1)/2 lines. The time complexity of the best algorithm for finding Pa and Pb is
 A Θ(n) B Θ(nlogn) C Θ(nlogsup>2n) D Θ(n2)
Gate IT 2007
Discuss it

 Question 79
The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at truck number 180. Which of the request sets will cause the head to change its direction after servicing every request assuming that the head does not change direction if there is a tie in SSTF and all the requests arrive before the servicing starts?
 A 11, 139, 170, 178, 181, 184, 201, 265 B 10, 138, 170, 178, 181, 185, 201, 265 C 10, 139, 169, 178, 181, 184, 201, 265 D 10, 138, 170, 178, 181, 185, 200, 265
Gate IT 2007
Discuss it

Question 79 Explanation:
A. 180->181->184 B. 180->181->178->185->170->201->138->265->10 So, B is true
 Question 80
The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at track number 180. What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are 2048 and the head can start from any track?
 A 9 B 10 C 11 D 12
Gate IT 2007
Discuss it

Question 80 Explanation:
Distance of SSTF changing – >
 1 3 7 15 31 63 127 255 511 1023 2047 1 2 3 4 5 6 7 8 9 10 11
Head is changing it's direction after servicing every request. Maximum Cardinality is thus 11  180->181->178->185->170->201->138->265->10
There are 80 questions to complete.

## GATE CS Corner

See Placement Course for placement preparation, GATE Corner for GATE CS Preparation and Quiz Corner for all Quizzes on GeeksQuiz.


text:
Question

# The reminder of $$\displaystyle 2005^{2002}+2002^{2005}$$ when divided by $$200$$ is $$........$$

A
0
B
1
C
2
D
3

Solution

## The correct option is A $$0$$Suppose $$(2005)^{2002}+(2002)^{2005}$$When we divide $$2005$$ by $$200$$ we get remainder as $$\dfrac {5}{200}$$Now, Remainder $$= \dfrac {5}{200} < 1$$and $$($$Remainder$$)^{0}$$ tends to $$0(\because$$ Remainder is small $$)$$Similarly, when we divide $$2002$$ by $$200$$ we getremainder as $$\dfrac {2}{200}$$Again $$($$Remainder$$)^{0}$$ tends to $$0$$.$$\therefore$$ Required answer $$=0$$Mathematics

Suggest Corrections

0

Similar questions
View More

People also searched for
View More

format: plain


text:
# Does ${\rm tr}(\Pi \rho) = 1$ imply $\Pi\rho\Pi=\rho$?

Suppose I have a density matrix $$\rho$$ and an orthogonal projector $$\Pi$$. Is it true that, if $$tr(\Pi \rho) = 1$$ then it must hold that $$\Pi \rho \Pi = \rho$$?

If yes, how can I prove it?

Yes its true. Define another orthogonal projector $$\Pi_\perp$$ such that $$\Pi + \Pi_\perp = I$$ and write $$\rho$$ in terms of a spectral decomposition $$$$\rho = \sum_k \lambda_k(\rho) |\lambda_k\rangle \langle \lambda_k| \tag{1}$$$$
where we're fine to just consider components such that $$\lambda_k(\rho) >0$$. Then we have $$1 = \text{Tr}(\Pi \rho) = \text{Tr}((I - \Pi_\perp) \rho) = 1 - \text{Tr}(\Pi_\perp \rho) \tag{2}$$ implying \begin{align} 0 &= \text{Tr}(\Pi_\perp \rho)\tag{3} \\&= \text{Tr}(\Pi_\perp \rho\Pi_\perp)\tag{4} \\&= \sum_k \lambda_k(\rho)\langle \lambda_k|\Pi_\perp\Pi_\perp |\lambda_k\rangle \tag{5}\\&= \sum_k \lambda_k(\rho) \lVert\Pi_\perp |\lambda_k\rangle \rVert^2\tag{6} \end{align} where line $$(4)$$ used the cyclic property of the trace and $$\Pi_\perp \Pi_\perp = \Pi_\perp$$. Now since $$\lambda_k(\rho) >0$$ and $$\lVert \cdot \lVert \geq 0$$ the above only holds if $$\Pi_\perp |\lambda_k\rangle = 0$$ for all $$k$$. And so \begin{align} \Pi \rho \Pi &= (I - \Pi_\perp) \rho (I - \Pi_\perp)\tag{7} \\&=\rho + \sum_k \lambda_k(\rho) \Bigl(-|\lambda_k\rangle \langle \lambda_k| \Pi_\perp -\Pi_\perp |\lambda_k\rangle \langle \lambda_k| + \Pi_\perp |\lambda_k\rangle \langle \lambda_k| \Pi_\perp\Bigr)\tag{8} \\&= \rho \tag{9} \end{align}
Write the eigendecomposition of the state as $$\rho=\sum_k p_k u_k u_k^\dagger$$, where $$\{u_k\}_k$$ is a family of orthonormal vectors in the underlying space.
Suppose there is some $$u_k\notin \operatorname{supp}(\Pi)$$, that is, some $$u_k$$ such that $$\Pi u_k\neq u_k$$. Then $$\operatorname{Tr}(\Pi u_k u_k^\dagger)=\| \Pi u_k\|^2<\|u_k\|^2=1,$$ and thus $$\operatorname{Tr}(\Pi\rho)=\sum_k p_k \operatorname{Tr}(\Pi u_k u_k^\dagger)< \sum_k p_k=1.$$ It follows that if $$\operatorname{Tr}(\Pi\rho)=1$$, each $$u_k$$ must be in the support of $$\Pi$$, and thus $$\Pi\rho\Pi=\rho$$.


text:
# How does an op amp integrator work?

I know there are at least two questions related to this on stackoverflow but neither really answer my question, and in any case, both questions got downvoted. What I am after is an operational understanding of how an op-amp integrator works. I know how a simple RC circuit can integrate, what I don't understand is how the feedback loop in an op-amp configuration helps. I understand how feedback works in a noninverting amplifier. I took the figure below from www.electronics-tutorials.ws. This web site has an explanation but I don't follow it. My understanding so far is this:

1. Apply a positive voltage to input vin. Current flows through Rin resulting initially in a non-zero voltage at X (Correct?).

2. Due to the high impedance of the op-amp at X, we can assume that all the current then flows to the capacitor (initial discharged).

3. The capacitor starts to charge resulting in a voltage across the capacitor.

4. The difference in voltage at the two op-amp inputs (the positive input is at zero, hence the difference is negative) resulting in the output, vout, going negative (we assume that vout was zero initially).

My question is what happens next? How does the feedback act to bring the difference between the two inputs back to zero? Or have I got this wrong?

I am very familiar with the proofs for showing that the configuration will integrate but they don't give any real intuition and many videos, wikpedia, and books but almost all regurgitate the proof without giving much insight. I'm after an intuitive understanding, not a mathematical proof.

Out of interest I also redrew the op-amp circuit next to the RC integrator shown below which gives the suggestion that the op-amp is amplifying the small vollage across C (assuming high R1) while having high impedance from the resistor/capacitor node. Not sure if that is a legitimate way to look at it.

• Put in a square wave, the opamp strives to hold the (-) pin very close to zero volts, which imposes a constant voltage across the input resistor. This constant current has to go somewhere, and the only path is into the capacitor. Give constant current into a capacitor, you get a perfect RAMP output, which is the integral. Jan 18 '19 at 3:04
• To me - this small comment (if compared with all the answers) is the best explanation of the circuits behaviour in the time domain.
– LvW
Jan 18 '19 at 14:57
• But it doesn't explain why the op-amp strives to hold the (-) pin close to zero. An op-amp on its own won't do that, it's the combination with the feedback that makes that happen. This is the bit I wasn't sure about. Jan 18 '19 at 18:47
• The RC integrator is not a real integrator. It can be treated as one in a limited sense. But consider a charged capacitor and an input voltage of 0 V. According to how integrations work, the integral should not change. However, in this case the capacitor discharges => Your integral value goes to 0. This can also be seen in the Laplace transform of the two circuits: An integrator: H(s) = constant * 1/s. Your RC-circuit (essentially a lowpass): H(s) = constant * 1 / (1+RC * s). For high frequencies (!) 1 + RC * s can be assumed as the same as RC* s. In this case it is acting as an integrator
– GNA
May 27 '20 at 6:52

This may help:

• Remember that when current flows into the RC junction of your op-amp that the voltage at that point will tend to rise.
• If the inverting input voltage rises the slightest bit above the non-inverting input voltage then the op-amp output will start to swing negative.
• The output swinging negative will, through the capacitor1, tend to pull the inverting input down towards zero again where it stabilise (for the moment).

The result is that feeding current into the RC node causes the op-amp output to go negative.

Out of interest I also redrew the op-amp circuit next to the RC integrator shown below which gives the suggestion that the op-amp is amplifying the small voltage across C (assuming high R1) while having high impedance from the resistor/capacitor node. Not sure if that is a legitimate way to look at it.

That's correct. It might be better than you think. The simple RC circuit has the advantage that it's non-inverting but the disadvantage that it's non-linear. With a constant input voltage the output will be an exponential charge curve.

Putting the op-amp in as you have shown still allows the capacitor to charge up but maintains the top terminal at virtual ground. The advantage is a linear change in output. The disadvantage is that there is a minus sign on the integral obtained.

1 You can think of a capacitor as holding the voltage across it as a constant in the short term. That means that if the voltage on one side is changed the voltage on the other side will try to change by the same amount.

One question. what is the orientation of the capacitor in terms of conventional current? i.e. if vin goes positive the capacitor is I assume negative on its right-hand side (nearest vout). Now vout goes negative and therefore reduces the voltage across the capacitor until the potential at X is zero?

I think your understanding is correct.

If Vin goes positive then current flows into the X node charging up C. (Remember the op-amp's voltage hasn't changed yet.) This tends to increase the voltage on the inverting input and that causes the output voltage to decrease. This draws some charge from the right hand side of C. Now the inverting input is pulled back down to zero volts but there is charge on C so there is a voltage across it. Since the conventional current flowed to the right there is a negative voltage remaining on the capacitor.

• I think this the kind of answer I was looking for. One question. what is the orientation of the capacitor in terms of conventional current? ie if vin goes positive the capacitor is I assume negative on its right-hand side (nearest vout). Now vout goes negative and therefore reduces the voltage across the capacitor until the potential at X is zero? Jan 17 '19 at 22:44
• See the update. Jan 17 '19 at 23:15

The op-amp is going to try its best to keep the voltage between it's plus and minus input the same. In an ideal op-amp, no current flows into the inputs, so the only way that it can do that is by changing its output voltage.

In the schematic below, $$\v_+ = 0\mathrm{V}\$$. That means that the op-amp will try to hold $$\v_-\$$ at zero, also.

Whatever voltage is generated by V2 gets turned into a current by R1. Because $$\v_-\$$ is being held at $$\0\mathrm{V}\$$, that same current has to flow in C1. And because $$\v_-\$$ is being held at $$\0\mathrm{V}\$$, the op-amp has to drive the output voltage such that the current in C1 matches the current in R1.

So if $$\v_2\$$ is constant, then the current into the node around the negative input is constant, which means that the current out of that node from the cap must be constant -- and that can only happen if the output voltage is falling at a constant rate. The end result is that the op-amp integrates the input voltage into the output voltage.

More complicated voltages at $$\v_2\$$ cause more complicated behavior, but the op-amp is always going to be trying to drive $$\v_-\$$ to $$\0\mathrm{V}\$$. It can only do that by satisfying $$\ \frac{d}{dt} C_1 v_{out} + \frac{v_2}{R_1} = 0 \$$. If you solve that differential equation, it says that $$v_{out} = -\frac{1}{R_1 C_1} \int v_2 dt$$

HTH

simulate this circuit – Schematic created using CircuitLab

• In your comment "The op-amp is going to try its best to keep the voltage between it's plus and minus input the same.", strictly speaking, it's the op-amp combined with the next feedback that does this. This is the bit I was stuck on, how the feedback coupled with the op-amp manages to maintain the difference close to zero. Jan 18 '19 at 18:50
• Well, I'm glad you worked through it! These are difficult concepts and hard to simplify. Jan 18 '19 at 18:57

Rhody - have you heard about the MILLER effect? Well - the shown circuit is called "MILLER integrator" because the MILLER effect is exploited. Remember: This effect reduces the feedback impedance between an amplifier output (for example: collector) and the inverting input (example: base node of the transistor). And the factor of increase is the gain.

Here, we have the same principle. Hence, there will be a very small capacitive impedance (that means: A very large capacitor) between input and output of the opamp. And the factor of increase is the open-loop gain Aol of the opamp.

Hence, you can make a comparison with a simple RC circuit. However, because of the very large capacitor the cut-off frequency is very low (nearly DC).

Frequency domain: The transfer function between the opamps inverting node and the signal input is

Ho(s)=1/(1+sCo * R) with Co=Aol * C (MILLER effect).

Because of the very large value Aol, we can neglect the "1" in the denominator and arrive at

Ho(s)=1/(sC * Aol *R)

We are lucky and can use the low resistive opamp output (and multiply the function Ho(s) with the gain -Aol) and arrive at the final result (opamp output-to-signal input):

H(s)=Ho(s) * (-Aol) = - 1/sR*C (Transfer function of an ideal integrator)

The inputs of the opamp don't take input current and the opamp will keep its input voltage equal as long as it is wired for negative feedback.

So effectively, the current that the input sinks against the 0V it sees goes straight into charging the capacitor. Usually when you charge a capacitor through a resistor, the charge building up on the capacitor reduces the voltage across the resistor and thus also the charging current, leading to an exponential decay of the charge current.

Here, however, the opamp output actively adjusts the voltage at the other side of the capacitor so that the resistor never gets to see the difference it makes, thus keeping the current through resistor (and into capacitor) independent from the charge across the capacitor.

It's like Útgarða-Loki handing Þorr the mouth of the ocean as a drinking horn and Þorr does not actually find himself able to drain it, not noticing that he causes the tides with his attempt.

The Passive cap. integrator current decays with voltage as it approaches the input.

The active cap. integrator saturates after some time if Vin ≠ 0 because the output voltage drives current into Vin- to maintain 0V diff. until the output saturates at the supply rail.

So input offset is critical and you need an analog switch to discharge and initialize to 0V output.

## anecdotal

I remember knowing nothing about this in 1st yr Eng and my once famous brother-in-law medical Dr of Anesthesia, Intensive Care and open heart surgery, gave me a tour around the hospital and said he needed an integrator to measure O2 content in blood for the brain, after a heart attack victim stops, to know the best treatment ( such as hypothermia )to give when no response to defib. and meds with the likelihood of success. I had no idea ! and was embarrassed to not know! (circa '75) Don't be. Just research it.

It is a great challenge to find a new explanation for such a legendary circuit because everyone knows what an op-amp integrator is. But to know a specific circuit solution does not mean that you really understand it. To (deeply) understand a circuit means something more - to see the general idea behind it that links many specific circuit implementations (op-amp, BJT, FET, tube…) You can see it even in life in the form of many non-electrical applications...

1. Op-amp inverting integrator. The idea behind this circuit solution is extremely simple and intuitive. It may sound paradoxical... but to see it you only need to remove the symbol of the ground from the circuit diagram. As you can see in Fig. 1, I have only labeled the place of the virtual ground (1) and the place of the real ground (2)... and I have no longer used these names. You understand that there is no virtual ground because there is no real ground. But if you still miss the virtual ground, then you can talk about a virtual short between node 1 and 2.

Fig. 1. Op-amp inverting integrator (only the negative power supply V- is explicitly shown)

The current path is crucial here to see the great idea. Since the input voltage is positive, the op-amp output voltage is negative and the current enters the op-amp output... then passes through the negative power supply V- and returns to the input source. The positive source V+ is not essential in this case; so it is only hinted.

2. Electric equivalent circuit. The main question to be answered is, "What does the op-amp do here?" You know that it keeps almost zero voltage between its inputs so its output voltage is always equal to the voltage drop across the capacitor. So the op-amp output serves as a following voltage source. Then let's replace the op-amp with a variable voltage source VOA to simplify this electronic circuit - Fig. 2. By the way, I conducted such a real experiment in 2001 with my students in the laboratory when we used a capacitor with high capacity and zero indicator connected between 1 and 2.

Fig. 2. Electric equivalent circuit

This simple trick is enough to show the great idea behind the circuit. The voltage source VOA is connected in series to the capacitor C so that its voltage compensates the voltage drop VC across the capacitor and the voltage between the two nodes 1 and 2 is (almost) zero. So the conclusion is:

The op-amp in the circuit of the inverting amplifier compensates the voltage drop VC across the capacitor by adding equivalent voltage VOA = VC in series.

So, the key point of this explanation is adding, not amplifying. To think of the amplifier in a negative feedback circuit not as of an amplifier but rather as of something like integrator is a powerful technique for intuitive understanding and explaining such op-amp circuits. Indeed, here it seems a little strange (integrator inside integrator)... but works...

How simple is this "magic recipe"... You want to make the imperfect RC integrator perfect? Then connect a small variable "battery" with voltage VC in series to the capacitor and (the next brilliant idea) take its inverted "copy" voltage as an output. The load will consume current from this "helping" source... not from the input source (i.e., this is a buffered output).

The power of this intuitive explanation is that we can explain this sophisticated op-amp circuit to a "six year old" (Einstein)... and that will mean we understand it ourselves...

3. Virtual short. The total voltage across the network of two elements in series - a capacitor C and compensating voltage source (VOUT), is always zero. So this network behaves as a "piece of wire" that shorts the points 1 and 2 - Fig. 3. This is what the input source "sees" when "looking" through the resistor R at the op-amp input.

Fig. 3. Equivalent circuit of the output part on the right

Figuratively speaking, the op-amp output acts as a "negative capacitor". While the "positive capacitor" C subtracts its voltage VC from the input voltage source, the op-amp "negative capacitor" adds its voltage VOUT to the input voltage.


text:
## Tag: geometric-langlands

48 Double affine Hecke algebras and mainstream mathematics 2009-11-23T02:55:33.280

36 Consequences of Geometric Langlands 2009-11-05T00:46:39.290

31 Topological Langlands? 2009-11-30T15:32:20.337

27 Current Status on Langlands Program 2014-03-29T20:22:29.667

27 Number theory and physics 2015-11-22T18:35:34.153

18 A good example of a curve for geometric Langlands 2009-12-16T11:49:50.607

17 What do Hecke eigensheaves actually look like? 2016-04-20T06:58:16.457

15 LMS Lectures on Geometric Langlands 2017-11-01T15:08:45.417

15 References for Langlands classification 2017-11-02T13:38:52.960

13 Langlands duality and multiplying cocharacters 2014-11-20T14:15:46.953

12 Langlands Dual Groups 2009-10-22T23:03:48.550

12 What is Eisenstein series? 2009-10-25T21:26:23.163

12 Vector bundles, Higgs bundles and the Langlands program 2014-07-14T11:10:10.030

11 ubiquitous quantum cohomology 2009-10-24T09:32:23.863

11 Meaning of topological tensor products in Frenkel-Gaitsgory 2016-03-09T21:46:26.310

10 The affine Grassmannian and the Bogomolny equations 2011-05-06T19:58:34.820

10 Examples of Eigensheaves outside of langlands 2012-06-29T15:26:01.463

9 Why is the simple trace formula a weaker tool than the Arthur trace formula? 2011-04-24T12:14:37.717

9 Geometric Satake and Restriction 2016-03-29T05:49:52.970

8 What is an Oper? 2009-10-25T19:39:51.050

8 On Geometric Langlands Correspondence 2013-05-09T10:47:47.333

7 Explanation for Satake correspondence 2009-11-08T13:32:33.167

7 A question on group action on categories 2010-04-01T16:27:20.003

7 The De Rham Stack and $\text{LocSys}$ 2012-06-02T04:26:47.583

7 Homological contractibility of a prestack 2016-03-15T04:11:07.063

6 Any progress on Strominger-Yau and Zaslow conjecture? 2017-05-12T21:58:04.293

6 Global Langlands function fields 2017-08-15T18:32:03.437

6 Bi-Whittaker functions and local Langlands compatibility 2017-11-27T23:59:07.647

5 Sheaves on Bun_G 2009-10-25T21:34:02.943

5 Real representations of G = those of Langlands dual and maps of a cylinder 2009-11-05T20:15:49.430

5 Fiber functor of category of D-module on affine Grassmannian. 2010-04-26T08:51:00.497

5 Why is the Arthur trace formula so powerful? 2011-04-25T20:54:26.190

5 What are local spaces and what are they good for? 2016-01-18T02:47:50.763

4 Reverse Langlands transform 2009-10-25T21:46:12.640

4 Feigin-Frenkel centre and opers for reductive Lie algebras 2017-01-13T00:00:28.970

3 Arthur's refinement of parameters for unitary automorphic representations 2014-08-23T06:29:13.423

2 Understanding formula in Frenkel-Witten 2009-11-18T22:19:45.947

2 Opers, connections 2011-05-24T05:29:36.483

2 Orbit stratification of semi infinite flag manifold? 2011-12-02T02:13:50.160

2 Local counterpart of the NON-Hitchin Hecke eigen-sheaves ? 2012-02-06T06:57:44.940

2 Complex Finite Dimensional Representation of GL(N,C) 2012-11-20T19:49:31.140

2 Langlands correspondence for reducible representations 2013-06-07T06:52:50.323

1 Symmetric and Exterior products of sl(n,C)-module 2012-11-16T23:26:06.223

1 Twists in "Eisenstein property" in Geometric Langlands 2013-09-20T15:23:33.280

1 A question related to the semisimplification of a Weil-Deligne representation 2016-04-28T18:39:52.747

0 Reference on Casselman-Shalika formula for GL(n) and PGL(n)? 2012-11-26T20:14:20.207


text:
## 33.21 Complete local rings

Some results on complete local rings of schemes over fields.

Lemma 33.21.1. Let $k$ be a field. Let $X$ be a locally Noetherian scheme over $k$. Let $x \in X$ be a point with residue field $\kappa$. There is an isomorphism

33.21.1.1
$$\label{varieties-equation-complete-local-ring} \kappa [[x_1, \ldots , x_ n]]/I \longrightarrow \mathcal{O}_{X, x}^\wedge$$

inducing the identity on residue fields. In general we cannot choose (33.21.1.1) to be a $k$-algebra isomorphism. However, if the extension $\kappa /k$ is separable, then we can choose (33.21.1.1) to be an isomorphism of $k$-algebras.

Proof. The existence of the isomorphism is an immediate consequence of the Cohen structure theorem1 (Algebra, Theorem 10.160.8).

Let $p$ be an odd prime number, let $k = \mathbf{F}_ p(t)$, and $A = k[x, y]/(y^2 + x^ p - t)$. Then the completion $A^\wedge$ of $A$ in the maximal ideal $\mathfrak m = (y)$ is isomorphic to $k(t^{1/p})[[z]]$ as a ring but not as a $k$-algebra. The reason is that $A^\wedge$ does not contain an element whose $p$th power is $t$ (as the reader can see by computing modulo $y^2$). This also shows that any isomorphism (33.21.1.1) cannot be a $k$-algebra isomorphism.

If $\kappa /k$ is separable, then there is a $k$-algebra homomorphism $\kappa \to \mathcal{O}_{X, x}^\wedge$ inducing the identity on residue fields by More on Algebra, Lemma 15.38.3. Let $f_1, \ldots , f_ n \in \mathfrak m_ x$ be generators. Consider the map

$\kappa [[x_1, \ldots , x_ n]] \longrightarrow \mathcal{O}_{X, x}^\wedge ,\quad x_ i \longmapsto f_ i$

Since both sides are $(x_1, \ldots , x_ n)$-adically complete (the right hand side by Algebra, Lemmas 10.96.3) this map is surjective by Algebra, Lemma 10.96.1 as it is surjective modulo $(x_1, \ldots , x_ n)$ by construction. $\square$

Lemma 33.21.2. Let $K/k$ be an extension of fields. Let $X$ be a locally algebraic $k$-scheme. Set $Y = X_ K$. Let $y \in Y$ be a point with image $x \in X$. Assume that $\dim (\mathcal{O}_{X, x}) = \dim (\mathcal{O}_{Y, y})$ and that $\kappa (x)/k$ is separable. Choose an isomorphism

$\kappa (x)[[x_1, \ldots , x_ n]]/(g_1, \ldots , g_ m) \longrightarrow \mathcal{O}_{X, x}^\wedge$

of $k$-algebras as in (33.21.1.1). Then we have an isomorphism

$\kappa (y)[[x_1, \ldots , x_ n]]/(g_1, \ldots , g_ m) \longrightarrow \mathcal{O}_{Y, y}^\wedge$

of $K$-algebras as in (33.21.1.1). Here we use $\kappa (x) \to \kappa (y)$ to view $g_ j$ as a power series over $\kappa (y)$.

Proof. The local ring map $\mathcal{O}_{X, x} \to \mathcal{O}_{Y, y}$ induces a local ring map $\mathcal{O}_{X, x}^\wedge \to \mathcal{O}_{Y, y}^\wedge$. The induced map

$\kappa (x) \to \kappa (x)[[x_1, \ldots , x_ n]]/(g_1, \ldots , g_ m) \to \mathcal{O}_{X, x}^\wedge \to \mathcal{O}_{Y, y}^\wedge$

composed with the projection to $\kappa (y)$ is the canonical homomorphism $\kappa (x) \to \kappa (y)$. By Lemma 33.5.1 the residue field $\kappa (y)$ is a localization of $\kappa (x) \otimes _ k K$ at the kernel $\mathfrak p_0$ of $\kappa (x) \otimes _ k K \to \kappa (y)$. On the other hand, by Lemma 33.5.3 the local ring $(\kappa (x) \otimes _ k K)_{\mathfrak p_0}$ is equal to $\kappa (y)$. Hence the map

$\kappa (x) \otimes _ k K \to \mathcal{O}_{Y, y}^\wedge$

factors canonically through $\kappa (y)$. We obtain a commutative diagram

$\xymatrix{ \kappa (y) \ar[rr] & & \mathcal{O}_{Y, y}^\wedge \\ \kappa (x) \ar[r] \ar[u] & \kappa (x)[[x_1, \ldots , x_ n]]/(g_1, \ldots , g_ m) \ar[r] & \mathcal{O}_{X, x}^\wedge \ar[u] }$

Let $f_ i \in \mathfrak m_ x^\wedge \subset \mathcal{O}_{X, x}^\wedge$ be the image of $x_ i$. Observe that $\mathfrak m_ x^\wedge = (f_1, \ldots , f_ n)$ as the map is surjective. Consider the map

$\kappa (y)[[x_1, \ldots , x_ n]] \longrightarrow \mathcal{O}_{Y, y}^\wedge ,\quad x_ i \longmapsto f_ i$

where here $f_ i$ really means the image of $f_ i$ in $\mathfrak m_ y^\wedge$. Since $\mathfrak m_ x \mathcal{O}_{Y, y} = \mathfrak m_ y$ by Lemma 33.5.3 we see that the right hand side is complete with respect to $(x_1, \ldots , x_ n)$ (use Algebra, Lemma 10.96.3 to see that it is a complete local ring). Since both sides are $(x_1, \ldots , x_ n)$-adically complete our map is surjective by Algebra, Lemma 10.96.1 as it is surjective modulo $(x_1, \ldots , x_ n)$. Of course the power series $g_1, \ldots , g_ m$ are mapped to zero under this map, as they already map to zero in $\mathcal{O}_{X, x}^\wedge$. Thus we have the commutative diagram

$\xymatrix{ \kappa (y)[[x_1, \ldots , x_ n]]/(g_1, \ldots , g_ m) \ar[r] & \mathcal{O}_{Y, y}^\wedge \\ \kappa (x)[[x_1, \ldots , x_ n]]/(g_1, \ldots , g_ m) \ar[r] \ar[u] & \mathcal{O}_{X, x}^\wedge \ar[u] }$

We still need to show that the top horizontal arrow is an isomorphism. We already know that it is surjective. We know that $\mathcal{O}_{X, x} \to \mathcal{O}_{Y, y}$ is flat (Lemma 33.5.1), which implies that $\mathcal{O}_{X, x}^\wedge \to \mathcal{O}_{Y, y}^\wedge$ is flat (More on Algebra, Lemma 15.43.8). Thus we may apply Algebra, Lemma 10.99.1 with $R = \kappa (x)[[x_1, \ldots , x_ n]]/(g_1, \ldots , g_ m)$, with $S = \kappa (y)[[x_1, \ldots , x_ n]]/(g_1, \ldots , g_ m)$, with $M = \mathcal{O}_{Y, y}^\wedge$, and with $N = S$ to conclude that the map is injective. $\square$

[1] Note that if $\kappa$ has characteristic $p$, then the theorem just says we get a surjection $\Lambda [[x_1, \ldots , x_ n]] \to \mathcal{O}_{X, x}^\wedge$ where $\Lambda$ is a Cohen ring for $\kappa$. But of course in this case the map factors through $\Lambda /p\Lambda [[x_1, \ldots , x_ n]]$ and $\Lambda /p\Lambda = \kappa$.

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
💬 👋 We’re always here. Join our Discord to connect with other students 24/7, any time, night or day.Join Here!

SB

Determine whether the lines $L_1$ and $L_2$ are parallel, skew, or intersecting. If they intersect, find the point of intersection.$L_1 : x = 3 + 2t , y = 4 - t , z = 1 + 3t$$L_2 : x = 1 + 4s , y = 3 - 2s , z = 4 + 5s$

Skew

Vectors

Discussion

You must be signed in to discuss.
Anna Marie V.

Campbell University

Heather Z.

Oregon State University

Kayleah T.

Harvey Mudd College

Michael J.

Idaho State University

Lectures

Join Bootcamp

Video Transcript

according to the question we have to determine whether the lions, L one and L two R parallels Q. Or intersecting If the intersect, find the point of intersection, The given lines are L one has the direction coordinates as X equal to tripolis duty by equal to four minus T. Is equal to one plus three. T. And L two is equal to X is equal to one plus forest. Why equal to three minus tourists. And that equal to four plus five is So according to the criteria they're asking to search. That is whether these lines are parallel or not. So these lines has coefficients off the unknowns. That is given in each of the coordinates. If we find the ratio of each of the coordinates for each of the lines then if they are all equal then only these two lines are parallel to each other so gradually one is checking for L one and L two are Caroline two. Each other are not. Yeah. So the coefficients of each of the coordinates and the rest of the two lines are two by four is equal to minus one x -2 equal to three x 5. These numbers are taken from the coordinates of each of the lines. That is so coordinate of the X coordinate and coefficient of the first lane and this is the coefficient of the X. Coordinate of the 2nd Line. Yeah. In this way all the coordinates are put in ratio form to find whether these lines are in same direction to each other or not. Okay, so if we calculate this then it will Simplify as one x 2 equal to one x 2 equal to three x 5. Since she verified is not equal to one x 2. Therefore L one and L two R not parallel to each other. Okay now we'll take the second criteria. That is my book whether L one and L two are intersecting or not. Mhm. Okay. Yeah. Mhm. So in order to check this we have to equip all the coordinates of borderlines that is you have to equipped X one equal to X two. Why one equal to Y two and okay that one equal to that too. Therefore if we substitute any particular value in other equations and if it satisfies the equation then we can say that these to answer intersecting to each other. Otherwise it will not intersect. So the equations are three Plus to be equal to one plus for us or minus T is equal to 3- to us and Yeah. Okay one plus three D. Is equal to four plus virus. So from equation one we can find the value of T. That is to t is equal to one minus three plus four. S that is two days equal to For S -2 or T is equal to The West -1. Okay. Yeah. Yeah. Yeah I'm putting this value of t. Any question. Do we get? Okay. Mhm. Yeah. Yeah. Yeah. What? Yeah. Immigration. Do we know that four minus T Is equal to 3- to us. Therefore if you substitute the value of teeth from equation for that is physical too. Mhm two is -1. In this equation. We get that four minus two. Waste minus one is equal to three minus to us. Yeah. Therefore 4 -2 s Plus one is equal to 3 -2. Is or We can check that -2 s. is comin from both sides so they will cancel each other and the equation becomes five equal to three or To equal to zero which is not true. Therefore L. one and L. two. Oh not intersecting also. Okay. Yeah. Yeah The 3rd criteria is to check. Yeah. Mhm. If L one and L two R Schiewe lines mm Therefore as L one and L two are not parallel or not intersecting yeah to each other that being said. Therefore L one and L two lines. I skew lines listen and since L one and L two lines are not intersecting so we cannot find the intersecting points off L. one and L two. Mhm. As they are skew lines. So of course this is the required answer

Topics

Vectors

Anna Marie V.

Campbell University

Heather Z.

Oregon State University

Kayleah T.

Harvey Mudd College

Michael J.

Idaho State University

Lectures

Join Bootcamp