Success TrackerSuccess Tracker
Log inSign up

The PYQ practice room

GATE CS 2018 Set 1

All 65 solved GATE CS 2018 Set 1 questions in exam order. Open a question, commit to an answer, and learn from the step-by-step solution. One question at a time.

Attempt before revealInstant answer feedbackExplore questions
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.

Questions

65

Paper marks

100

Question formats

2

MCQ · NAT

Revision mode

Self-paced

No timer. Focus on understanding.

Difficulty mixEasy 22Medium 35Hard 8

Explore the questions

65 of 65 questions

General Aptitude (GA)

10
  1. Think it through. Then check your answer.

    Question

    “From where are they bringing their books? ______ bringing ___ books from ___.”
    The words that best fill the blanks in the above sentence are
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  2. Think it through. Then check your answer.

    Question

    “A _________ investigation can sometimes yield new facts, but typically organized ones are more successful.”
    The word that best fills the blank in the above sentence is
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  3. Think it through. Then check your answer.

    Question

    The area of a square is dd. What is the area of the circle which has the diagonal of the square as its diameter?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  4. Think it through. Then check your answer.

    Question

    What would be the smallest natural number which when divided either by 20 or by 42 or by 76 leaves a remainder of 7 in each case?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  5. Think it through. Then check your answer.

    Question

    What is the missing number in the following sequence?
    2, 12, 60, 240, 720, 1440, _____, 0
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  6. Think it through. Then check your answer.

    Question

    In appreciation of the social improvements completed in a town, a wealthy philanthropist decided to gift Rs 750 to each male senior citizen in the town and Rs 1000 to each female senior citizen. Altogether, there were 300 senior citizens eligible for this gift. However, only 8/9th8/9^{th} of the eligible men and 2/3rd2/3^{rd} of the eligible women claimed the gift. How much money (in Rupees) did the philanthropist give away in total?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  7. Think it through. Then check your answer.

    Question

    If pqr≠0pqr \neq 0 and p−x=1q,q−y=1r,r−z=1pp^{-x} = \frac{1}{q}, q^{-y} = \frac{1}{r}, r^{-z} = \frac{1}{p}, what is the value of the product xyzxyz?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  8. Think it through. Then check your answer.

    Question

    In a party, 60% of the invited guests are male and 40% are female. If 80% of the invited guests attended the party and if all the invited female guests attended, what would be the ratio of males to females among the attendees in the party?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  9. Think it through. Then check your answer.

    Question

    In the figure below, ∠DEC+∠BFC\angle DEC + \angle BFC is equal to ____________ .
    A geometric figure showing a quadrilateral ABCD with sides extended to meet at points E and F. Point E is the intersection of lines AD and BC extended. Point F is the intersection of lines AB and DC extended.
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  10. Think it through. Then check your answer.

    Question

    A six sided unbiased die with four green faces and two red faces is rolled seven times. Which of the following combinations is the most likely outcome of the experiment?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page

COMPUTER SCIENCE AND INFORMATION TECHNOLOGY

55
  1. Think it through. Then check your answer.

    Question

    Which one of the following is a closed form expression for the generating function of the sequence {an}\{a_n\}, where an=2n+3a_n = 2n + 3 for all n=0,1,2,…n = 0, 1, 2, \dots ?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  2. Think it through. Then check your answer.

    Question

    Consider the following C program.
    The output of this program is:
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  3. Think it through. Then check your answer.

    Question

    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 nn 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 a node from the tail.
    Diagram of a singly linked list with head and tail pointers. Head points to the first node, tail points to the last node. Arrows point from left to right.
    Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  4. Think it through. Then check your answer.

    Question

    Let ⊕\oplus and ⊙\odot denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  5. Think it through. Then check your answer.

    Question

    Consider the following processor design characteristics.
    I. Register-to-register arithmetic operations only
    II. Fixed-length instruction format
    III. Hardwired control unit
    Which of the characteristics above are used in the design of a RISC processor?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  6. Think it through. Then check your answer.

    Question

    Let NN be an NFA with nn states. Let kk be the number of states of a minimal DFA which is equivalent to NN. Which one of the following is necessarily true?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  7. Think it through. Then check your answer.

    Question

    The set of all recursively enumerable languages is
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  8. Think it through. Then check your answer.

    Question

    Which one of the following statements is FALSE?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  9. Think it through. Then check your answer.

    Question

    The following are some events that occur after a device controller issues an interrupt while process LL is under execution.
    (P) The processor pushes the process status of LL onto the control stack.
    (Q) The processor finishes the execution of the current instruction.
    (R) The processor executes the interrupt service routine.
    (S) The processor pops the process status of LL from the control stack.
    (T) The processor loads the new PC value based on the interrupt.
    Which one of the following is the correct order in which the events above occur?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  10. Think it through. Then check your answer.

    Question

    Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is MM units if the corresponding memory page is available in memory, and DD units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is XX units.
    Which one of the following is the correct expression for the page fault rate experienced by the process?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  11. Think it through. Then check your answer.

    Question

    In an Entity-Relationship (ER) model, suppose RR is a many-to-one relationship from entity set E1 to entity set E2. Assume that E1 and E2 participate totally in RR and that the cardinality of E1 is greater than the cardinality of E2.
    Which one of the following is true about RR?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  12. Think it through. Then check your answer.

    Question

    Consider the following two tables and four queries in SQL.
    Book (isbn, bname), Stock (isbn, copies)
    Query 1:
    SELECT B.isbn, S.copies
FROM Book B INNER JOIN Stock S
ON B.isbn = S.isbn;

    Query 2:
    SELECT B.isbn, S.copies
FROM Book B LEFT OUTER JOIN Stock S
ON B.isbn = S.isbn;

    Query 3:
    SELECT B.isbn, S.copies
FROM Book B RIGHT OUTER JOIN Stock S
ON B.isbn = S.isbn;

    Query 4:
    SELECT B.isbn, S.copies
FROM Book B FULL OUTER JOIN Stock S
ON B.isbn = S.isbn;

    Which one of the queries above is certain to have an output that is a superset of the outputs of the other three queries?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  13. Think it through. Then check your answer.

    Question

    Match the following:
    FieldLength in bits
    P. UDP Header’s Port NumberI. 48
    Q. Ethernet MAC AddressII. 8
    R. IPv6 Next HeaderIII. 32
    S. TCP Header’s Sequence NumberIV. 16
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  14. Think it through. Then check your answer.

    Question

    Consider the following statements regarding the slow start phase of the TCP congestion control algorithm. Note that cwndcwnd stands for the TCP congestion window and MSS denotes the Maximum Segment Size.
    (i) The cwndcwnd increases by 2 MSS on every successful acknowledgment.
    (ii) The cwndcwnd approximately doubles on every successful acknowledgement.
    (iii) The cwndcwnd increases by 1 MSS every round trip time.
    (iv) The cwndcwnd approximately doubles every round trip time.
    Which one of the following is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  15. Think it through. Then check your answer.

    Question

    Two people, P and Q, decide to independently roll two identical dice, each with 6 faces, numbered 1 to 6. The person with the lower number wins. In case of a tie, they roll the dice repeatedly until there is no tie. Define a trial as a throw of the dice by P and Q. Assume that all 6 numbers on each dice are equi-probable and that all trials are independent. The probability (rounded to 3 decimal places) that one of them wins on the third trial is _____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  16. Think it through. Then check your answer.

    Question

    The value of ∫0π/4xcos⁡(x2)dx\int_0^{\pi/4} x \cos(x^2) dx correct to three decimal places (assuming that π=3.14\pi = 3.14) is _____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  17. Think it through. Then check your answer.

    Question

    Consider a matrix A=uvTA = uv^T where u=(12),v=(11)u = \begin{pmatrix} 1 \\ 2 \end{pmatrix}, v = \begin{pmatrix} 1 \\ 1 \end{pmatrix}. Note that vTv^T denotes the transpose of vv. The largest eigenvalue of AA is _____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  18. Think it through. Then check your answer.

    Question

    The chromatic number of the following graph is _______.
    A simple undirected graph with 6 vertices labeled a, b, c, d, e, f.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  19. Think it through. Then check your answer.

    Question

    Let GG be a finite group on 84 elements. The size of a largest possible proper subgroup of GG is ________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  20. Think it through. Then check your answer.

    Question

    The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  21. Think it through. Then check your answer.

    Question

    Consider the following C program.
    #include <stdio.h>
int counter = 0;
int calc (int a, int b) {
 int c;
 counter++;
 if (b==3) return (a*a*a);
 else {
 c = calc(a, b/3);
 return (c*c*c);
 }
}
int main (){
 calc(4, 81);
 printf ("%d", counter);
}
    The output of this program is _____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  22. Think it through. Then check your answer.

    Question

    Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops.
    sequential circuit with two D flip-flops and an XOR gate
    The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of “in” is _____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  23. Think it through. Then check your answer.

    Question

    A 3232-bit wide main memory unit with a capacity of 1 GB1\text{ GB} is built using 256M×4-bit256\text{M} \times 4\text{-bit} DRAM chips. The number of rows of memory cells in the DRAM chip is 2142^{14}. The time taken to perform one refresh operation is 50 nanoseconds50\text{ nanoseconds}. The refresh period is 2 milliseconds2\text{ milliseconds}. The percentage (rounded to the closest integer) of the time available for performing the memory read/write operations in the main memory unit is __________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  24. Think it through. Then check your answer.

    Question

    Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of KK instances. Resource instances can be requested and released only one at a time. The largest value of KK that will always avoid deadlock is ____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  25. Think it through. Then check your answer.

    Question

    Q.25 Consider a long-lived TCP session with an end-to-end bandwidth of 1 Gbps (=109= 10^9 bits-per-second). The session starts with a sequence number of 1234. The minimum time (in seconds, rounded to the closest integer) before this sequence number can be used again is _______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  26. Think it through. Then check your answer.

    Question

    Consider a matrix P whose only eigenvectors are the multiples of [14]\begin{bmatrix} 1 \\ 4 \end{bmatrix}.
    Consider the following statements.
    (I) P does not have an inverse
    (II) P has a repeated eigenvalue
    (III) P cannot be diagonalized
    Which one of the following options is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  27. Think it through. Then check your answer.

    Question

    Let NN be the set of natural numbers. Consider the following sets.
    PP: Set of Rational numbers (positive and negative)
    QQ: Set of functions from {0,1}\{0, 1\} to NN
    RR: Set of functions from NN to {0,1}\{0, 1\}
    SS: Set of finite subsets of NN.
    Which of the sets above are countable?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  28. Think it through. Then check your answer.

    Question

    Consider the first-order logic sentenceϕ≡∃s∃t∃u∀v∀w∀x∀yψ(s,t,u,v,w,x,y)\phi \equiv \exists s \exists t \exists u \forall v \forall w \forall x \forall y \psi(s, t, u, v, w, x, y)where ψ(s,t,u,v,w,x,y)\psi(s, t, u, v, w, x, y) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose ϕ\phi has a model with a universe containing 7 elements.
    Which one of the following statements is necessarily true?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  29. Think it through. Then check your answer.

    Question

    Consider the following C program:
    #include<stdio.h>
void fun1(char *s1, char *s2){
char *tmp;
tmp = s1;
s1 = s2;
s2 = tmp;
}
void fun2(char **s1, char **s2){
char *tmp;
tmp = *s1;
*s1 = *s2;
*s2 = tmp;
}
int main(){
char *str1 = "Hi", *str2 = "Bye";
fun1(str1, str2); printf("%s %s ", str1, str2);
fun2(&str1, &str2); printf("%s %s", str1, str2);
return 0;
}
    The output of the program above is
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  30. Think it through. Then check your answer.

    Question

    Let G be a simple undirected graph. Let TDT_D be a depth first search tree of G. Let TBT_B be a breadth first search tree of G. Consider the following statements.
    (I) No edge of G is a cross edge with respect to TDT_D. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TDT_D.)
    (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TBT_B, then ∣i–j∣=1|i – j| = 1.
    Which of the statements above must necessarily be true?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  31. Think it through. Then check your answer.

    Question

    Assume that multiplying a matrix G1G_1 of dimension p×qp \times q with another matrix G2G_2 of dimension q×rq \times r requires pqrpqr scalar multiplications. Computing the product of n matrices G1G2G3...GnG_1G_2G_3... G_n can be done by parenthesizing in different ways. Define GiGi+1G_iG_{i+1} as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain G1G2G3G4G5G6G_1G_2G_3G_4G_5G_6 using parenthesization (G1(G2G3))(G4(G5G6))(G_1(G_2G_3))(G_4(G_5G_6)), G2G3G_2G_3 and G5G6G_5G_6 are the only explicitly computed pairs.
    Consider a matrix multiplication chain F1F2F3F4F5F_1F_2F_3F_4F_5, where matrices F1,F2,F3,F4F_1, F_2, F_3, F_4 and F5F_5 are of dimensions 2x25, 25x3, 3x16, 16x1 and 1x1000, respectively. In the parenthesization of F1F2F3F4F5F_1F_2F_3F_4F_5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  32. Think it through. Then check your answer.

    Question

    Consider the following C code. Assume that unsigned long int type length is 64 bits.
    unsigned long int fun(unsigned long int n){
    unsigned long int i, j = 0, sum = 0;
    for (i = n; i > 1; i = i/2) j++;
    for ( ; j > 1; j = j/2) sum++;
    return(sum);
}

    The value returned when we call fun with the input 2402^{40} is ____.
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  33. Think it through. Then check your answer.

    Question

    Consider the unsigned 8-bit fixed point binary number representation below,b7b6b5b4b3.b2b1b0b_7 b_6 b_5 b_4 b_3 . b_2 b_1 b_0where the position of the binary point is between b3b_3 and b2b_2. Assume b7b_7 is the most significant bit. Some of the decimal numbers listed below cannot be represented exactly in the above representation:
    (i) 31.500
    (ii) 0.875
    (iii) 12.100
    (iv) 3.001
    Which one of the following statements is true?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  34. Think it through. Then check your answer.

    Question

    The size of the physical address space of a processor is 2P2^P bytes. The word length is 2W2^W bytes. The capacity of cache memory is 2N2^N bytes. The size of each cache block is 2M2^M words. For a KK-way set-associative cache memory, the length (in number of bits) of the tag field is
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  35. Think it through. Then check your answer.

    Question

    Consider the following languages:
    I. {ambncpdq∣m+p=n+q, where m,n,p,q≥0}\{a^m b^n c^p d^q \mid m + p = n + q, \text{ where } m, n, p, q \geq 0\}
    II. {ambncpdq∣m=n and p=q, where m,n,p,q≥0}\{a^m b^n c^p d^q \mid m = n \text{ and } p = q, \text{ where } m, n, p, q \geq 0\}
    III. {ambncpdq∣m=n=p and p≠q, where m,n,p,q≥0}\{a^m b^n c^p d^q \mid m = n = p \text{ and } p \neq q, \text{ where } m, n, p, q \geq 0\}
    IV. {ambncpdq∣mn=p+q, where m,n,p,q≥0}\{a^m b^n c^p d^q \mid mn = p + q, \text{ where } m, n, p, q \geq 0\}
    Which of the languages above are context-free?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  36. Think it through. Then check your answer.

    Question

    Consider the following problems. L(G) denotes the language generated by a grammar GG. L(M) denotes the language accepted by a machine MM.
    (I) For an unrestricted grammar GG and a string ww, whether w∈L(G)w \in L(G)
    (II) Given a Turing machine MM, whether L(M) is regular
    (III) Given two grammars G1G_1 and G2G_2, whether L(G1)=L(G2)L(G_1) = L(G_2)
    (IV) Given an NFA NN, whether there is a deterministic PDA PP such that NN and PP accept the same language.
    Which one of the following statements is correct?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  37. Think it through. Then check your answer.

    Question

    A lexical analyzer uses the following patterns to recognize three tokens T1T_1, T2T_2, and T3T_3 over the alphabet {a,b,c}\{a,b,c\}.

    T1:a?(b∣c)∗aT_1: a? (b|c)^* a
    T2:b?(a∣c)∗bT_2: b? (a|c)^* b
    T3:c?(b∣a)∗cT_3: c? (b|a)^* c

    Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.
    If the string bbaacabc is processed by the analyzer, which one of the following is the sequence of tokens it outputs?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  38. Think it through. Then check your answer.

    Question

    Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #.
    Parse tree for the expression. The root is #. Its left child is 'a'. Its right child is a subtree rooted at #. This # node has a left child rooted at $ and a right child rooted at #. The $ subtree represents ((b $ c) $ d). The rightmost # subtree represents (e # f).
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  39. Think it through. Then check your answer.

    Question

    In a system, there are three types of resources: E,FE, F and GG. Four processes P0,P1,P2P_0, P_1, P_2 and P3P_3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P2,FP_2,F] is the maximum number of instances of FF that P2P_2 would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation.
    Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of EE and 3 instances of FF are the only resources available.
    AllocationMax
    EEFFGGEEFFGG
    P0P_0101431
    P1P_1112214
    P2P_2103133
    P3P_3200541
    From the perspective of deadlock avoidance, which one of the following is true?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  40. Think it through. Then check your answer.

    Question

    Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is NN. Three semaphores empty, full and mutex are defined with respective initial values of 0, NN and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R, and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait() and signal().
    Producer:Consumer:
    do{do{
    wait(P); wait(R);
    wait(mutex); wait(mutex);
    //Add item to buffer //Consume item from buffer
    signal(mutex); signal(mutex);
    signal(Q); signal(S);
    }while(1);}while(1);
    Which one of the following assignments to P, Q, R and S will yield the correct solution?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  41. Think it through. Then check your answer.

    Question

    Consider the relations r(A,B)r(A, B) and s(B,C)s(B, C), where s.Bs.B is a primary key and r.Br.B is a foreign key referencing s.Bs.B. Consider the queryQ:r⋈(σB<5(s))Q: r \bowtie (\sigma_{B < 5}(s))Let LOJLOJ denote the natural left outer-join operation. Assume that rr and ss contain no null values.
    Which one of the following queries is NOT equivalent to QQ?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  42. Think it through. Then check your answer.

    Question

    Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys.
    Schema I: Registration (rollno, courses)
    Field ‘courses’ is a set-valued attribute containing the set of courses a student has registered for.
    Non-trivial functional dependency:
    rollno →\rightarrow courses
    Schema II: Registration (rollno, courseid, email)
    Non-trivial functional dependencies:
    rollno, courseid →\rightarrow email
    email →\rightarrow rollno
    Schema III: Registration (rollno, courseid, marks, grade)
    Non-trivial functional dependencies:
    rollno, courseid →\rightarrow marks, grade
    marks →\rightarrow grade
    Schema IV: Registration (rollno, courseid, credit)
    Non-trivial functional dependencies:
    rollno, courseid →\rightarrow credit
    courseid →\rightarrow credit
    Which one of the relational schemas above is in 3NF but not in BCNF?
    Your answer

    Choose one option, then check your answer.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  43. Think it through. Then check your answer.

    Question

    Let GG be a graph with 100!100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,…,1001, 2, \dots, 100. There is an edge between vertices uu and vv if and only if the label of uu can be obtained by swapping two adjacent numbers in the label of vv. Let yy denote the degree of a vertex in GG, and zz denote the number of connected components in GG. Then, y+10z=_____.y + 10z = \_\_\_\_\_.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  44. Think it through. Then check your answer.

    Question

    Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (HH), medium (MM) and low (LL). Let P(HG)P(H_G) denote the probability that Guwahati has high temperature. Similarly, P(MG)P(M_G) and P(LG)P(L_G) denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use P(HD)P(H_D), P(MD)P(M_D) and P(LD)P(L_D) for Delhi.
    The following table gives the conditional probabilities for Delhi’s temperature given Guwahati’s temperature.
    HDH_DMDM_DLDL_D
    HGH_G0.400.480.12
    MGM_G0.100.650.25
    LGL_G0.010.500.49
    Consider the first row in the table above. The first entry denotes that if Guwahati has high temperature (HGH_G) then the probability of Delhi also having a high temperature (HDH_D) is 0.40; i.e., P(HD∣HG)=0.40P(H_D|H_G) = 0.40. Similarly, the next two entries are P(MD∣HG)=0.48P(M_D|H_G) = 0.48 and P(LD∣HG)=0.12P(L_D|H_G) = 0.12. Similarly for the other rows.
    If it is known that P(HG)=0.2P(H_G) = 0.2, P(MG)=0.5P(M_G) = 0.5, and P(LG)=0.3P(L_G) = 0.3, then the probability (correct to two decimal places) that Guwahati has high temperature given that Delhi has high temperature is _______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  45. Think it through. Then check your answer.

    Question

    Consider the following program written in pseudo-code. Assume that xx and yy are integers.
    Count(x,y) {
    if (y != 1){ 
        if (x != 1) {
            print("*");
            Count(x/2, y);
        }
        else {
            y = y-1;
            Count(1024, y);
        }
    }
}
    The number of times that the print statement is executed by the call Count(1024,1024) is _____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  46. Think it through. Then check your answer.

    Question

    The number of possible min-heaps containing each value from {1,2,3,4,5,6,7}\{1, 2, 3, 4, 5, 6, 7\} exactly once is _____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  47. Think it through. Then check your answer.

    Question

    Consider the following undirected graph G:
    An undirected graph with 6 nodes and 9 weighted edges. The nodes are arranged with one at the top, two in the middle, and three at the bottom. The edge weights are: top-left edge is 4, top-right edge is $x$, top-to-bottom-center edge is 1, middle-left-to-bottom-center edge is 3, middle-right-to-bottom-center edge is 3, middle-left-to-bottom-left edge is 4, bottom-left-to-bottom-center edge is 4, bottom-center-to-bottom-right edge is 4, and middle-right-to-bottom-right edge is 5.
    Choose a value for xx that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of xx is ______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  48. Think it through. Then check your answer.

    Question

    Consider the weights and values of items listed below. Note that there is only one unit of each item.
    Item numberWeight (in Kgs)Value (in Rupees)
    11060
    2728
    3420
    4224
    The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by VoptV_{opt}. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by VgreedyV_{greedy}.
    The value of Vopt−VgreedyV_{opt} - V_{greedy} is ____________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  49. Think it through. Then check your answer.

    Question

    Consider the minterm list form of a Boolean function FF given below.F(P,Q,R,S)=∑m(0,2,5,7,9,11)+d(3,8,10,12,14)F(P, Q, R, S) = \sum m(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)Here, mm denotes a minterm and dd denotes a don't care term. The number of essential prime implicants of the function FF is ______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  50. Think it through. Then check your answer.

    Question

    The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. Assume that there are no data hazards and no control hazards.
    The number of clock cycles required for completion of execution of the sequence of instructions is ______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  51. Think it through. Then check your answer.

    Question

    A processor has 16 integer registers (R0, R1, .. , R15) and 64 floating point registers (F0, F1,… , F63). It uses a 2-byte instruction format. There are four categories of instructions: Type-1, Type-2, Type-3, and Type-4. Type-1 category consists of four instructions, each with 3 integer register operands (3Rs). Type-2 category consists of eight instructions, each with 2 floating point register operands (2Fs). Type-3 category consists of fourteen instructions, each with one integer register operand and one floating point register operand (1R+1F). Type-4 category consists of NN instructions, each with a floating point register operand (1F).
    The maximum value of NN is __________.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  52. Think it through. Then check your answer.

    Question

    Given a language LL, define LiL^i as follows:L0={ε}L^0 = \{\varepsilon\}Li=Li−1⋅L for all i>0L^i = L^{i-1} \cdot L \text{ for all } i > 0The order of a language LL is defined as the smallest kk such that Lk=Lk+1L^k = L^{k+1}.
    Consider the language L1L_1 (over alphabet 0) accepted by the following automaton.
    Finite automaton with three states. The start state (left) transitions to the middle state on input '0'. The middle state is an accepting state (double circle) and transitions to the right state on input '0'. The right state transitions back to the middle state on input '0'.
    The order of L1L_1 is _____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  53. Think it through. Then check your answer.

    Question

    Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, … , 199), and 256 sectors per track (numbered as 0, 1, … , 255). The following 6 disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time:[120,72,2],[180,134,1],[60,20,0],[212,86,3],[56,116,2],[118,16,1][120, 72, 2] , [180, 134, 1] , [60, 20, 0] , [212, 86, 3] , [56, 116, 2] , [118, 16, 1]
    Currently the head is positioned at sector number 100 of cylinder 80, and is moving towards higher cylinder numbers. The average power dissipation in moving the head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head between different platters is negligible.
    The total power consumption in milliwatts to satisfy all of the above disk requests using the Shortest Seek Time First disk scheduling algorithm is _______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  54. Think it through. Then check your answer.

    Question

    Consider an IP packet with a length of 4,500 bytes that includes a 20-byte IPv4 header and a 40-byte TCP header. The packet is forwarded to an IPv4 router that supports a Maximum Transmission Unit (MTU) of 600 bytes. Assume that the length of the IP header in all the outgoing fragments of this packet is 20 bytes. Assume that the fragmentation offset value stored in the first fragment is 0.
    The fragmentation offset value stored in the third fragment is _______.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page
  55. Think it through. Then check your answer.

    Question

    Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carrier-sense based medium access protocol. A node that receives a packet to transmit will carrier-sense the medium for 5 units of time. If the node does not detect any other transmission in this duration, it starts transmitting its packet in the next time unit. If the node detects another transmission, it waits until this other transmission finishes, and then begins to carrier-sense for 5 time units again. Once they start to transmit, nodes do not perform any collision detection and continue transmission even if a collision occurs. All transmissions last for 20 units of time. Assume that the transmission signal travels at the speed of 10 meters per unit time in the medium.
    Assume that the system has two nodes P and Q, located at a distance dd meters from each other. P starts transmitting a packet at time t=0t=0 after successfully completing its carrier-sense phase. Node Q has a packet to transmit at time t=0t=0 and begins to carrier-sense the medium.
    The maximum distance dd (in meters, rounded to the closest integer) that allows Q to successfully avoid a collision between its proposed transmission and P’s ongoing transmission is _____.
    Your answer

    Enter a number. Decimals, negative values and scientific notation are accepted.

    Restoring your progress…

    The solution stays hidden until you check.
    Open question page