-
1.
Statement for Linked Answer Questions :
[1] Which one of the following grammars generates the language L = {aibj | i≠j}
[2 marks]
[2] In the correct grammar above, what is the length of the derivation (number of steps starring from S) to generate the string labm with l ≠ m? [2 marks]
(A) max (l,m) + 2
(B) l + m + 2
(C) l + m + 3
(D) max (l,m) + 3asked in Computer Science And Engineering, 2006
View Comments [0 Reply]
-
2.
Consider the diagram shown below where a number of LANs are connected by (transparent) bridges. In order to avoid packets looping through circuits in the graph, the bridges organize themselves in a spanning tree. First, the root bridge is identified as the bridge with the least serial number. Next, the root sends out (one or more) data units to enable the setting up of the spanning tree of shortest paths from the root bridge to each bridge.
Each bridge identifies a port (the root port) through which it will forward frames to the root bridge. Port conflicts are always resolved in favour of the port with the lower index value. When there is a possibility of multiple bridges forwarding to the same LAN (but not through the root port), ties are broken as follows: bridges closest to the root get preference and between such bridges, the one with the lowest serial number is
preferred.
[1] For the given connection of LANs by bridges, which one of the following choices represents the depth first traversal of the spanning tree of bridges? [2 marks]
(A) B1, B5, B3, B4, B2
(B) B1, B3, B5, B2, B4
(C) B1, B5, B2, B3, B4
(D) B1, B3, B4, B5, B2[2] Consider the correct spanning tree for the previous question. Let host H1 send out a broadcast ping packet. Which of the following options represents the correct forwarding table on B3?[2 marks]
(A)Hosts Port H1, H2, H3, H4 3 H5, H6, H9, H10 1 H7, H8, H11, H12 2
(B)Hosts Port H1, H2 4 H3, H4 3 H5, H6 1 H7, H8, H9, H10,H11,H12 2
(C)Hosts Port H3, H4 3 H5, H6, H9, H10 1 H1, H2 4 H7, H8, H11, H12 2
(D)Hosts Port H1, H2, H3, H4 3 H5, H7, H9, H10 1 H7, H8, H11, H12 4 last reply by CpjJwWHV • 13 years ago • asked in Computer Science And Engineering, 2006
View Comments [1 Reply]
-
3.
A CPU has a 32 KB direct mapped cache with 128-byte block size. Suppose A is a twodimensional array of size 512×512 with elements that occupy 8-bytes each. Consider the following two C code segments, P1 and P2.
P1: for (i=0; i<512; i++) {
for (j=0; j<512; j++) {
x +=A[i] [j];
}
}
P2: for (i=0; i<512; i++) {
for (j=0; j<512; j++) {
x +=A[j] [i];
}
}
P1 and P2 are executed independently with the same initial state, namely, the array A is not in the cache and i, j, x are in registers. Let the number of cache misses experienced by P1 be M1 and that for P2 be M2 .
[1] The value of M1 is: [2 marks]
(A) 0
(B) 2048
(C) 16384
(D) 262144[2] The value of the ratio M1/M2 is : [2 marks]
(A) 0
(B) 1/16
(C) 1/8
(D) 16
asked in Computer Science And Engineering, 2006
View Comments [0 Reply]
-
4.
Statement for Linked Answer Questions ::
Barrier is a synchronization construct where a set of processes synchronizes globally i.e. each process in the set arrives at the barrier and waits for all others to arrive and then all processes leave the barrier. Let the number of processes in the set be three and S be a binary semaphore with the usual P and V functions. Consider the following C implementation of a barrier with line numbers shown on left.
void barrier (void) {
1: P(S);
2: process_arrived++;
3. V(S);
4: while (process_arrived !=3);
5: P(S);
6: process_left++;
7: if (process_left==3) {
8: process_arrived = 0;
9: process_left = 0;
10: }
11: V(S);
}
The variables process_arrived and process_left are shared among all processes and are initialized to zero. In a concurrent program all the three processes call the barrier function when they need to synchronize globally.
[1] The above implementation of barrier is incorrect. Which one of the following is true?
[2 marks]
(A) The barrier implementation is wrong due to the use of binary semaphore S
(B) The barrier implementation may lead to a deadlock if two barrier in invocations are used in immediate succession.
(C) Lines 6 to 10 need not be inside a critical section
(D) The barrier implementation is correct if there are only two processes instead of three.[2] Which one of the following rectifies the problem in the implementation? [2 marks]
(A) Lines 6 to 10 are simply replaced by process_arrived
(B) At the beginning of the barrier the first process to enter the barrier waits until process_arrived becomes zero before proceeding to execute P(S).
(C) Context switch is disabled at the beginning of the barrier and re-enabled at the end.
(D) The variable process_left is made private instead of sharedasked in Computer Science And Engineering, 2006
View Comments [0 Reply]
-
5.
Statement for Linked Answer Questions ::
A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.[1] Which one of the following is a valid sequence of elements in an array representing 3-ary max heap? [2 marks]
(A) 1, 3, 5, 6, 8, 9
(B) 9, 6, 3, 1, 8, 5
(C) 9, 3, 6, 8, 5, 1
(D) 9, 5, 6, 8, 3, 1[2] Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question. Which one of the following is the sequence of items in the array representing the resultant heap? [2 marks]
(A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(B) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(C) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5asked in Computer Science And Engineering, 2006
View Comments [0 Reply]
-
6.
Consider two cache organizations: The first one is 32 KB 2-way set associative with 32- byte block size. The second one is of the same size but direct mapped. The size of an address is 32 bits in both cases. A 2-to-1 multiplexer has a latency of 0.6 ns while a k-bit comparator has a latency of k 10 ns. The hit latency of the set associative organization is h1 while that of the direct mapped one is h2 .
[1] The value of h1 is: [2 marks]
(A) 2.4 ns
(B) 2.3 ns
(C) 1.8 ns
(D) 1.7 ns[2] The value of h2 is: [2 marks]
(A) 2.4 ns
(B) 2.3 ns
(C) 1.8 ns
(D) 1.7 ns
asked in Computer Science And Engineering, 2006
View Comments [0 Reply]