# GATE Numerical Answer Questions

Question 1

**Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L ≠ G and that the size of L is at least 4. The size of L is _______.**

.

Correct answer is =5

Solution :

Order of subgroup divides order of group (Lagrange’s theorem).

3, 5 and 15 can be the order of subgroup. As subgroup has atleast 4 elements and it is not equal to the given group, order of subgroup can’t be 3 and 15. Hence it is 5.

Question 2

**If V1 and V2 are 4-dimensional subspaces of a 6-dimensional vector space V, then the smallest possible dimension of V1 ∧ v2 is _______.**

.

Correct answer is =2

Solution :

Let the basis of 6-dimensional vector space be {e1, e2, e3,e4, e5, e6}. In order for V1 ∧ V2 to have smallest possible dimension V1 and V2 could be, say, {e1, e2, e3,e4} and {e3, e4, e5, e6} respectively. The basis of V1 ∧ V2 would then be {e3, e4}. => Smallest possible dimension = 2.

Question 3

**Find the value of k**

.

Correct answer is =4

Question 4

**The minimum number of arithmetic operations required to evaluate the polynomial P (X) = X**

^{5}+ 4X^{3}+ 6x + 5 for a given value of X, using only one temporary variable is _____..

Correct answer is =7

Solution :

Take x common repeatedly and form an equation and count the steps.

Question 5

**Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.**

.

Correct answer is =19

Question 6

**The length of the shortest string NOT in the language (over ∑ = {a,b}) of the following regular expression is _________. a*b* (ba)* a***

.

Correct answer is =3

Solution :

R.E= a * b*(ba)*a *

Length 0 is present as it accepts ∈ all length 1 strings are present (a,b)also aa,ab,ba,bb are present, But 'bab ' is not present. So it is 3

Question 7

**A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below?**

4, 7, 6, 1, 7, 6, 1, 2, 7, 2

4, 7, 6, 1, 7, 6, 1, 2, 7, 2

.

Correct answer is =6

Question 8

**An IP router implementing Classless Inter-domain routing (CIDR) receives a packet with address 131.23.151.76. The router’s routing table has the following entries. The identifier of the output interface on which this packet will be forwarded is _____.**

.

Correct answer is =1

Solution :

Given address 131.23.151.76.coming to the first field of given routing table

131.16.0.0/12

131.0001 0111.151.76

131.0001 0000.0.0 ( given mask bits = 12)

131.16.0.0 Matched

Coming to the 2nd field of given Routing table

131.28.0.0/14

131.0001 0111.151.76

131.0001 0100.0.0 ( given mask bits = 14)

131.20.0.0 Not matched.

Coming to the 3rd field of given Routing table

Error! Not a valid link. 131.19.0.0/16

131.0001 0111.151.76

131.0001 0

Question 9

**Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that each host has a globally unique IPv4 address. Design a 50-bit globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?**

.

Correct answer is =256

Solution :

Given that each host has a globally unique IPv4 Address and we have to design 50 – bit unique Id. So, 50 – bit in the sense (32 + 18). So, It is clearly showing that IP Address (32 – bit) followed by 18 bits.

1000 unique Ids => 1Sec

2

^{18}/ 1000 = 2

^{8}= 256

Question 10

**A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.**

.

Correct answer is =7

Question 11

**An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds). The average waiting time (in milliseconds) of the processes is _________.**

.

Correct answer is =5.5

Solution :

Average waiting time = 15 + 0 +3+4 / 4 =5.5

Question 12

**Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is _________.**

.

Correct answer is =122

Question 13

**Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y), T(z)). Then the value of the product yz is _____.**

.

Correct answer is =150

Solution :

By definition, T(9) = Dist. From 9 to 100

As given, T(9) = 1+min (T(y), T()z) = 1+min (Dist. from y to 100, Dist. From z to 100)

1=Dist. from 9 to y/Dist. From 9 to z

There are only two such values-one is the simple one step on number line i.e. 10, and the other is the shortcut associated with 9 i.e. 15.

Therefore, y and z are 10 and 15 (in any order)

Product yz = 150. Answ

Question 14

**Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O( n**

^{a}log^{b}n + m^{c}log^{d}n , the value of a + 10b + 100c + 1000d is _______..

Correct answer is =110

Solution :

It takes (log n ) time to determine numbers n1 and n2 in balanced binary search tree T such that

1. n1 is the smallest number greater than or equal to L and there is no predecessor n’1 of n1 such that n’1 is equal to n1.

2. n2 is the largest number less than or equal to H and there is no successor of n’2 of n2 such that is equal to n2.

Since there are m elements between n1 and n2, it takes ‘m’ time to add all elements between n1 and n2.

So time complexity is O (log n + m)

Question 15

**An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is __________.**

.

Correct answer is =1.54

Question 16

**The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache, 2 nanoseconds for a write operation with a hit in cache and 10 nanoseconds for a write operation with a miss in cache. Execution of a sequence of instructions involves 100 instruction fetch operations, 60 memory operand read operations and 40 memory operand write operations. The cache hit-ratio is 0.9. The average memory access time (in nanoseconds) in executing the sequence of instructions is __________.**

.

Correct answer is =1.68

Solution :

Total instruction= 100 instruction fetch operation + 60 memory operand read operation + 40 memory operand write op;

= 200 instructions (operations)

Time taken for fetching 100 instructions (equivalent to read) = 90*1ns +10*5ns =140ns

Memory operand Read operations = 90%(60)*1ns +10%(60)×5ns = 54ns + 30ns = 84ms

Memory operands write operation time = 90%(40)*2ns +10%(40)*10ns = 72ns + 40ns =112ns

Total time taken for executing 200 instructions =140 + 84 +112 = 336ns

Average memo

Question 17

**Let S be a sample space and two mutually exclusive events A and B be such that A ∪ B = S. If P(.) denotes the probability of the event, the maximum value of P(A)P(B) is ______ A**

.

Correct answer is =0.25

Question 18

**There are two elements x,y in a group (G,*) such that every element in the group can be written as a product of some number of x’s and y’s in some order. It is known that**

x * x = y * y = x * y *x * y = y* x * y *x = e

where e is the identity element. The maximum number of elements in such a group is _________________.

x * x = y * y = x * y *x * y = y* x * y *x = e

where e is the identity element. The maximum number of elements in such a group is _________________.

.

Correct answer is =4

**MY REPORT**

TOTAL = 18 | |||

ANSWERED = | |||

CORRECT / TOTAL = | /18 | ||

POSITIVE SCORE = | |||

NEGATIVE SCORE = | |||

FINAL SCORE = |