Q.1 Consider a relational table with a single record for each registered student with the following
attributes.
1. Registration_Num: Unique registration number of each registered student
2. UID: Unique identity number, unique at the national level for each citizen
3. BankAccount_Num: Unique account number at the bank. A student can have multiple
accounts or join accounts. This attribute stores the primary account number.
4. Name: Name of the student
5. Hostel_Room: Room number of the hostel
Which one of the following option is INCORRECT?(A) BankAccount_Num is candidate key(B) Registration_Num can be a primary key
(C) UID is candidate key if all students are from the same country
(D) If S is a superkey such that S∩UID is NULL then S∪UID is also a superkey
Explanation:
"X is the candidate key of a relation R only if X→Y where Y is all subsets of R"
-Navathe (Fundamentals of DBMS)
But it nither satisfies BankAccount_Num→UID nor BankAccount_Num→Registration_Num
Q.2 A computer handles several interrupt sources of which the following are relevant for this question.
* Interrupt from CPU temperature sensor (raises interrupt if CPU temperature is too high)
* Interrupt from Mouse (raises interrupt if mouse is moved or button is pressed)
* Interrupt from Keyboard (raises interrupt when a key is pressed or released)
* Interrupt from Hard Disk (raises interrupt when a disk read is completed)
Which one of these will be handled at HIGHEST priority?(A) Interrupt from Hard Disk
(B) Interrupt from Mouse
(C) Interrupt from Keyboard
(D) Interrupt from CPU temperature sensor
Explanation:
"Higher priority interrupt levels are assigned to requests which, if delayed or interrupted,
could have serious consequences. Devices with high speed transfer such as magnetic disks are given
high priority, and slow devices such as keyboard receive low priority."
-Morris Mano (Computer System Architecture)
We know that mouse pointer movements are more frequent than keyboard ticks. So its obvious that its
data transfer rate is higher than keyboard.
Delaying a CPU temperature sensor could have serious consequences, overheat can damage CPU circuitry.
From the above information we can conclude that priorities are-
CPU temperature sensor > Hard Disk > Mouse > Keyboard
Q.3 Which of the following is NOT desired in a good Software Requirement Specifications (SRS) document?
(A) Functional Requirements (B) Non-Functional Requirements
(C) Goals of Implementation (D) Algorithms for Software Implementation
Explanation:
"An SRS document should clearly document the following aspects of a system: Functional Requirements,
Non-Functional Requirements and Goals of implementation."
-Rajib Mall (Fundamentals of Software Engineering)
Q.4 HTML (HyperText Markup Language) has language elements which permit certain actions other than
describing the structure of the web document. Which one of the following actions is NOT supported
by pure HTML (without any server or client side scripting) pages?(A) Embed web objects from different sites into the same page
(B) Refresh the page automatically after a specified interval
(C) Automatic redirect to another page upon download
(D) Display the client time as the part of the page
Explanation:
<OBJECT>...</OBJECT> tag is used to embed object
<META HTTP-EQUIV="Refresh" CONTENT="5"> is used to refresh page after every 5 seconds
<META HTTP-EQUIV="Refresh" CONTENT="0;URL=another-page.html"> is used to redirect
Q.5 Which of the following pairs have DIFFERENT expressive power?(A) Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA)
(B) Deterministic push down automata (DPDA) and Non-Deterministic push down automata (NPDA)
(C) Deterministic single-tape Turing machine and Non-Deterministic single-tape Turing machine
(D) Single-tape Turing machine and Multi-tape Turing machine
Explanation:
"A language L is accepted by some DFA if and only if L is accepted by some NFA."
"If MN is a nondeterministic turing machine, then there is a deterministic turing machine MD such
that L(MN) = L(MD)"
"Every language is accepted by multitape turing machine is recursively enumerable."
-Ullman (Automata theory, languages and computations)
Q.6 A company needs to develop digital signal processing software for one of its newest inventions. The
software is expected to have 40000 lines of code. The company needs to determine the effort in
person-months needed to develop this software using the basic COCOMO model. The multiplicative
factor for this model is given as 2.8 for this software development on embedded systems, while the
exponentiation factor is given as 1.20. What is the estimation effort in person-months?(A) 234.25 (B) 932.50 (C) 287.80 (D) 122.40
Explanation:
"Effort = a1 × ( KLOC )^a2" -Rajib Mall (Fundamentals of Software Engineering)
KLOC = LOC/1000 = 40000/1000 = 40
Effort = 2.8 × 40^1.2 = 234.2
Q.7 Let the time taken to switch between user and kernel modes of execution be t1 while the time taken to
switch between two processes be t2. Which of the following is TRUE?(A) t1 > t2
(B) t1 = t2(C) t1 < t2
(D) nothing can be said about the relationship between t1 and t2
Explanation:
"Whenever a trap or interrupt occurs, the hardware switches from user mode to monitor mode (this is,
changes the state of the mode bit to 0). Thus whenever the operating system gains control of the
computer, it is in monitor mode. The system always switches to user mode (by setting the mode bit
to 1) before passing the control to a user program."
"When a context switch occurs, the kernal saves the context of old process in its PCB and loads the
saved context of the new process scheduled to run."
-Galvin (Operating System Concepts)
As mode switching is a part of context switching, it's definitely less than context switch time.
Alternatively, when ever context switch occurs between two user processes then there are two mode
changes first from user to monitor and after that monitor to user.
Q.8 A company needs to develop a strategy for software product development for which it has a choice of
two programming languages L1 and L2. The number of lines of code (LOC) developed using L2 is estimated
to be twice the LOC developed with L1. The product will have to maintained for five years. Various
parameters for the company are given in the table below.
Total cost of the project includes the cost of development and maintenance. What is the LOC for L1 for
which the total cost of the project using L1 is equal to the cost of project using L2?(A) 4000 (B) 5000 (C) 4333 (D) 4667
Explanation:
Let LOC of L1=x, so LOC of L2=2x
Now, (x/10000)*1000000 + 5*100000 = (2x/10000)*750000 + 5*50000
Solving for x=5000
Q.9 Consider the following activities related to email.
m1: Send an email from mailbox server to a mail client
m2: Download an email from mailbox server to a mail client
m3: Checking email in a web browser
Which application level protocol used in each activity?
(A) m1:HTTP m2:SMTP m3:POP
(B) m1:SMTP m2:FTP m3:HTTP(C) m1:SMTP m2:POP m3:HTTP
(D) m1:POP m2:SMTP m3:IMAP
Explanation:
"SMTP is a push protocol; it pushes the message from the client to server"
"POP and IMAP supports pull protocol they can pull the message from the server"
"Web-Based mail: Mail transfer from Alice's browser to her mail server is done through HTTP. The message
from the receiving server (the Web server) to Bob's browser is done through HTTP."
-Forouzan (Data Communications and Networking)
It's now clear that
m1:SMTP m2:POP or IMAP m3:HTTP
Q.10 If two fair coins are flipped and at least one of the outcomes is known to be head, what is the probability
that both outcomes are heads?(A) 1/3 (B) 1/4 (C) 1/2 (D) 2/3
Explanation:
Let A=at least one outcome is head and B=both outcomes are head
So P(A)=3/4, P(B)=1/4, and P(A∩B)=1/4
As P(A)×P(B) = 3/16 ≠ P(A∩B), they are not independent events
Hence, P(B/A) = P(A∩B)/P(A) = 1/3
Alternatively,
Sample Space = { HT, TH, HH}
Event = {HH}
From axiomatic definition of probability
P(Event) = |Event|/|SampleSpace| = 1/3
Q.11 A layer-4 firewall (a device that can look at all protocol headers up to the transport layer) CANNOT(A) block entire HTTP traffic during 9:00PM and 5:00AM
(B) block all ICMP traffic
(C) stop incoming traffic from a specific IP address but allow outgoing traffic to the same IP address
(D) block TCP traffic from a specific user on a multi-user system during 9:00PM and 5:00AM
Explanation:
"A packet-filter firewall cannot distinguish between different packets arriving at TCP port 80 (HTTP).
Testing must be done at the application level (using URLs)."
-Forouzan (Data Communications and Networking)
Only application-level gateway firewall can block HTTP packets.
-Stallings (Cryptography and Network Security)
Q.12 In a compiler, keywords of a language are recognized during
(A) parsing of the program (B) the code generation(C) the lexical analysis of the program (D) dataflow analysis
Explanation:
Lexical analysis includes recognition of keywords and identifiers
-Ullman (Compilers principles, techniques, & tools)
Q.13 An algorithm to find the length of the longest monotonically increasing sequence starting at index i in the
array.
Initialize Ln-1 = 1
For all i such that 0≤i≤n-2
Li = [ 1 + Li+1 if A[i]< A[i+1]
[ 1 otherwise
Finally the length of the longest monotonically increasing sequence is Max(L0, L1, ..., Ln-1).
Which of the following statement is TRUE?(A) The algorithm uses dynamic programming paradigm
(B) The algorithm has a linear complexity and uses branch and bound paradigm
(C) The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
(D) The algorithm uses divide and conquer paradigm.
Explanation:
It can be shown that algorithm has a linear complexity. As the array can be calculated from right to left in
a single go. However it doesnot uses branch and bound paradigm. The branch and bound paradigm generally used
to solve NP-hard problems. As it remove the recursions by solving each subproblems only once it reflects the
dynamic programming paradigm.
Q.14 Let P be a regular language and Q be a context-free language such that Q⊆P. (For example, let P be the
language represented by the regular expression p*q* and Q be { p^n q^n | n∈N}). Then which of the following
is ALWAYS regular?
(A) P∩Q (B) P - Q (C) Σ* - P (D) Σ* - Q
Explanation:
"If L is a regular language over alphabet Σ, then complement of L = Σ* - L is also a regular language."
-Ullman (Automata theory, languages and computations)
Q.15 A max-heap is a heap where the value of each parent is greater than or equal to the value of its children.
Which of the following is a max-heap?
Explanation:
"n-element heap has height ⌊lg n⌋." -Cormen (Introduction to Algorithms)
So, 7 elements heap has height 2. (A) has height 3 while (C) and (D) doesnot meet heap property.
Q.16 What does the following fragment of C program print?
char c[] = "GATE2011";
char *p = c;
printf("%s", p + p[3] - p[1]);
(A)GATE2011 (B) E2011 (C) 2011 (D) 011
Explanation:
p[3]='E'=69 (ASCII of E) and p[1]='A'=65 (ASCII of A)
so p[3]-p[1] = 69-65 = 4
p is address of the first element of array and p+4 is the address of fifth element which is '2'. Hence,
the output of program shows 2011 (Compiled on GCC compiler DEV-Cpp)
Q.17 Consider a hypothetical processor with an instruction of type LW R1, 20(R2), which during execution reads
a 32-bit word from memory and stores it in a 32-bit register R1. The effective address of the memory
location is obtained by the addition of a constant 20 and the contents of register R2. Which of the
following best reflects the addressing mode implementated by this instruction for operand in memory?
(A) Immediate Addressing (B) Register Addressing
(C) Register Indirect Scaled Addressing (D) Base Indexed Addressing
Explanation:
Currently explanation is not available (but answer can never be A or B)
Q.18 Let the page fault service time be 10ms in a computer with average memory access time being 20ns. If one
page fault is generated for every 10^6 memory accesses, what is the effective access time for the memory?
(A) 21ns (B) 30ns (C) 23ns (D) 35ns
Explanation:
effective access time = (1-p)×(memory access time) + p×(page-fault service time)
-Galvin (Operating System Concepts)
p = 1/10^6 = 0.000001
memory access time = 20ns
page-fault service time = 10ms = 10000000ns
so effective access time = .999999×20ns + .000001×10000000ns = 29.99998ns ≈ 30ns
Q.19 The lexical analysis for a modern computer language such as Java needs the power of which one of the
following machine models in a necessary and sufficient sense?(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-Deterministic pushdown automata
(D) Turing Machine
Explanation:
Currently explanation is not available but the answer is surely A
Q.20 If the difference between expectation of the square of a random variable (E[X²]) and the square of the
expectation of the random variable (E[X])² is denoted by R, then?
(A) R=0 (B) R<0 (C) R≥0 (D) R>0
Explanation:
Variance of a random variable X, V[X] = (E[X²]) - (E[X])² -Cormen (Introduction to Algorithms)
and variance can never be less than zero however it can be zero
Q.21 K4 and Q3 are graphs with the following structures.
K4 Q3
Which one of the following statements is TRUE in relation to these graphs?
(A) K4 is planar while Q3 is not
(B) Both K4 and Q3 are planar
(C) Q3 is planar while K4 is not
(D) Neither K4 nor Q3 are planar
Explanation:
Both can be made without intersecting edges
Q.22 A thread is usually defined as a "light weight process" because an operating system (OS) maintains smaller
data structures for a thread than for a process. In relation to this, which of the following is TRUE?
(A) On per-thread basis, the OS maintains only CPU register state
(B) The OS does not maintain a separate stack for each thread
(C) On per-thread basis, the OS does not maintain virtual memory state
(D) On per-thread basis, the OS maintains only scheduling and accounting information
Explanation:
Os maintains separate stack, register and thread-specific data for different threads.
-Galvin (Operating System Concepts)
Q.23 The minimum number of D flip-flops needed to design a mod-258 counter is(A) 9 (B) 8 (C) 512 (D) 258
Explanation:
"An n-bit binary counter consists of n flip-flops and can count in binary from 0 to 2^n - 1."
-Morris Mano (Digital logic and computer design)
So to count from 0 to n we needs at least ⌈lg n⌉ flip-flops and ⌈lg 257⌉ = 9
_ _ _ _
Q.24 The simplified SOP (Sum Of Product) form of the boolean expression (P+Q+R).(P+Q+R).(P+Q+R) is _ _ _ _ (A) (P.Q + R) (B) (P + Q.R)
_
(C) (P.Q + R) (D) (P.Q + R)
Explanation:
Q.25 Which one of the following circuit is NOT equivalent to a 2-input XNOR (exclusive NOR)gate?
Explanation:
Q.26 - Q.55 carry two marks each.
Q.26 Consider evaluating the following expression tree on a machine with load-store architecture in which
memory can be accessed only through load and store instructions. The variables a,b,c,d and e initially
stored in memory. The binary operators used in this expression tree can be evaluate by the machine only
when the operands are in registers. The instructions produce results only in a register. If no
intermediate results can be stored in memory, what is the minimum number of registers needed to
evaluate this expression?(A) 2 (B) 9 (C) 5 (D) 3
Explanation:
R1←c, R2←d, R2←R1+R2, R1←e, R2←R1-R2
Now to calculate the rest of the expression we must load a and b into the registers but we need the
content of R2 later.
So we must use another Register.
R1←a, R3←b, R1←R1-R3, R1←R1+R2
Q.27 Consider the following table of arrival time and burst time for three processes P0, P1 and P2.
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at
arrival or completion of processes. What is the average waiting time for the three processes?(A) 5.0 ms (B) 4.33 ms (C) 6.33 ms (D) 7.33 ms
Explanation:
GANTT CHART
Waiting time of P0 = 5 - 1 = 4
Waiting time of P1 = 1 - 1 = 0
Waiting time of P2 = 13 - 2 = 11
Average waiting time = (4+0+11)/3 = 5
Q.28 A deck of 5 cards (each carrying a distinct number from 1 to 5) is shuffled thoroughly. Two cards are
then removed one at time from the deck. What is the probability that the two cards are selected with
the number on the first card being one higher than the number on the second card?(A) 1/5 (B) 4/25 (C) 1/4 (D) 2/5
Explanation:
You have to select 2 cards from 5. So there are = 5!/3! = 20 elementary events
from which there are 4 favorable number of cases:
5 before 4, 4 before 3, 3 before 2 and 2 before 1.
Hence, probability = 4/20 = 1/5
Q.29 Consider a finite sequence of random values X = { x1, x2,..., xn}. Let μx be the mean and σx be the
standard deviation of X. Let another finite sequence Y of equal length be derived from this as
yi= a*xi+ b, where a and b are positive constants. Let μy be the mean and σy be the standard
deviation of this sequence. Which one of the following statements is INCORRECT?(A) Index position of mode of X in X is the same as the index position of mode of Y in Y.
(B) Index position of median of X in X is the same as the index position of median of Y in Y.
(C) μy = aμx+b(D) σy = aσx+b
Explanation:
Adding a constant like b shift the distribution while multiplying to a constant like a stretch the
distribution along median
Mode is the most frequent data of the distribution, so the index position of the mode will not change.
From the above graph it is clear that index position of the median will also not change.
Now for the mean
And for the standard deviation
Q.30 Consider a database table T containing two columns X and Y each of type integer. After the creation of
the table, one record (X=1, Y=1) is inserted in the table.
Let MX and My denote the respective maximum values of X and Y among all records in the table at any
point in time. Using MX and MY, new record is inserted in the table 128 times with X and Y values being
MX+1, 2*MY+1 respectively. It may be noted that each time after the insertion, values of MX and MY change.
What will be the output of the following SQL query after the steps mentioned above are carried out?
SELECT Y FROM T WHERE X=7;(A) 127 (B) 255 (C) 129 (D) 257
Explanation:
X increases as Xi = Xi-1 + 1 and X1=1 so Xi = i
and Y increases as Yi = 2*Yi-1 + 1 and Y1=1
So at X7=7 and Y7=2^7-1=127
Q.31 Given i=√-1, what will be the evaluation of the integral ?
(A)0 (B) 2 (C) -i (D) i
Explanation:
Q.32 Which one of the following options is CORRECT given three positive integers x, y and z, and a predicate
P(x) = ¬(x=1)∧∀y(∃z(x=y*z)⇒(y=x)∨(y=1))(A) P(x) being true means that x is a prime number
(B) P(x) being true means that x is a number other than 1
(C) P(x) is always true irrespective of the value of x
(D) P(x) being true means that x has exactly two factors other than 1 and x
Explanation:
-Kenneth H Rosen (Discrete Mathematics & Its Applications)
So the predicate is evaluated as
P(x) = (¬(x=1))∧(∀y(∃z(x=y*z)⇒((y=x)∨(y=1))))
P(x) being true means x≠1 and
For all y if there exists a z such that x=y*z then y must be x (i.e. z=1) or y must be 1 (i.e. z=x)
It means that x have only two factors first is 1 and second is x itself.
This predicate defines the prime number.
Q.33 We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we
populate the tree with the given set so that it becomes a binary search tree?(A)0 (B) 1 (C) n! (D)
Explanation:
The number of different binary search trees on n nodes is . -Cormen (Introduction to Algorithms)
Q.34 On a non-pipelined sequential processor, a program segment, which is a part of the interrupt service routine,
is given to transfer 5000 bytes from an I/O device to memory.
Initialize the address register
Initialize the count to 500
LOOP: Load a byte from device
Store in memory at address given by address register
Increment the address register
Decrement the count
If count != 0 go to LOOP
Assume that each statement in this program is equivalent to machine instruction which takes one clock cycle to
execute if it is a non-load/store instruction. The load-store instructions take two clock cycles to execute.
The designer of the system also has an alternate approach of using DMA controller to implement the same
transfer. The DMA controller requires 20 clock cycles for initialization and other overheads. Each DMA transfer
cycle takes two clock cycles to transfer one byte of data from the device to the memory.
What is the approximate speedup when the DMA controller based design is used in place of the interrupt driven
program based input-output?(A) 3.4 (B) 4.4 (C) 5.1 (D) 6.7
Explanation:
STATEMENT CLOCK CYCLE(S) NEEDED
Initialize the address register 1
Initialize the count to 500 1
LOOP: Load a byte from device 2
Store in memory at address given by address register 2
Increment the address register 1
Decrement the count 1
If count != 0 go to LOOP 1
Interrrupt driven transfer time = 1+1+500×(2+2+1+1+1) = 3502
DMA based transfer time = 20+500*2 = 1020
Speedup = 3502/1020 ≈ 3.4
Q.35 Consider the languages L1, L2 and L3 as given below.
L1 = { 0^p 1^q | p,q∈N},
L2 = { 0^p 1^q | p,q∈N and p=q} and
L3 = { 0^p 1^q 0^r | p,q,r∈N and p=q=r}. Which of the following statements is NOT TRUE?
(A) Push Down Automata (PDA) can be used to recognize L1 and L2
(B) L1 is a regular language
(C) All three languages are context free
(D) Turing machines can be used to recognize all the languages
Explanation:
L1 is regular. Its DFA is given as
L2 is not regular, can be proved using pumping lemma (refer to Ullman). But L2 is CFL.
S→AB
A→0A|ε
B→1B|ε
L3 is not CFL, can be proved using pumping lemma (refer to Ullman). But L3 is Recursive.
Every regular language is also a CFL. So PDA can be used to recognised L1 and L2.
As a CFL and Regular language is algo a Recursive language. Hence, turing machine can be used to recognise
L1, L2 and L3.
Q.36 Consider two binary operators '↑' and '↓' with the precedence of operator ↓ being lower than that of
the operator ↑. Operator ↑ is right associative while operator ↓ is left associative. Which one of the
following represents the parse tree for expression (7↓3↑4↑3↓2)?
Explanation:
the expression (7↓3↑4↑3↓2) is evaluated as ((7↓(3↑(4↑3)))↓2)
the corresponding tree to expression is B
Q.37 Database table by name Loan_Records is given below.
What is the output of the following SQL query?
SELECT count(*)
FROM(
(SELECT Borrower,Bank_Manager FROM Loan_Recordx) AS S
NATURAL JOIN
(SELECT Bank_Manager,Loan_Amount FROM Loan_Records) AS T
);(A) 3 (B) 9 (C) 5 (D) 6
Explanation:
S T
It is evaluated as ΠBorrower,Bank_Manager,Loan_Amount(σS.Bank_Manager=T.Bank_Manager(S×T))
S×T
Final rows after Project operator has been applied
Q.38 The following is the comment written for a C function.
/* This function computes the roots of a quadratic equation
a.x^2 + b.x + c = . The function stores two real roots
in *root1 and *root2 and returns the status of validity
of roots. It handles four different kinds of cases.
(i) When coefficient a is zero irrespective of discriminant
(ii) When discreminant is positive
(iii) When discriminant is zero
(iv) When discriminant is negative.
Only in case (ii) and (iii) the stored roots are valid.
Otherwise 0 is stored in roots. The function returns
0 when the roots are valid and -1 otherwise.
The function also ensures root1 >= root2
int get_QuadRoots( float a, float b, float c,
float *root1, float *root2);
*/
A software test engineer is assigned the job of doing black box testing. He comes up with the
following test cases, many of which are redundant.
Which one of the following option provide the set of non-redundant tests using equivalence class
partitioning approach from input prespective for black box testing?
(A) T1,T2,T3,T6 (B) T1,T3,T4,T5
(C) T2,T4,T5,T6 (D) T2,T3,T4,T5
Explanation:
T2,T4,T5 and T6 belong to different classes. Hence it gives an optimal test suite.
Q.39 A deterministic finite automation (DFA) D with alphabet ∑={a,b} is given below.
Which of the following finite state machines is a valid minimal DFA which accepts the same
language as D?
Explanation:
(B) accepts 'b' which is not accepted by D
(C) is not a DFA as q has two edges going for b
(D) accepts 'bba' which is not accepted by DQ.40 An application loads 100 libraries at startup. Loading each library requires exactly one disk access.
The seek time of the disk to a random locaion is given as 10 ms. Rotaional speed of disk is 6000 rpm.
If all 100 libraries are loaded from random locations on the disk, how long does it take to load all
libraries? (The time to transfer data from the disk block once the head has been positioned at the
start of the block may be neglected.)
(A) 0.50 s (B) 1.50 s (C) 1.25 s (D) 1.00 s
Explanation:
Rotational speed = 6000rpm
Average Latency = (60/rpm)/2 = 5 ms
Average access time = Average latency + Average seek time = 5 ms + 10 ms = 15 ms
As there the copy time is neglected time to load 1 library is 15 ms
Time to load 100 libraries = 100 × 15 ms = 1.5 s
Q.41 An 8KB direct-mapped write-back cache is organized as multiple blocks, each of size 32-bytes. The processor
generates 32-bit addresses. The cache controller maintains the tag information for each cache block
comprising of the following.
1 Valid bit
1 Modified bit
As many bits as the minimum needed to identify the memory block mapped in the cache.
What is the total size of memory needed at the cache controller to store meta-data (tags) for the cache?(A)4864 bits (B) 6144 bits (C) 6656 bits (D) 5376 bits
Explanation:
Cache size = 8 KB
Block size = 32 bytes
Number of cache lines = Cache size / Block size = (8 × 1024 bytes)/32 = 256
total bits required to store meta-data of 1 line = 1 + 1 + 19 = 21 bits
total memory required = 21 × 256 = 5376 bits
Q.42 Definition of a language L with alphabet {a} is given as following.
L={| k>0, and n is a positive integer constant}
What is the minimum number of states needed in DFA to recognize L?
(A) k+1 (B) n+1 (C) 2^(n+1) (D) 2^(k+1)
Explanation:
This language is same is (a.a.a...n times)†
The DFA of the language is given as
Others Coming Soon...
Total cost of the project includes the cost of development and maintenance. What is the LOC for L1 for
which the total cost of the project using L1 is equal to the cost of project using L2?
(A) 4000 (B) 5000 (C) 4333 (D) 4667
Explanation:
Let LOC of L1=x, so LOC of L2=2x
Now, (x/10000)*1000000 + 5*100000 = (2x/10000)*750000 + 5*50000
Solving for x=5000
Q.9 Consider the following activities related to email.
m1: Send an email from mailbox server to a mail client
m2: Download an email from mailbox server to a mail client
m3: Checking email in a web browser
Which application level protocol used in each activity?
(A) m1:HTTP m2:SMTP m3:POP
(B) m1:SMTP m2:FTP m3:HTTP
(C) m1:SMTP m2:POP m3:HTTP
(D) m1:POP m2:SMTP m3:IMAP
Explanation:
"SMTP is a push protocol; it pushes the message from the client to server"
"POP and IMAP supports pull protocol they can pull the message from the server"
"Web-Based mail: Mail transfer from Alice's browser to her mail server is done through HTTP. The message
from the receiving server (the Web server) to Bob's browser is done through HTTP."
-Forouzan (Data Communications and Networking)
It's now clear that
m1:SMTP m2:POP or IMAP m3:HTTP
Q.10 If two fair coins are flipped and at least one of the outcomes is known to be head, what is the probability
that both outcomes are heads?
(A) 1/3 (B) 1/4 (C) 1/2 (D) 2/3
Explanation:
Let A=at least one outcome is head and B=both outcomes are head
So P(A)=3/4, P(B)=1/4, and P(A∩B)=1/4
As P(A)×P(B) = 3/16 ≠ P(A∩B), they are not independent events
Hence, P(B/A) = P(A∩B)/P(A) = 1/3
Alternatively,
Sample Space = { HT, TH, HH}
Event = {HH}
From axiomatic definition of probability
P(Event) = |Event|/|SampleSpace| = 1/3
Q.11 A layer-4 firewall (a device that can look at all protocol headers up to the transport layer) CANNOT
(A) block entire HTTP traffic during 9:00PM and 5:00AM
(B) block all ICMP traffic
(C) stop incoming traffic from a specific IP address but allow outgoing traffic to the same IP address
(D) block TCP traffic from a specific user on a multi-user system during 9:00PM and 5:00AM
Explanation:
"A packet-filter firewall cannot distinguish between different packets arriving at TCP port 80 (HTTP).
Testing must be done at the application level (using URLs)."
-Forouzan (Data Communications and Networking)
Only application-level gateway firewall can block HTTP packets.
-Stallings (Cryptography and Network Security)
Q.12 In a compiler, keywords of a language are recognized during
(A) parsing of the program (B) the code generation
(C) the lexical analysis of the program (D) dataflow analysis
Explanation:
Lexical analysis includes recognition of keywords and identifiers
-Ullman (Compilers principles, techniques, & tools)
Q.13 An algorithm to find the length of the longest monotonically increasing sequence starting at index i in the
array.
Initialize Ln-1 = 1
For all i such that 0≤i≤n-2
Li = [ 1 + Li+1 if A[i]< A[i+1]
[ 1 otherwise
Finally the length of the longest monotonically increasing sequence is Max(L0, L1, ..., Ln-1).
Which of the following statement is TRUE?
(A) The algorithm uses dynamic programming paradigm
(B) The algorithm has a linear complexity and uses branch and bound paradigm
(C) The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
(D) The algorithm uses divide and conquer paradigm.
Explanation:
It can be shown that algorithm has a linear complexity. As the array can be calculated from right to left in
a single go. However it doesnot uses branch and bound paradigm. The branch and bound paradigm generally used
to solve NP-hard problems. As it remove the recursions by solving each subproblems only once it reflects the
dynamic programming paradigm.
Q.14 Let P be a regular language and Q be a context-free language such that Q⊆P. (For example, let P be the
language represented by the regular expression p*q* and Q be { p^n q^n | n∈N}). Then which of the following
is ALWAYS regular?
(A) P∩Q (B) P - Q (C) Σ* - P (D) Σ* - Q
Explanation:
"If L is a regular language over alphabet Σ, then complement of L = Σ* - L is also a regular language."
-Ullman (Automata theory, languages and computations)
Q.15 A max-heap is a heap where the value of each parent is greater than or equal to the value of its children.
Which of the following is a max-heap?
Explanation:
"n-element heap has height ⌊lg n⌋." -Cormen (Introduction to Algorithms)
So, 7 elements heap has height 2. (A) has height 3 while (C) and (D) doesnot meet heap property.
Q.16 What does the following fragment of C program print?
char c[] = "GATE2011";
char *p = c;
printf("%s", p + p[3] - p[1]);
(A)GATE2011 (B) E2011 (C) 2011 (D) 011
Explanation:
p[3]='E'=69 (ASCII of E) and p[1]='A'=65 (ASCII of A)
so p[3]-p[1] = 69-65 = 4
p is address of the first element of array and p+4 is the address of fifth element which is '2'. Hence,
the output of program shows 2011 (Compiled on GCC compiler DEV-Cpp)
Q.17 Consider a hypothetical processor with an instruction of type LW R1, 20(R2), which during execution reads
a 32-bit word from memory and stores it in a 32-bit register R1. The effective address of the memory
location is obtained by the addition of a constant 20 and the contents of register R2. Which of the
following best reflects the addressing mode implementated by this instruction for operand in memory?
(A) Immediate Addressing (B) Register Addressing
(C) Register Indirect Scaled Addressing (D) Base Indexed Addressing
Explanation:
Currently explanation is not available (but answer can never be A or B)
Q.18 Let the page fault service time be 10ms in a computer with average memory access time being 20ns. If one
page fault is generated for every 10^6 memory accesses, what is the effective access time for the memory?
(A) 21ns (B) 30ns (C) 23ns (D) 35ns
Explanation:
effective access time = (1-p)×(memory access time) + p×(page-fault service time)
-Galvin (Operating System Concepts)
p = 1/10^6 = 0.000001
memory access time = 20ns
page-fault service time = 10ms = 10000000ns
so effective access time = .999999×20ns + .000001×10000000ns = 29.99998ns ≈ 30ns
Q.19 The lexical analysis for a modern computer language such as Java needs the power of which one of the
following machine models in a necessary and sufficient sense?
(A) Finite state automata
(B) Deterministic pushdown automata
(C) Non-Deterministic pushdown automata
(D) Turing Machine
Explanation:
Currently explanation is not available but the answer is surely A
Q.20 If the difference between expectation of the square of a random variable (E[X²]) and the square of the
expectation of the random variable (E[X])² is denoted by R, then?
(A) R=0 (B) R<0 (C) R≥0 (D) R>0
Explanation:
Variance of a random variable X, V[X] = (E[X²]) - (E[X])² -Cormen (Introduction to Algorithms)
and variance can never be less than zero however it can be zero
Q.21 K4 and Q3 are graphs with the following structures.
K4 Q3
Which one of the following statements is TRUE in relation to these graphs?
(A) K4 is planar while Q3 is not
(B) Both K4 and Q3 are planar
(C) Q3 is planar while K4 is not
(D) Neither K4 nor Q3 are planar
Explanation:
Both can be made without intersecting edges
Q.22 A thread is usually defined as a "light weight process" because an operating system (OS) maintains smaller
data structures for a thread than for a process. In relation to this, which of the following is TRUE?
(A) On per-thread basis, the OS maintains only CPU register state
(B) The OS does not maintain a separate stack for each thread
(C) On per-thread basis, the OS does not maintain virtual memory state
(D) On per-thread basis, the OS maintains only scheduling and accounting information
Explanation:
Os maintains separate stack, register and thread-specific data for different threads.
-Galvin (Operating System Concepts)
Q.23 The minimum number of D flip-flops needed to design a mod-258 counter is
(A) 9 (B) 8 (C) 512 (D) 258
Explanation:
"An n-bit binary counter consists of n flip-flops and can count in binary from 0 to 2^n - 1."
-Morris Mano (Digital logic and computer design)
So to count from 0 to n we needs at least ⌈lg n⌉ flip-flops and ⌈lg 257⌉ = 9
_ _ _ _
Q.24 The simplified SOP (Sum Of Product) form of the boolean expression (P+Q+R).(P+Q+R).(P+Q+R) is
_ _ _ _
(A) (P.Q + R) (B) (P + Q.R)
_
(C) (P.Q + R) (D) (P.Q + R)
Explanation:
Q.25 Which one of the following circuit is NOT equivalent to a 2-input XNOR (exclusive NOR)gate?
Explanation:
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at
arrival or completion of processes. What is the average waiting time for the three processes?
GANTT CHART
Waiting time of P0 = 5 - 1 = 4
Waiting time of P1 = 1 - 1 = 0
Waiting time of P2 = 13 - 2 = 11
Average waiting time = (4+0+11)/3 = 5
= 5!/3! = 20 elementary events
from which there are 4 favorable number of cases:
5 before 4, 4 before 3, 3 before 2 and 2 before 1.
Hence, probability = 4/20 = 1/5
Mode is the most frequent data of the distribution, so the index position of the mode will not change.
From the above graph it is clear that index position of the median will also not change.
Now for the mean
And for the standard deviation
So at X7=7 and Y7=2^7-1=127
?
-Kenneth H Rosen (Discrete Mathematics & Its Applications)
So the predicate is evaluated as
P(x) = (¬(x=1))∧(∀y(∃z(x=y*z)⇒((y=x)∨(y=1))))
P(x) being true means x≠1 and
For all y if there exists a z such that x=y*z then y must be x (i.e. z=1) or y must be 1 (i.e. z=x)
It means that x have only two factors first is 1 and second is x itself.
This predicate defines the prime number.
. -Cormen (Introduction to Algorithms)
L2 is not regular, can be proved using pumping lemma (refer to Ullman). But L2 is CFL.
S→AB
A→0A|ε
B→1B|ε
L3 is not CFL, can be proved using pumping lemma (refer to Ullman). But L3 is Recursive.
Every regular language is also a CFL. So PDA can be used to recognised L1 and L2.
As a CFL and Regular language is algo a Recursive language. Hence, turing machine can be used to recognise
L1, L2 and L3.
Explanation:
the expression (7↓3↑4↑3↓2) is evaluated as ((7↓(3↑(4↑3)))↓2)
the corresponding tree to expression is B
What is the output of the following SQL query?
SELECT count(*)
FROM(
(SELECT Borrower,Bank_Manager FROM Loan_Recordx) AS S
NATURAL JOIN
(SELECT Bank_Manager,Loan_Amount FROM Loan_Records) AS T
);
S 
T
It is evaluated as ΠBorrower,Bank_Manager,Loan_Amount(σS.Bank_Manager=T.Bank_Manager(S×T))
S×T
Final rows after Project operator has been applied
Which one of the following option provide the set of non-redundant tests using equivalence class
partitioning approach from input prespective for black box testing?
T2,T4,T5 and T6 belong to different classes. Hence it gives an optimal test suite.
Which of the following finite state machines is a valid minimal DFA which accepts the same
language as D?
Explanation:
(B) accepts 'b' which is not accepted by D
(C) is not a DFA as q has two edges going for b
(D) accepts 'bba' which is not accepted by D
total bits required to store meta-data of 1 line = 1 + 1 + 19 = 21 bits
total memory required = 21 × 256 = 5376 bits
| k>0, and n is a positive integer constant}
What is the minimum number of states needed in DFA to recognize L?
Others Coming Soon...