Q: Consider the following C program. #include void mystery(int *ptra, int *ptrb) { int *temp; temp = ptrb; ptrb = ptra; ptra = temp; } int main() { int a=2016, b=0, c=4, d=42; mystery(&a, &b); if (a < c) mystery(&c, &a); mystery(&a, &d); printf("%d ", a); } The output of

42. The function 'mystery' swaps the pointers but does not affect the values of the variables they point to. After the calls to 'mystery', the value of 'a' is ultimately set to the value of 'd', which is 42, making that the final output.

Q: Which of the following languages is generated by the given grammar? S → aS | bS | ε

{a,b}*. The grammar allows for any combination of 'a' and 'b' by recursively adding 'a' or 'b' to the string, including the empty string, which means it can generate all possible strings made up of 'a' and 'b'.

Q: Which of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = Φ? II. Given a CFG G = (N, Σ, P, S) and a string x ∈ Σ*, does x ∈ L(G)? III. Given CFGs G1 and G2, is L(G1) = L(G2)? IV. Given a TM M, is L(M) = Φ?

III and IV only. Options III and IV are correct because determining if two context-free grammars generate the same language (III) and whether the language of a Turing machine is empty (IV) are both undecidable problems, meaning there is no algorithm that can solve them for all possible inputs.

Q: Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

(0 + 1)*(00(0 + 1)*11 + 11(0 + 1)*00)(0 + 1)*. The correct option captures the requirement for the presence of both '00' and '11' in any order within the binary strings, allowing for any characters before or after these patterns. This ensures that the strings can contain any combination of 0s and 1s while still meeting the criteria of having two consecutive 0s and two consecutive 1s.

Q: Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

Shortest remaining time first. Shortest remaining time first (SRTF) minimizes the average waiting time by always selecting the process with the least remaining CPU burst time, allowing shorter processes to complete quickly and reducing the waiting time for subsequent processes.

Question 1

We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is

Accepted Answer

3. The sequence 0-1-0-2-0-3 has six steps and the three occurrences of 0 are different states (they lead to different next outputs 1,2,3), so the counter needs 6 distinct states. Six states require ceil(log2 6)=3 flip-flops, so 3 J-K flip-flops are needed (index 2).

Question 2

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

Accepted Answer

Both operations can be performed in O(1) time. Both ENQUEUE and DEQUEUE operations can be implemented to run in O(1) time by using a circular array approach, which allows efficient addition and removal of elements without needing to shift other elements.

Question 3

Consider the following C program.

void f(int, short);
void main()
{
 int i = 100;
 short s = 12;
 short *p = &s;
 ________; // call to f()
}

Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?

Accepted Answer

f(i,*p). The expression 'f(i,*p)' correctly passes an integer and a short to the function 'f', as 'i' is an integer and '*p' dereferences to the short value stored in 's', thus matching the function's parameter types without causing a type checking error.

Question 4

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

Accepted Answer

Θ(n²), Θ(n log n), and Θ(n²). Insertion sort has a worst-case running time of Θ(n²) due to its nested loops when the input is in reverse order. Merge sort consistently performs at Θ(n log n) because it divides the array and merges sorted subarrays regardless of the input order. Quick sort, while efficient on average, can degrade to Θ(n²) in the worst case when the pivot selection is poor, such as when the smallest or largest element is consistently chosen.

Question 5

Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not

Accepted Answer

P only. Adding a constant to every edge preserves the relative order of edge weights, so the MST is unchanged (P true). But shortest paths can change because a path with more edges accumulates more added constant, so Q is false. Answer: P only.

Question 6

Consider the following C program.

#include<stdio.h>
void mystery(int *ptra, int *ptrb) {
 int *temp;
 temp = ptrb;
 ptrb = ptra;
 ptra = temp;
}

int main() {
 int a=2016, b=0, c=4, d=42;
 mystery(&a, &b);
 if (a < c)
 mystery(&c, &a);
 mystery(&a, &d);
 printf("%d
", a);
}

The output of

Accepted Answer

42. The function 'mystery' swaps the pointers but does not affect the values of the variables they point to. After the calls to 'mystery', the value of 'a' is ultimately set to the value of 'd', which is 42, making that the final output.

Question 7

Which of the following languages is generated by the given grammar?

S → aS | bS | ε

Accepted Answer

{a,b}*. The grammar allows for any combination of 'a' and 'b' by recursively adding 'a' or 'b' to the string, including the empty string, which means it can generate all possible strings made up of 'a' and 'b'.

Question 8

Which of the following decision problems are undecidable?

I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = Φ?
II. Given a CFG G = (N, Σ, P, S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G1 and G2, is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = Φ?

Accepted Answer

III and IV only. Options III and IV are correct because determining if two context-free grammars generate the same language (III) and whether the language of a Turing machine is empty (IV) are both undecidable problems, meaning there is no algorithm that can solve them for all possible inputs.

Question 9

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

Accepted Answer

(0 + 1)*(00(0 + 1)*11 + 11(0 + 1)*00)(0 + 1)*. The correct option captures the requirement for the presence of both '00' and '11' in any order within the binary strings, allowing for any characters before or after these patterns. This ensures that the strings can contain any combination of 0s and 1s while still meeting the criteria of having two consecutive 0s and two consecutive 1s.

Question 10

Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?

Accepted Answer

Shortest remaining time first. Shortest remaining time first (SRTF) minimizes the average waiting time by always selecting the process with the least remaining CPU burst time, allowing shorter processes to complete quickly and reducing the waiting time for subsequent processes.

Question 11

Which of the following is NOT a superkey in a relational schema with attributes V, W, X, Y, Z and primary key VY?

Accepted Answer

VWXZ. VWXZ is not a superkey because it does not include the primary key attributes V and Y together, which are necessary to uniquely identify a record in the relational schema.

Question 12

Which one of the following is NOT a part of the ACID properties of database transactions?

Accepted Answer

Deadlock-freedom. Deadlock-freedom is not one of the ACID properties; instead, it refers to a condition in which a set of processes cannot proceed because each is waiting for the other to release resources. The ACID properties focus on ensuring reliable transaction processing in databases.

Question 13

Which one of the following protocols is NOT used to resolve one form of address to another one?

Accepted Answer

DHCP. DHCP is primarily used for dynamically assigning IP addresses to devices on a network, rather than resolving one address type to another, which is the function of the other protocols listed.

Question 14

Which of the following is/are example(s) of stateful application layer protocols? (i) HTTP (ii) FTP (iii) TCP (iv) POP3

Accepted Answer

(ii) and (iv) only. FTP and POP3 are considered stateful application layer protocols because they maintain session information and state across multiple requests, unlike HTTP, which is stateless.

Question 15

Consider a carry lookahead adder for adding two n-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is

Accepted Answer

Θ(log(n)). The carry lookahead adder improves the speed of addition by calculating carry signals in parallel, allowing the addition process to be completed in logarithmic time relative to the number of bits, as it reduces the depth of the circuit to a logarithmic scale.

Question 16

The following function computes the maximum value contained in an integer array p[ ] of size n (n >= 1).

int max(int *p, int n) {
 int a=0, b=n-1;

while (__________) {
 if (p[a] <= p[b]) { a = a+1; }
 else { b = b-1; }
 }

return p[a];
}

The missing loop condition is

Accepted Answer

b != a. The loop condition 'b != a' ensures that the indices a and b do not cross each other, allowing the function to correctly compare elements from both ends of the array until the maximum value is found. This prevents the loop from terminating prematurely and guarantees that the maximum value is identified.

Question 17

What will be the output of the following C program?

void count(int n){
 static int d=1;

printf("%d ", n);
 printf("%d ", d);
 d++;
 if(n>1) count(n-1);
 printf("%d ", d);
}

void main(){
 count(3);
}

Accepted Answer

3 1 2 2 1 3 4 4. The correct output is generated by the recursive function, which prints the current value of 'n', the static variable 'd', and increments 'd' with each call. As the recursion unwinds, it prints 'd' again, resulting in the sequence observed in the correct option.

Question 18

An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest

Accepted Answer

O(d) but not O(1). After removing an element from a binary heap, the heap property must be restored, which involves either bubbling down or bubbling up the affected node. This process can take time proportional to the depth of the heap, denoted as d, since the maximum number of levels to traverse is equal to the depth.

Question 19

Accepted Answer

{a^m bⁿ | m ≥ 0 and n > 0} and {a^m bⁿ | m > 0 or n > 0}. The correct option accurately describes the languages generated by the grammars: G1 allows for any number of 'a's followed by at least one 'b', while G2 requires at least one 'a' or one 'b', ensuring that both languages have the specified conditions on the counts of 'a's and 'b's.

Question 20

Consider the transition diagram of a PDA given below with input alphabet Σ = {a,b} and stack alphabet Γ = {X,Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA. Which one of the following is TRUE?

Accepted Answer

L = {aⁿ | n ≥ 0} ∪ {aⁿ bⁿ | n ≥ 0} and is deterministic context-free. The correct option accurately describes the language accepted by the PDA as a union of two sets: strings of 'a's of any length and strings of 'a's followed by an equal number of 'b's. This language can be recognized by a deterministic pushdown automaton, confirming its classification as deterministic context-free.

Question 21

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that ̅Y reduces to W, and Z reduces to ̅X (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

Accepted Answer

W is not recursively enumerable and Z is recursive.. Since Y is r.e. but not recursive, its complement bar-Y is not r.e.; as bar-Y many-one reduces to W, W cannot be r.e. either. X is recursive so bar-X is recursive, and Z reducing to bar-X makes Z recursive. Thus W is not r.e. and Z is recursive.

Question 22

Consider the following proposed solution for the critical section problem. There are n processes: P0,...,Pn-1. In the code, function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero.

Code for Pi:

do {
 c[i]=1; t[i] = pmax(t[0],...,t[n-

Accepted Answer

At most one process can be in the critical section at any time. The solution ensures that only one process can enter the critical section by using the timestamp mechanism, where each process waits for others to finish based on their timestamps. This guarantees mutual exclusion, as a process will only enter the critical section when it has the highest timestamp among all processes.

Question 23

Consider the following two phase locking protocol. Suppose a transaction T accesses (for read or write operations), a certain set of objects {O1,...,Ok}. This is done in the following manner:

Step 1. T acquires exclusive locks to O1,...,Ok in increasing order of their addresses.
Step 2. T

Accepted Answer

guarantee serializability and deadlock-freedom. The protocol ensures that locks are acquired in a strict order, which prevents circular wait conditions, thereby achieving deadlock-freedom. Additionally, by acquiring all necessary locks before performing any operations, it guarantees that the transactions will execute in a manner that is equivalent to some serial execution, ensuring serializability.

Question 24

Consider that B wants to send a message m that is digitally signed to A. Let the pair of private and public keys for A and B be denoted by K_A⁻ and K_A⁺ for x = A,B, respectively. Let Kₓ(m) represent the operation of encrypting m with a key Kₓ and H(m) represent the message digest. Which o

Accepted Answer

{m, K_B^-(H(m))}. The correct option is right because B needs to sign the message digest H(m) using their private key K_B⁻, which allows A to verify the signature using B's public key K_B⁺. This ensures the authenticity and integrity of the message.

Question 25

Let x1 ⊕ x2 ⊕ x3 ⊕ x4 = 0 where x1, x2, x3, x4 are Boolean variables, and ⊕ is the XOR operator. Which one of the following must always be TRUE?

Accepted Answer

x̄1 ⊕ x̄3 = x̄2 ⊕ x̄4. The equation x1 ⊕ x2 ⊕ x3 ⊕ x4 = 0 indicates that the number of true values among x1, x2, x3, and x4 must be even. The correct option shows that the negations of the variables also maintain this even parity, as the XOR operation on the negated variables reflects the same relationship.

Question 26

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

I. Quicksort runs in Θ(n²) time
II. Bubblesort runs in Θ(n²) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs i

Accepted Answer

(D) I and IV only. Quicksort has a worst-case time complexity of Θ(n²) when the input is already sorted, as it may repeatedly choose poor pivot elements. Insertion sort, however, is efficient for already sorted data, operating in Θ(n) time as it only requires a single pass through the list to confirm order.

Question 27

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Accepted Answer

Dynamic Programming paradigm.. The Floyd-Warshall algorithm utilizes dynamic programming by systematically considering all pairs of vertices and updating the shortest path estimates based on previously computed paths, ensuring that all possible paths are evaluated efficiently.

Question 28

Language L1 is defined by the grammar: S1 → aS1b | ε
Language L2 is defined by the grammar: S2 → abS2 | ε
Consider the following statements:
P: L1 is regular
Q: L2 is regular
Which one of the following is TRUE?

Accepted Answer

P is false and Q is true. L1 generates a^n b^n, which is not regular (requires matching counts, provable by pumping lemma). L2 generates (ab)^n = (ab)*, which is regular. So P is false and Q is true.

Question 29

Consider the following types of languages: L1: Regular, L2: Context-free, L3: Recursive, L4: Recursively enumerable. Which of the following is/are TRUE?
I. L̅3 ∪ L4 is recursively enumerable
II. L̅2 ∪ L3 is recursive
III. L1* ∩ L2 is context-free
IV. L̅1 ∪ L̅2 is context-free

Accepted Answer

I, II and III only. The correct options are true because: I states that the complement of a recursive language combined with a recursively enumerable language is recursively enumerable, which is accurate; II indicates that the union of the complement of a context-free language and a recursive language is recursive, which holds true; III asserts that the intersection of a regular language (which is closed under intersection) and a context-free language results in a context-free language, which is also correct.

Question 30

Match the following:
(P) Lexical analysis
(Q) Top down parsing
(R) Semantic analysis
(S) Runtime environments
(i) Leftmost derivation
(ii) Type checking
(iii) Regular expressions
(iv) Activation records

Accepted Answer

P ↔ iii, Q ↔ i, R ↔ ii, S ↔ iv. The correct option matches lexical analysis with regular expressions, as it involves tokenizing input based on patterns defined by regular expressions. Top-down parsing is associated with leftmost derivation, which is a method of constructing parse trees. Semantic analysis relates to type checking, ensuring that operations in the code are semantically valid, while runtime environments are linked to activation records, which manage function calls and local variables during execution.

Question 31

In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when the number of allocated frames increases?

Accepted Answer

FIFO (First In First Out). FIFO can lead to an increase in page fault rates when more frames are allocated because it may evict pages that are still needed, unlike other algorithms that consider usage patterns.

Question 32

B+ Trees are considered BALANCED because

Accepted Answer

the lengths of the paths from the root to all leaf nodes are all equal.. B+ Trees are balanced because all leaf nodes are at the same depth, ensuring that the paths from the root to each leaf node are of equal length, which allows for efficient searching and maintaining order.

Question 33

Suppose a database schedule S involves transactions T1,..., Tn. Construct the precedence graph of S with vertices representing the transactions and edges representing the conflicts. If S is serializable, which one of the following orderings of the vertices of the precedence graph is guaran

Accepted Answer

Topological order. A topological order of the vertices in a precedence graph ensures that for every directed edge from transaction Ti to Tj, Ti appears before Tj in the ordering. This property is essential for constructing a serial schedule that respects the conflicts represented in the graph, thereby guaranteeing serializability.

Question 34

Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires

Accepted Answer

Anarkali’s public key.. To verify a digital signature, the recipient needs the sender's public key, which is used to confirm that the signature was created with the corresponding private key, ensuring the authenticity of the message.

Question 35

In an Ethernet local area network, which one of the following statements is TRUE?

Accepted Answer

The exponential backoff mechanism reduces the probability of collision on retransmissions.. The exponential backoff mechanism helps to minimize the chances of collisions during retransmissions by increasing the wait time exponentially after each successive collision, allowing more time for the network to clear before attempting to resend the data.

Question 36

Identify the correct sequence in which the following packets are transmitted on the network by a host when a browser requests a webpage from a remote server, assuming that the host has just been restarted.

Accepted Answer

DNS query, TCP SYN, HTTP GET request. The correct sequence starts with a DNS query to resolve the domain name into an IP address, followed by a TCP SYN packet to establish a connection with the server, and finally the HTTP GET request to retrieve the webpage.

Question 37

A binary relation R on N × N is defined as follows: (a,b)R(c,d) if a ≤ c or b ≤ d. Consider the following propositions:
P: R is reflexive
Q: R is transitive
Which one of the following statements is TRUE?

Accepted Answer

P is true and Q is false.. The relation R is reflexive because for any pair (a,b), it holds that (a,b)R(a,b) since a ≤ a and b ≤ b. However, R is not transitive because if (a,b)R(c,d) and (c,d)R(e,f), it does not necessarily follow that (a,b)R(e,f) since the conditions can fail when combining the inequalities.

Question 38

Which one of the following well-formed formulae in predicate calculus is NOT valid?

Accepted Answer

∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x)). The formula ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x)) is not valid because it suggests that if every element satisfies either p or q, then every element must satisfy p or every element must satisfy q, which is not necessarily true; there can be elements that satisfy p and others that satisfy q.

Question 39

The following function computes X^Y for positive integers X and Y.

int exp(int X, int Y) {
 int res = 1, a = X, b = Y;

while (b != 0) {
 if (b%2 == 0) { a = a*a; b = b/2; }
 else { res = res*a; b = b-1; }
 }
 return res;
}

Which one of the following conditions is TRUE before every iter

Accepted Answer

(C) X^Y = res * a^b. The condition X^Y = res * a^b holds true before each iteration because the algorithm progressively breaks down the exponent Y while maintaining the product of the accumulated result (res) and the current base (a) raised to the remaining exponent (b). This ensures that the overall value of X^Y is preserved throughout the loop.

Question 40

In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to

Accepted Answer

Θ(n+m). The time complexity is Θ(n+m) because each vertex's adjacency list is processed once to set the twin pointers, resulting in a linear traversal of all vertices (n) and edges (m) in the graph.

Question 41

Consider the following two statements:
I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ*.
II. There exists a regular language A such that for all languages B, A ∩ B is regular.
Which one of the following is CORRECT?

Accepted Answer

Only II is true. Statement I is false because if all states of an NFA are accepting, it only means that the NFA accepts all strings that can be formed from the input alphabet, but it does not guarantee acceptance of all possible strings in Σ*. Statement II is true as the regular language A can be chosen as the empty set, which ensures that the intersection with any language B remains regular.

Question 42

Consider the following languages:
L1 = {aⁿ b^m c^(n+m): m,n ≥ 1}
L2 = {aⁿ bⁿ c^(2n): n ≥ 1}
Which one of the following is TRUE?

Accepted Answer

Both L1 and L2 are context-free.. Both languages L1 and L2 can be generated by context-free grammars, as they can be described by rules that allow for the correct counting and arrangement of symbols, thus satisfying the properties of context-free languages.

Question 43

Which one of the following grammars is free from left recursion?

Accepted Answer

S → Ab | Bb | c
A → Bd | ε
B → e. The correct option is free from left recursion because none of its productions lead to a non-terminal that can eventually derive itself as the first symbol in the derivation, thus preventing infinite loops during parsing.

Question 44

Consider the following two-process synchronization solution.

Process 0
--------
Entry: loop while (turn == 1);
 (critical section)
Exit: turn = 1;

Process 1
--------
Entry: loop while (turn == 0);
 (critical section)
Exit: turn = 0;

The shared variable turn is initialized to zero. Which

Accepted Answer

This solution violates progress requirement.. The solution violates the progress requirement because if one process enters its critical section, the other process may be indefinitely delayed if it keeps waiting for the turn variable to change, leading to a situation where neither process can proceed.

Question 45

Consider the following database schedule with two transactions, T1 and T2.

S = r2(X); r1(X); r2(Y); w1(X); r1(Y); w2(X); a1; a2

where ri(Z) denotes a read operation by transaction Ti on a variable Z, wi(Z) denotes a write operation by Ti on a variable Z, and ai denotes abort by transacti

Accepted Answer

S does not have a cascading abort. The schedule does not have a cascading abort because T1 reads the values of X and Y before T2 writes to X, meaning T1's operations are not dependent on T2's writes. Therefore, if T2 were to abort, T1 would not be affected by any uncommitted changes.

Question 46

For the IEEE 802.11 MAC protocol for wireless communication, which of the following statements is/are TRUE?

I. At least three non-overlapping channels are available for transmissions.
II. The RTS-CTS mechanism is used for collision detection.
III. Unicast frames are ACKed.

Accepted Answer

I and III only. Statement I is true because the IEEE 802.11 standard provides multiple non-overlapping channels for efficient communication. Statement III is also true as unicast frames require acknowledgment to ensure successful delivery. However, statement II is incorrect because the RTS-CTS mechanism is used for collision avoidance, not detection.

Question 47

Consider the following C program.

#include<stdio.h>
struct Ournode{
 char x,y,z;
};

int main(){
 struct Ournode p = {'1', '0', 'a'+2};
 struct Ournode *q = &p;
 printf ("%c, %c", *((char*)q+1), *((char*)q+2));
 return 0;
}

The output of this program is:

Accepted Answer

0,c. The program initializes a struct with characters, where '1' is at index 0, '0' at index 1, and 'a'+2 evaluates to 'c' at index 2. The pointer arithmetic used in the printf statement accesses the second and third characters of the struct, resulting in '0' and 'c' being printed.

Question 48

A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of

Accepted Answer

Θ(1), Θ(n). In this implementation, enqueueing a new node at the head can be done in constant time, Θ(1), since it only requires adjusting the head pointer. However, dequeuing from the tail requires traversing the entire list to find the second-to-last node, resulting in a linear time complexity of Θ(n).

Question 49

Consider the following statements regarding the slow start phase of the TCP congestion control algorithm. Note that cwnd stands for the TCP congestion window and MSS denotes the Maximum Segment Size.
(i) The cwnd increases by 2 MSS on every successful acknowledgement.
(ii) The cwnd approxi

Accepted Answer

Only (iv) is true. During slow start cwnd increases by 1 MSS per ACK, which makes it roughly double every round-trip time. So (i) and (ii) (per-ACK doubling/+2) are false and (iii) (+1 MSS per RTT) is false; only (iv) (doubles every RTT) is true.

Question 50

Assume that multiplying a matrix G1 of dimension p × q with another matrix G2 of dimension q × r requires pqr scalar multiplications. Computing the product of n matrices G1 G2 G3... Gn can be done by parenthesizing in different ways. Define G_i G_(i+1) as an explicitly computed pair for a

Accepted Answer

F3F4 only. With dimensions 2x25, 25x3, 3x16, 16x1, 1x1000, the optimal parenthesization is ((F1(F2(F3F4)))F5) with 2173 scalar multiplications. The only directly multiplied adjacent pair is F3F4, so option 2 is correct; the stored answer (F1F2 and F3F4) is wrong.

GATE Technical: COMPUTER SCIENCE AND INFORMATION TECHNOLOGY questions with solutions

Questions